तेज़ regex खोज: एजेंट टूल्स के लिए टेक्स्ट का अनुक्रमण
समय एक सपाट वृत्त है। जब grep का पहला संस्करण 1973 में जारी हुआ, तब यह फ़ाइलसिस्टम की टेक्स्ट फ़ाइलों में regular expressions का मिलान करने के लिए एक बुनियादी यूटिलिटी था। वर्षों के साथ, जैसे-जैसे डेवलपर टूल्स अधिक उन्नत होते गए, इसे धीरे-धीरे अधिक विशेषीकृत टूल्स ने पीछे छोड़ दिया। पहले ctags जैसे मोटे तौर पर वाक्यविन्यास-आधारित इंडेक्स आए। बाद में, कई डेवलपर्स खास प्रोग्रामिंग भाषाओं के लिए बने विशेषीकृत IDEs पर चले गए, जो कोडबेस को parse करके और वाक्यविन्यास-आधारित इंडेक्स बनाकर उसमें बेहद दक्षता से नेविगेट करने देते थे; इनमें अक्सर type-level जानकारी भी शामिल होती थी। अंततः इसे Language Server Protocol (LSP) में मानकीकृत किया गया, जिसने ये इंडेक्स नए-पुराने सभी टेक्स्ट एडिटर्स तक पहुँचा दिए। फिर, ठीक उसी समय जब LSP एक मानक बन रहा था, एजेंटिक कोडिंग आ गई—और हुआ यूँ कि एजेंट्स को grep इस्तेमाल करना बहुत पसंद है।
Agents के लिए संदर्भ जुटाने की और भी अत्याधुनिक तकनीकें हैं। हम पहले भी बात कर चुके हैं कि कई कामों में अर्थगत इंडेक्स का इस्तेमाल करके Agent के प्रदर्शन को कितना बेहतर बनाया जा सकता है, लेकिन कुछ विशिष्ट क्वेरी ऐसी होती हैं जिन्हें मॉडल केवल regular expressions से खोजकर ही सुलझा सकता है। यानी, हमें 1973 की ओर लौटना पड़ता है, भले ही तब से यह क्षेत्र काफ़ी आगे बढ़ चुका हो।
हमारे सहित ज़्यादातर एजेंट हार्नेस, खोज टूल देते समय डिफ़ॉल्ट रूप से ripgrep का उपयोग करते हैं। यह Andrew Gallant द्वारा विकसित एक standalone executable है, जो क्लासिक grep का एक विकल्प देता है, लेकिन अधिक व्यावहारिक डिफ़ॉल्ट्स के साथ (जैसे फ़ाइलों को अनदेखा करने के मामले में) और कहीं बेहतर प्रदर्शन के साथ। ripgrep अपनी तेज़ी के लिए मशहूर है, क्योंकि Andrew ने regular expressions का मिलान करते समय गति पर बहुत समय तक विचार किया है।
ripgrep किसी फ़ाइल की सामग्री पर चाहे जितनी तेज़ी से मिलान कर ले, उसकी एक गंभीर सीमा है: उसे सभी फ़ाइलों की सामग्री पर मिलान करना पड़ता है। छोटे प्रोजेक्ट में काम करते समय यह ठीक है, लेकिन Cursor के कई उपयोगकर्ता, खास तौर पर बड़े Enterprise ग्राहक, बहुत बड़े मोनोरेपोज़ में काम करते हैं। बेहद बड़े। हम नियमित रूप से ऐसे rg invocations देखते हैं जो 15 सेकंड से ज़्यादा लेते हैं, और इससे उस किसी भी व्यक्ति का वर्कफ़्लो सचमुच रुक जाता है जो Agent के साथ सक्रिय रूप से बातचीत करते हुए उसे कोड लिखने में मार्गदर्शन दे रहा होता है।
regular expressions का मिलान अब एजेंटिक विकास का एक अहम हिस्सा बन चुका है, और हमारा मानना है कि इसे स्पष्ट रूप से लक्ष्य करना बेहद ज़रूरी है: जिस तरह एक पारंपरिक IDE, Go To Definition जैसे ऑपरेशनों के लिए स्थानीय रूप से वाक्यविन्यास-आधारित इंडेक्स बनाता है, उसी तरह हम उस मुख्य ऑपरेशन के लिए इंडेक्स बना रहे हैं जिसे आधुनिक एजेंट टेक्स्ट ढूंढ़ते समय करते हैं।
पारंपरिक एल्गोरिथ्म
रेगुलर एक्सप्रेशन मैचों को तेज़ करने के लिए टेक्स्ट डेटा के अनुक्रमण का विचार बिल्कुल नया नहीं है। इसे पहली बार 1993 में Zobel, Moffat और Sacks-Davis ने "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files" नामक एक शोध-पत्र में प्रकाशित किया था। इसमें वे n-grams (स्ट्रिंग के ऐसे खंड जिनकी लंबाई n वर्ण होती है) का इस्तेमाल करके inverted index बनाने का एक तरीका प्रस्तुत करते हैं, साथ ही रेगुलर एक्सप्रेशंस को n-grams के एक वृक्ष में तोड़ने के लिए heuristics भी बताते हैं, जिन्हें इंडेक्स में खोजा जा सकता है।
अगर आपने इस अवधारणा के बारे में पहले सुना है, तो संभवतः वह उस शोध-पत्र से नहीं, बल्कि एक ब्लॉग पोस्ट से होगा, जिसे Russ Cox ने 2012 में Google Code Search के बंद होने के तुरंत बाद प्रकाशित किया था। आइए इन indexes के बुनियादी घटकों को जल्दी से फिर देख लें, क्योंकि वे तब से विकसित अनुक्रमण के लगभग हर दूसरे तरीके पर किसी न किसी रूप में लागू होते हैं।
उल्टे इंडेक्स
एक उल्टा इंडेक्स सर्च इंजन के पीछे की मूलभूत डेटा संरचना है। अनुक्रमित किए जाने वाले दस्तावेज़ों के एक सेट से शुरू करके, आप हर दस्तावेज़ को टोकन में बाँटकर एक उल्टा इंडेक्स बनाते हैं। इसे टोकनीकरण कहा जाता है, और इसे करने के कई अलग-अलग तरीके हैं — इस उदाहरण में, हम सबसे सरल तरीका अपनाएँगे: अलग-अलग शब्दों को टोकन मानकर। फिर ये टोकन एक शब्दकोश-जैसी डेटा संरचना में कुंजियाँ बन जाते हैं, और मान के रूप में हर टोकन के लिए उन सभी दस्तावेज़ों की सूची रखी जाती है जिनमें वह दिखाई देता है। इस सूची को आम तौर पर posting list कहा जाता है, क्योंकि हर दस्तावेज़ की एक विशिष्ट पहचान एक संख्यात्मक मान, यानी "posting", से होती है। जब आप एक या अधिक टोकन खोजते हैं, तो हम उनकी posting lists लोड करते हैं; अगर posting list एक से अधिक हों, तो हम उनका प्रतिच्छेद निकालते हैं, ताकि वे दस्तावेज़ मिल सकें जो उन सभी में मौजूद हैं।
1. Documents
Edit documents to see how the index updates. Click to select and view terms.
Hover or tap a term to trace the same index entry.
2. Inverted Index
Each term maps to documents containing it. Hover or tap to inspect one entry at a time.
across→and→bat→black→by→cat→cautious→curious→drift→fall→in→light→rat→room→sat→small→the→watched→watching→window→3. Search
Search for terms to find matching documents.
यही डिज़ाइन (जिसके ऊपर काफ़ी अतिरिक्त जटिलता जोड़ी जाती है) आज उपलब्ध ज़्यादातर सर्च इंजनों की नींव है। लेकिन ये प्राकृतिक भाषा के लिए बने सर्च इंजन हैं, जबकि हम नियमित अभिव्यक्तियों की खोज करना चाहते हैं, और उन्हें स्रोत कोड पर मिलाना चाहते हैं। यहाँ यह तरीका ठीक से काम नहीं करता।
आप यहाँ टोकनीकरण के बारे में बहुत गहराई से सोचकर कुछ उपयोगी बनाने की कोशिश कर सकते हैं — जैसे हर प्रोग्रामिंग भाषा के सिंटैक्स को समझना, स्रोत कोड में पहचानकर्ताओं को तोड़ना, वगैरह। लेकिन इसे सही ढंग से करना बहुत कठिन है। GitHub के शुरुआती दिनों में, उनका Code Search फ़ीचर इसी तरह काम करता था: प्रोग्रामिंग भाषाओं के लिए एक बहुत जटिल tokenizer और एक बहुत बड़ा ElasticSearch cluster। नतीजे अच्छे नहीं थे, और इस फ़ीचर के बारे में लोगों की राय भी बहुत खराब थी। आप पहचानकर्ताओं को खोज सकते थे (कुछ हद तक), लेकिन नियमित अभिव्यक्तियों का मिलान नहीं कर सकते थे। इसके लिए आपको टोकनीकरण का एक बेहतर तरीका चाहिए।
ट्राइग्राम विघटन
रेगुलर एक्सप्रेशन के मिलान के लिए स्रोत कोड पर साधारण टोकनाइज़ेशन उपयोगी नहीं होता। हमें दस्तावेज़ों को और बुनियादी हिस्सों में बाँटना पड़ता है। पारंपरिक एल्गोरिदम ट्राइग्राम चुनता है: इनपुट स्ट्रिंग में तीन वर्णों का हर ओवरलैपिंग खंड एक टोकन होता है।
तीन ही क्यों? हम इन ट्राइग्रामों को अपने inverted index में कुंजियों के रूप में संग्रहीत करेंगे। अगर हम bigrams (2 वर्णों के खंड) चुनें, तो हमारे इंडेक्स में बहुत कम कुंजियाँ होंगी, अधिकतम 64k तक, लेकिन हर कुंजी की posting lists बहुत बड़ी होंगी — इतनी बड़ी कि उनके साथ दक्षता से काम करना मुश्किल हो जाएगा। अगर हम quadgrams (4 वर्णों के खंड) चुनें, तो posting lists बहुत छोटी होंगी, जो अच्छी बात है, लेकिन फिर हमारे inverted index में अरबों कुंजियाँ होंगी, और उसके साथ काम करना भी कठिन होगा।
इसलिए ट्राइग्राम काफ़ी अच्छा संतुलन देते हैं। इससे दस्तावेज़ों का अनुक्रमण करते समय टोकनाइज़ेशन बहुत सरल हो जाता है: जिस दस्तावेज़ का अनुक्रमण किया जा रहा है, उसमें से 3 वर्णों का हर ओवरलैपिंग क्रम निकालें और inverted index में उन्हें अपने टोकन के रूप में उपयोग करें।
असल जटिलता तब आती है जब किसी रेगुलर एक्सप्रेशन को इस तरह टोकनाइज़ करना हो कि उसका इंडेक्स से मिलान किया जा सके। रेगुलर एक्सप्रेशन का अपना syntax होता है, इसलिए आपको उन्हें parse करना पड़ता है और heuristics का उपयोग करके यह समझना होता है कि अभिव्यक्ति के जिन हिस्सों में वास्तव में पाठ है, उनसे कौन-कौन से ट्राइग्राम निकाले जा सकते हैं।
किसी literal string को ट्राइग्रामों में विघटित करना सीधा है, क्योंकि यह वही एल्गोरिदम है जो दस्तावेज़ का अनुक्रमण करते समय इस्तेमाल होता है। स्ट्रिंग में मौजूद हर overlapping ट्राइग्राम निकालें; जो दस्तावेज़ इन सभी ट्राइग्रामों को समाहित करता है, उसमें literal होने की संभावना है (लेकिन यह ज़रूरी नहीं है!)। Alternations को अलग-अलग विघटित किया जाता है, जिससे दो branch बनती हैं, जिनमें से कोई एक दस्तावेज़ में मौजूद होनी चाहिए ताकि उसका मिलान हो सके। inverted index पर हम इसे posting lists को intersect करने के बजाय join करके query करते हैं। Character classes को कई ट्राइग्रामों में विघटित किया जा सकता है। छोटी classes, जैसे [rbc]at, class के हर element के लिए एक ट्राइग्राम देती हैं। broader character classes का उपयोग करते समय, हम बस उन सीमाओं के आर-पार ट्राइग्राम निकालना छोड़ देते हैं।
/MAX_FILE_SIZE/→MAX_FILE_SIZE→"MAX_FILE_SIZE"→सब कुछ एक साथ जोड़ना
हम जानते हैं कि इन दस्तावेज़ों को टोकनाइज़ करने का सही तरीका trigram हैं, हम जानते हैं कि इंडेक्स बनाते समय दस्तावेज़ों को कैसे टोकनाइज़ करना है, और खोज के समय queries को कैसे टोकनाइज़ करना है। इन सभी को मिलाकर हम एक वास्तविक खोज इंडेक्स बना सकते हैं, जो regular expressions का बेहद कुशलता से मिलान कर सकता है। किसी भी regular expression को trigrams के एक सेट में विभाजित करके और inverted index से सभी प्रासंगिक posting lists लोड करके, हमें दस्तावेज़ों की एक ऐसी सूची मिलती है जो संभावित रूप से हमारे regular expression से मेल खा सकती है। यह महत्वपूर्ण है! अंतिम परिणाम सेट केवल सभी संभावित दस्तावेज़ों को वास्तव में लोड करके और regular expression का मिलान "पारंपरिक तरीके" से करके ही मिलेगा। लेकिन दस्तावेज़ों का यह उप-समूह होना, पूरे कोडबेस को फ़ाइल-दर-फ़ाइल स्कैन करके मिलान करने की तुलना में, हमेशा तेज़ होता है।
1. Documents
Edit documents to see how the index updates. Click to select and view trigrams.
Hover or tap a trigram to trace the same index entry.
2. Inverted Index
Each trigram maps to documents containing it. Hover or tap to inspect one entry at a time.
·ba→·ca→·ra→·sa→a·c→at·→bat→cat→e·b→e·c→e·r→he·→ran→rat→sat→t·r→t·s→the→3. Search
Search using literal strings or regular expressions to see trigram decomposition.
Try cat, the rat, or the regex c[au]t.
यह डिज़ाइन हर तरह से पूरी तरह कार्यक्षम है। google/codesearch और sourcegraph/zoekt जैसे प्रोजेक्ट trigram के inverted index का इस्तेमाल करके बड़े indexes के लिए अच्छा प्रदर्शन देते हैं (और सभी search engines की तरह, वे इसके ऊपर काफ़ी अधिक जटिलता भी जोड़ते हैं)। लेकिन यहाँ कुछ स्पष्ट कमियाँ हैं: इंडेक्स का आकार छोटा नहीं होता, और query time पर decomposition में एक समझौता करना पड़ता है। यदि आप simple heuristics का उपयोग करते हैं, तो queries कुछ ही trigrams में विभाजित होंगी, और इसका नतीजा यह होगा कि मिलान के लिए बहुत-से संभावित दस्तावेज़ मिलेंगे। यदि आप complex heuristics का उपयोग करते हैं, तो आपके पास दर्जनों —शायद सैकड़ों— trigrams हो सकते हैं, और inverted index से उन सभी को लोड करना, शुरू से सब कुछ खोजने जितना धीमा हो सकता है।
हम इससे बेहतर कर सकते हैं।
Suffix Arrays: एक प्रसंगांतर
चूँकि हम regular expression खोजों के लिए टेक्स्ट डेटा के अनुक्रमण के इतिहास पर बात कर रहे हैं, मैं थोड़ा प्रसंगांतर लेते हुए इस implementation पर चर्चा करना चाहूँगा, जिसे Nelson Elhage ने 2015 में अपनी livegrep वेब सेवा के लिए विकसित किया था। उद्योग के अन्य बड़े प्रयासों की तुलना में, livegrep बहुत छोटा है —यह केवल Linux Kernel के सबसे हाल के संस्करण को ही अनुक्रमित करता है— लेकिन अपने सीमित दायरे के कारण इसका implementation वहाँ मौजूद किसी भी दूसरी चीज़ से बिल्कुल अलग है, और यही बात इसे बेहद रोचक और चर्चा के योग्य बनाती है।
Nelson ने इस समस्या को मूल सिद्धांतों से हल किया: इस search engine के पीछे कोई inverted index नहीं है। इसके बजाय, पूरे स्रोत कोड को एक suffix array के भीतर अनुक्रमित किया जाता है।
suffix array की अवधारणा अपने-आप में स्पष्ट है: किसी string के सभी suffixes का क्रमबद्ध array। यदि आप किसी बड़ी string के लिए ऐसा array बनाने की कोशिश करेंगे, तो आप देखेंगे कि यह data structure बहुत तेज़ी से बढ़ता है। यह एक काफ़ी महँगा index लग सकता है, और कई मायनों में यह है भी, लेकिन यदि आपके पास मूल string तक पहुँच है, तो इसके storage को काफ़ी अच्छी तरह compress किया जा सकता है: आप बस हर suffix की शुरुआत के offsets store कर सकते हैं।
एक बार जब हम खोजे जाने वाले corpus के लिए suffix array बना लेते हैं, तो regular expression को literals में विभाजित करके regular expression खोजें कुशलतापूर्वक की जा सकती हैं। इसके बाद regular expression के लिए हर संभावित match position को suffix array पर binary search करके पाया जा सकता है।
कोई छोटी string जैसे th खोजकर देखें, ताकि आप देख सकें कि binary search दस्तावेज़ में उन सभी positions का दायरा कैसे तय करती है जहाँ यहवास्तव में match करता है।
Search the Suffix Array
regular expression syntax में मौजूद अधिक जटिल संरचनाओं का मिलान भी suffix array के इन्हीं गुणों का उपयोग करके किया जा सकता है। उदाहरण के लिए, यदि आप [a-z] जैसी किसी character range का मिलान कर रहे हैं, तो आप range की शुरुआत और अंत के लिए binary search करके array का दायरा सीमित कर सकते हैं। उन दो endpoints के बीच की सामग्री अनिवार्य रूप से उस range से match करेगी।
1. Input String
Enter a string to build its suffix array. Each position in the string defines a suffix.
Hover or tap a suffix row to see where that suffix starts in the string.
2. Suffix Array
All suffixes sorted lexicographically. The array stores only indices; suffixes are derived from the original string.
·and·thither·thitherand·thitherd·thithererer·and·thitherherher·and·thitherhitherhither·and·thitheritherither·and·thithernd·thitherrr·and·thithertherther·and·thitherthitherयहाँ कमियाँ क्या हैं? एक suffix array किसी input string से बनाया जाना चाहिए। यह एक बड़ी सीमा है। यदि आप किसी बड़े कोडबेस (या शायद कई अलग-अलग कोडबेस) को अनुक्रमित करने की कोशिश कर रहे हैं, तो पहले आपको सारी सामग्री को जोड़कर एक single string बनानी होगी, और उसी से suffix array बनाना होगा। suffix array के भीतर मिलान करते समय, आपको match position को उस मूल फ़ाइल से मैप करने के लिए एक सहायक data structure की भी आवश्यकता होगी, जिसमें वह मौजूद है। यह ऐसी जटिलता नहीं है जिसे पार न किया जा सके, लेकिन इससे index को dynamic रूप से update करना बहुत महँगा हो जाता है। यह एक ऐसा समाधान है जिसे स्केल करना बहुत कठिन है।
प्रायिकतामूलक मास्क के साथ Trigram क्वेरी
अब कुछ अधिक पारंपरिक डिज़ाइनों पर लौटते हैं: यहाँ एक तरीका है, जिसे मूल रूप से GitHub में Project Blackbird के लिए विकसित किया गया था। यह एक अनुसंधान प्रोजेक्ट था, जिसका लक्ष्य पुराने Code Search फ़ीचर को बदलना था। जैसा कि हमने पहले चर्चा की है, पुरानी खोज स्रोत कोड को tokens में विभाजित करके लागू की गई थी और वह regular expressions का मिलान नहीं कर सकती थी। इस नए implementation का लक्ष्य कुछ ऐसा विकसित करना था जो यह कर सके।
शुरुआती iterations में keys के रूप में trigrams के साथ classic inverted index का उपयोग करने की कोशिश की गई, लेकिन बहुत जल्दी capacity से जुड़ी समस्याएँ सामने आने लगीं। GitHub में बहुत सारा कोड है, और उसे अनुक्रमित करने के लिए trigrams का इस्तेमाल करने पर posting lists इतनी बड़ी हो गईं कि उनमें खोज करना व्यावहारिक नहीं रहा।
जब trigrams अपेक्षा के अनुसार काम नहीं कर पाए, तो अगला चरण उन n-grams के लिए बेहतर आकार खोजने का था जिन्हें अनुक्रमित किया जाना था। हमने देखा है कि bigrams बहुत व्यापक होते हैं, क्योंकि उनकी posting lists संभालना मुश्किल हो जाती हैं, और quadgrams बहुत विशिष्ट होते हैं, क्योंकि इससे हमारे index में keys की संख्या बहुत बढ़ जाती है। Trigrams दोनों के बीच एक अच्छा संतुलन हैं, लेकिन व्यवहार में आदर्श आकार कुछ ऐसा है जैसे... 3.5-grams। लेकिन हम किसी character को दो हिस्सों में तो नहीं बाँट सकते, है न?
असल में, हम उसके काफ़ी क़रीब कुछ कर सकते हैं: यह डिज़ाइन inverted index के लिए key के रूप में trigrams का उपयोग करने और posting lists में उस "चौथे character" के बारे में अतिरिक्त जानकारी जोड़ने का प्रस्ताव रखता है, जो उस विशेष document में trigram के बाद आता है। ऐसा करने के लिए, हम उस चौथे character को एक अतिरिक्त byte के रूप में सीधे store कर सकते थे, लेकिन तब हमारा index एक quadgram index बन जाता, और हमने देखा है कि वे store करने के लिए बहुत बड़े होते हैं। इसके बजाय, हम एक bloom filter store करते हैं, जिसमें वे सभी characters शामिल होते हैं जो उस विशेष trigram के बाद आते हैं।
1. Documents & Trigrams
Each trigram gets an 8-bit locMask (position mod 8) and nextMask (hash of each follow-up character).
Hover or tap a trigram to trace the same entry in the index.
2. Phrase-Aware Trigram Index
Each (trigram, doc) entry stores two 8-bit masks. Hover or tap to inspect one trigram at a time.
·ca·fo·re·rua·rcarcatd·ce·ce·fed·foxhe·ox·redruntheunsx·rpos mod 8 = i.आप bloom filter को एक बहुत बड़ी और जटिल data structure के रूप में सोच सकते हैं, लेकिन ऐसा होना ज़रूरी नहीं है। bloom filter को बहुत कम bits में समेटा जा सकता है। अगर encoding सावधानी से की जाए, तो 8 bits में काफ़ी जानकारी समा सकती है। प्रति posting सिर्फ़ दो bytes के साथ, हम classic trigram index की दो सबसे बड़ी समस्याओं का समाधान कर सकते हैं।
हर trigram के बाद आने वाले characters को समेटे हुए mask की मदद से, हमारा inverted index trigram keys का उपयोग करके बनाया जा सकता है, लेकिन उस पर query quadgrams के जरिए की जा सकती है! इससे संभावित documents का दायरा एक साधारण trigram index की तुलना में पहले ही काफ़ी कम हो जाता है।
दूसरा augmented mask, जिसमें वे offsets होते हैं जहाँ trigram document में दिखाई देता है, trigram ambiguity की समस्या को हल करता है: सिर्फ़ इसलिए कि किसी document में दो trigrams मौजूद हैं, इसका यह मतलब नहीं कि वे वास्तव में एक-दूसरे के ठीक बगल में हैं — जबकि हमारी query के मिलान के लिए हमें यही चाहिए। दूसरे trigram के position mask को एक bit बाएँ shift करके और उसकी तुलना पहले trigram के mask से करके, हम यह सुनिश्चित कर सकते हैं कि वे सचमुच आस-पास हैं। खास तौर पर बहुत सामान्य trigrams के मामले में, candidate documents की सूची को और भी छोटा करने के लिए यह बेहद मूल्यवान है।
यह सारी जानकारी, स्वाभाविक रूप से, प्रायिकतामूलक है: bloom filter में store किसी भी चीज़ की तरह, यह false positives दे सकती है। लेकिन यहाँ false positives हमेशा स्वीकार्य हैं, क्योंकि अंतिम मिलान deterministic तरीके से सीधे text पर किया जाता है। लक्ष्य यह है कि हमारे index का उपयोग करके उन संभावित documents की संख्या न्यूनतम की जाए जिन्हें हमें scan करना पड़ता है।
Search the Phrase Index
"e·f" → "·fo"e·f→D0·fo→D0e·f, D0):7654321010000000o) = bit 7Bit is sete·f):00000100·fo):00001000परिणामी indexes बेहद efficient हैं, लेकिन उनकी एक बड़ी कमी है। Bloom filters saturated हो सकते हैं। यह bloom filters का एक दुर्भाग्यपूर्ण गुण है; उन्हें अपडेट किया जा सकता है, लेकिन अगर आप उनमें बहुत अधिक data जोड़ दें, तो अंततः filter के सभी bits set हो जाते हैं। और एक बार bloom filter saturated हो जाए, तो वह हर चीज़ से मेल खाने लगता है, और हम फिर उसी प्रदर्शन पर लौट आते हैं जिस पहले index के बारे में हमने बात की थी।
यह ऐसा index है जो storage को न्यूनतम करता है, लेकिन जब आपको इसे in-place अपडेट करना हो, तो यह परेशानी पैदा करता है।
Sparse N-grams: ज़्यादा स्मार्ट Trigram चयन
यह एक और बेहद स्मार्ट विचार है। आपने शायद इसे ClickHouse में उनके regular expression operator के लिए उपयोग होते देखा होगा, और GitHub में भी, नई Code Search सुविधा में, जो कुछ साल पहले शिप हुई थी और regular expressions के मिलान की अनुमति देती है। इसे Sparse N-grams कहा जाता है, और यह बीच का सबसे बेहतरीन संतुलन है।
एक पारंपरिक trigram इंडेक्स हर लगातार 3-अक्षरों के अनुक्रम को निकालता है, लेकिन आप देख सकते हैं कि इससे बहुत ज़्यादा दोहराव पैदा होता है। हर trigram के अक्षर उसके बगल वाले trigram में फिर से आ जाते हैं! इस algorithm में, हम n-grams की यादृच्छिक संख्या निकालते हैं, और हर n-gram की लंबाई भी यादृच्छिक होती है।
बेशक, यहाँ यादृच्छिक सचमुच पूरी तरह यादृच्छिक नहीं हो सकता, क्योंकि तब इंडेक्स पर क्वेरी नहीं की जा सकेगी। हम दस्तावेज़ में हर अक्षर-युग्म को एक "weight" दे रहे हैं। यह weight कुछ भी हो सकता है, बस उसका deterministic होना ज़रूरी है (ClickHouse दो अक्षरों के crc32 hash का उपयोग करता है)। फिर, हमारे sparse n-grams वे सभी substrings होते हैं जिनके दोनों सिरों के weights, भीतर मौजूद सभी weights से सख्ती से बड़े होते हैं।
अहम बात यह है कि sparse n-grams की लंबाई कोई भी हो सकती है। वे सुसंगत नहीं होते। इसका यह भी मतलब है कि हम इनकी बहुत बड़ी संख्या जनरेट कर सकते हैं — अगर हम सिर्फ trigrams निकाल रहे होते, तो उससे भी ज़्यादा। लेकिन क्योंकि n-grams deterministic तरीके से जनरेट किए जाते हैं, हम query time पर कुछ बहुत महत्वपूर्ण optimizations कर सकते हैं। आइए देखें कैसे।
यह algorithm समझना आसान नहीं है, इसलिए हमें इसके साथ थोड़ा प्रयोग करना होगा। आप पीछे और आगे वाले तीरों का उपयोग करके visualization में इसे चरण-दर-चरण देख सकते हैं।
इनपुट के character breakdown के ऊपर, आप हर character pair को दिया गया यादृच्छिक weight देख सकते हैं। यही weights उन segments को तय करते हैं जिन्हें n-grams के रूप में निकाला जाएगा।
सबसे नीचे वाले section में, आप यह देख सकते हैं कि इनपुट string से कितने sparse n-grams निकाले जाते हैं, और कितने निकाले जाते यदि हम bigrams, trigrams या quadgrams निकाल रहे होते। इस स्पष्ट अंतर पर ध्यान दें: हम वास्तव में बहुत ज़्यादा sparse n-grams निकाल रहे हैं!
तो यहाँ असल बात क्या है? क्या हम बस कुछ बेवकूफ़ी कर रहे हैं? पूरी तरह नहीं। हम अनुक्रमण के समय शुरुआत में ज़्यादा लागत चुका रहे हैं ताकि query time पर बहुत तेज़ queries मिल सकें। build_all algorithm, जिसे आप अभी देख रहे हैं, वही है जिसका हम दस्तावेज़ों के अनुक्रमण के समय उपयोग करते हैं। यह इनपुट से संभव सभी sparse n-grams निकालता है। लेकिन ध्यान दें कि querying के समय हमें ऐसा करने की ज़रूरत नहीं होती। क्योंकि weights यादृच्छिक होने के बावजूद deterministic हैं, query time पर हम एक covering algorithm का उपयोग कर सकते हैं, जो केवल उतने ही न्यूनतम n-grams जनरेट करता है जितने इंडेक्स में मिलान के लिए आवश्यक हों।
Sparse N-Gram Algorithm
हम जानते हैं कि ये n-grams न्यूनतम हैं क्योंकि index time पर, हम इन्हें तभी जनरेट करते हैं जब भीतर मौजूद सभी weights, किनारों पर मौजूद weights से छोटे हों। इसलिए, हमें केवल किनारों पर मौजूद sparse n-grams निकालने की ज़रूरत है —यह सभी trigrams निकालने की तुलना में बहुत कम हैं— और हम अपने संभावित documents को बहुत उच्च विशिष्टता के साथ चुन सकेंगे।
क्या हम इससे बेहतर कर सकते हैं? हाँ! बल्कि, बहुत बेहतर। उदाहरण के लिए, हम एल्गोरिद्म में अपने वेट फ़ंक्शन के रूप में crc32 इस्तेमाल कर रहे थे। हालांकि, यहाँ कोई भी हैश फ़ंक्शन काम करेगा, बस वह deterministic होना चाहिए। आइए कुछ बहुत स्मार्ट चुनें: ऐसा हैश फ़ंक्शन जो हर उस वर्ण-युग्म को ज़्यादा वेट दे जो वास्तव में बहुत दुर्लभ है, और हर उस युग्म को कम वेट दे जो बहुत आम है।
इस हैश फ़ंक्शन की गणना करना आसान है। चूँकि हम स्रोत कोड का अनुक्रमण करने जा रहे हैं, हम इंटरनेट से एक-दो टेराबाइट ओपन-सोर्स कोड ले सकते हैं और उसमें मिलने वाले सभी वर्ण-युग्मों के लिए एक फ़्रीक्वेंसी टेबल बिल्ड कर सकते हैं। वही फ़्रीक्वेंसी टेबल हमारा हैश फ़ंक्शन है। देखें, जब हम इसे अपने एल्गोरिद्म पर लागू करते हैं तो क्या होता है: अब सबसे ज़्यादा वेट सबसे कम बार आने वाले वर्ण-युग्मों के नीचे दिखाई देते हैं, और इसी वजह से covering mode में lookup के लिए और भी कम n-grams लगते हैं, और ऐसे दस्तावेज़ भी कम हो जाते हैं जो संभवतः मैच कर सकते हैं।
यह तरीका, जो posting lookups की संख्या को न्यूनतम करता है, उपयोगकर्ताओं की मशीनों पर कुशलतापूर्वक क्वेरी किए जा सकने वाले इंडेक्स बनाने के लिए एक आदर्श शुरुआती बिंदु साबित होगा।
यह सब, आपकी मशीन पर
रेगुलर एक्सप्रेशन खोज को तेज़ करने वाले इंडेक्स को कहीं न कहीं रहना ही पड़ता है। अब तक हमने जो भी डिज़ाइन देखे हैं, वे सभी सर्वर-साइड पर परिनियोजित किए गए हैं, और जिन अर्थगत इंडेक्स की हमने बात की है, उन्हें भी सर्वर पर ही प्रबंधित किया जाता है और उन्हीं पर क्वेरी चलाई जाती है। फिर भी, यहाँ हम एक अलग दिशा चुन रहे हैं: हम उपयोगकर्ताओं की मशीनों पर ही इंडेक्स बना रहे हैं और उन्हीं पर क्वेरी कर रहे हैं।
इन इंडेक्स को लोकल रखना कई वजहों से समझदारी भरा है। पहली बात, रेगुलर एक्सप्रेशन मैच करने के लिए जो कुछ चाहिए होता है, उसमें इंडेक्स सिर्फ़ एक हिस्सा हैं। वे आपको दस्तावेज़ों का एक सीमित उपसमुच्चय देते हैं जहाँ रेगुलर एक्सप्रेशन मैच हो सकते हैं, लेकिन इसके बाद भी हर फ़ाइल को अलग-अलग स्कैन करना पड़ता है। इसे सर्वर पर करने का मतलब होगा या तो सभी फ़ाइलों को सिंक करना, या क्लाइंट और सर्वर के बीच बार-बार महंगे राउंडट्रिप करना। क्लाइंट पर यह करना आसान है, और इससे डेटा स्टोरेज से जुड़ी कई सुरक्षा और गोपनीयता संबंधी चिंताओं से भी बचा जा सकता है।
इस फ़ंक्शनैलिटी के लिए लेटेंसी भी बेहद अहम है। हमारा Composer मॉडल उद्योग में प्रति सेकंड टोकन (TPS) के मामले में सबसे तेज़ मॉडलों में से एक है, और हम इसे और अधिक स्मार्ट और तेज़ बनाने के लिए लगातार काम कर रहे हैं। ऐसे अहम ऑपरेशन में, जिसका मॉडल लगातार उपयोग करता है (अक्सर समानांतर में), नेटवर्क राउंडट्रिप जोड़ना सिर्फ़ अनावश्यक रुकावट और देरी बढ़ाता है, और हमें एजेंट्स के साथ इंटरैक्ट करने के अपने लक्ष्य से उलटी दिशा में ले जाता है।
अर्थगत इंडेक्स के विपरीत, रेगुलर एक्सप्रेशन खोज के लिए इंडेक्स का बहुत ताज़ा होना भी ज़रूरी है, खासकर तब जब मॉडल अपनी ही लिखी हुई चीज़ें पढ़ रहा हो। हमें अपने अर्थगत इंडेक्स को लगातार अपडेट करने की ज़रूरत नहीं पड़ती, क्योंकि किसी फ़ाइल में बदलाव के बाद उसके लिए एम्बेडिंग्स दोबारा कम्प्यूट करने से नया एम्बेडिंग बहु-आयामी स्पेस में अपनी स्थिति को इतना नहीं बदलता कि उसका असर बड़ा हो। हम जो nearest-neighbor खोज करते हैं, वह फिर भी Agent को सही दिशा में भेजती है। लेकिन अगर एजेंट किसी खास टेक्स्ट को खोज रहा हो और उसे वह न मिले, तो वह अक्सर बेकार की खोज में भटकने लगता है, टोकन बर्बाद करता है, और हमारे प्रदर्शन अनुकूलन के मूल उद्देश्य को ही निष्फल कर देता है।
इन इंडेक्स को क्लाइंट पर लाने के साथ अपनी कुछ चुनौतियाँ भी आती हैं। डिस्क डेटा को सिंक करना जटिल और महँगा हो सकता है, लेकिन व्यवहार में हम इसे काफ़ी कुशल बनाते हैं: हम इंडेक्स की स्थिति को आधारभूत Git रिपॉज़िटरी के एक कमिट पर आधारित रखकर नियंत्रित करते हैं। उपयोगकर्ता और एजेंट के परिवर्तन इसके ऊपर एक लेयर के रूप में स्टोर किए जाते हैं। इससे इसे अपडेट करना बहुत तेज़ हो जाता है, और स्टार्टअप पर लोड और सिंक करना भी बहुत तेज़ रहता है।
यह सुनिश्चित करने के लिए कि एडिटर में मेमोरी उपयोग न्यूनतम रहे, हम अपने इंडेक्स को दो अलग-अलग फ़ाइलों में स्टोर करते हैं। पहली फ़ाइल में इंडेक्स की सभी posting lists एक के बाद one होती हैं — निर्माण के दौरान हम इसे सीधे डिस्क पर flush कर देते हैं। दूसरी फ़ाइल में सभी n-grams के hashes और postings फ़ाइल में उनकी संबंधित posting list के offset के साथ एक sorted table होती है। यहाँ पूरे n-grams स्टोर किए बिना सिर्फ़ hashes रखना हमेशा सुरक्षित है: अगर दो hashes टकरा जाएँ, तो इससे posting list थोड़ी अधिक व्यापक हो सकती है (हालाँकि व्यवहार में इसकी संभावना बेहद कम है), लेकिन इससे गलत परिणाम नहीं मिल सकते। इससे हमें lookup table के लिए बहुत सघन लेआउट भी मिलता है। फिर हम एडिटर प्रक्रिया में इस table को, और सिर्फ़ इसी table को, mmap करते हैं, और binary search के ज़रिए क्वेरी serve करने के लिए इसका उपयोग करते हैं। खोज एक offset लौटाती है, और हम postings फ़ाइल में उसी offset पर सीधे पढ़ते हैं।
Hover or tap a lookup-table row to trace where its posting lives on disk.
000129 → @0 → MAXनिष्कर्ष
हमने पाया है कि तेज़ मॉडल्स को टेक्स्ट खोज इंडेक्स उपलब्ध कराना, जैसे हमारे अपने Composer 2 को, एजेंटिक वर्कफ़्लो में गुणात्मक फर्क लाता है। इसका प्रभाव बड़े Enterprise रिपॉज़िटरी में और भी अधिक स्पष्ट होता है, क्योंकि grep Agent की उन कुछ कार्रवाइयों में से एक है जिनकी विलंबता उस कोड के आकार और जटिलता के साथ बढ़ती है, जिस पर काम किया जा रहा हो। Composer 2 के साथ चल रहे इन उदाहरण वर्कफ़्लो पर नज़र डालें: कोडबेस में खोज करने में लगने वाले समय को पूरी तरह समाप्त कर देने से काफ़ी समय बचता है—खासकर तब, जब Agent बग्स की जाँच कर रहा हो—और इससे इटरेशन कहीं अधिक प्रभावी हो जाता है।
Toggle the mode, then hover or tap a segment to inspect its duration.
आगे क्या आने वाला है, कौन जानता है! Agents को संदर्भ उपलब्ध कराने को लेकर कई रोमांचक प्रगतियाँ हो रही हैं, और इस क्षेत्र में बहुत से शोधकर्ता काम कर रहे हैं—जिनमें हमारी टीम भी शामिल है। हम अर्थगत इंडेक्स सहित मौजूदा तरीकों के प्रदर्शन को बेहतर बनाना जारी रखेंगे, और हमें उम्मीद है कि हम Agents के प्रदर्शन को और आगे बढ़ाने के बिल्कुल नए तरीके सामने लाएँगे, साथ ही हमेशा यह सुनिश्चित करेंगे कि वे वहाँ भरोसेमंद ढंग से काम कर सकें जहाँ उनकी सचमुच सबसे ज़्यादा ज़रूरत है: दुनिया की सबसे बड़ी रिपॉज़िटरी में, जहाँ एजेंटिक विकास का भविष्य वास्तव में गति पकड़ रहा है।
