3GB SQLite डेटाबेस को 10MB FST (finite-state transducer) बाइनरी से बदलना

• Taskusanakirja एक Finnish-English डिक्शनरी है जो टाइप करते समय prefix search देती है
• Finnish inflection expansion के कारण एंट्रियों की संख्या 4 करोड़~6 करोड़ तक बढ़ गई, जिससे trie अपनी सीमा तक पहुँच गया
• अस्थायी SQLite FTS समाधान तेज़ था, लेकिन शुरुआती 3GB डाउनलोड ज़रूरी था
• Rust-आधारित FST ने SQLite डेटा को घटाकर लगभग 10MB बाइनरी बना दिया, यानी 300 गुना कमी
• FST prefix के साथ suffix भी साझा करता है, इसलिए यह दोहराए जाने वाले inflection patterns पर अच्छी तरह फिट बैठता है

---

Taskusanakirja की search संरचना और शुरुआती सीमाएँ

• Taskusanakirja, संक्षेप में tsk, एक Finnish-English डिक्शनरी है, और टाइप करते समय incremental search की सुविधा देती है
• यह मूल रूप से prefix search की समस्या है, और autocomplete के लिए prefix search का पारंपरिक समाधान trie implementation था
• पहली implementation Go में लिखी गई थी, और शुरुआती design goal यह था कि पूरे प्रोग्राम को एक .exe, एक .app, या एक statically linked बाइनरी के रूप में distribute किया जाए
• बीच के 6-digit scale वाले शब्द-संग्रह में single-digit percentage के बराबर आने वाली सभी entries को match न करने के लिए, यह केवल शुरुआती 50 या 100 results लौटाता था और 1·2·3-अक्षर combinations को memoize करता था
• इस तरीके से लगभग 60MB जगह में basic optimizations के साथ एक trie रखा जा सका, और एक साल तक निजी उपयोग में भी कोई महसूस होने वाली latency नहीं थी

Finnish inflection data से पैदा हुई scale की समस्या

• Finnish एक agglutinative language है, इसलिए एक मूल शब्द में सभी combinations गिने जाएँ तो 100 से ज़्यादा endings हो सकती हैं
• ये combinations नियमित नहीं हैं, और Finnish की बहुत नियमित orthography बोलचाल के वास्तविक रूपों को सीधे लिखित रूप में दिखाती है, इसलिए मूल शब्द endings के साथ जुड़ते हुए फैलते, खिसकते और बदलते रहते हैं
• शुरुआती learners को “Opiskelijassammekin on leijonan sydän” जैसे वाक्य में किसी खास शब्द पर अटकना आसान है, और tsk में यह जानकारी भी रखने की कोशिश थी कि शब्द को सही boundaries पर कैसे तोड़ा जाए
• भाषाविज्ञान की दृष्टि से, ऐसे बदलाव consonant gradation और vowel harmony से जुड़े हैं, और Finnish दोनों का एक साथ उपयोग करती है
• उदाहरण के लिए katu का अर्थ “street” है, लेकिन उसका genitive katun नहीं बल्कि kadun होता है, क्योंकि closed syllable की वजह से t, d में कमजोर हो जाता है
• जब इस संरचना को 15 cases, 2 plurals, 6 possessive suffixes और अनिश्चित संख्या के clitics से गुणा किया जाता है, तो साधारण trie -ssa-mme-kin जैसे उन endings की लागत साझा नहीं कर पाता जिन्हें हज़ारों शब्द share करते हैं
• लगभग 4 लाख entries को trie में करीब 50MB RAM पर रखा जा सकता था, लेकिन यही तरीका 4 करोड़~6 करोड़ entries तक scale नहीं हुआ
• अस्थायी समाधान के रूप में inflected forms को अलग SQLite FTS डेटाबेस में रखा गया और ज़रूरत पड़ने पर search किया गया; यह बिना महसूस होने वाली latency के काम करता था, लेकिन शुरुआती एक बार का 3GB डाउनलोड ज़रूरी था

Rust और FST पर स्विच करने का नतीजा

• 9 महीने बाद Rust में दोबारा कोशिश करते हुए, 3GB SQLite डेटाबेस से डेटा निकालकर उसे FST में compress करने वाला एक minimal Rust प्रोग्राम लिखा गया
• प्रेरणा BurntSushi aka Andrew Gallant की पोस्ट Index 1,600,000,000 Keys with Automata and Rust से मिली, जिसका मुख्य बिंदु यह था कि finite-state machines strings के sorted set या map को छोटे और तेज़ रूप में व्यक्त कर सकती हैं
• नतीजे में बनी बाइनरी लगभग 10MB की थी, जो 3GB SQLite डेटाबेस की तुलना में लगभग 300 गुना कम जगह लेती है
• यह उपयोग fst crate के लिए भी खास तौर पर अच्छा फिट था, क्योंकि समस्या highly agglutinative भाषा के inflected और conjugated forms को उनकी मूल definitions से map करने की थी
• trie prefixes को compress करता है, लेकिन FST prefix और suffix दोनों को compress करता है
• Finnish dictionary corpus में बहुत बार दोहराए जाने वाले कुछ लोकप्रिय suffixes मौजूद हैं, इसलिए suffix sharing का बड़ा असर पड़ता है
• डेटा रनटाइम के दौरान बदलता नहीं है, यानी यह static data है, इसलिए fst की सबसे बड़ी कमजोरी से बचा जा सका

FST trie से छोटा क्यों निकला

• प्राकृतिक भाषा डेटा में FST को trie से बहुत छोटा बनाने वाला मुख्य कारण suffix sharing है
• trie में kadun और kaduille जैसे शब्द आगे के तीन nodes share करते हैं, यानी prefix share होता है, लेकिन अलग suffix paths अलग-अलग store किए जाते हैं
• minimal acyclic deterministic finite-state automaton संरचनात्मक रूप से समान दो subtrees को merge कर देता है
• ऐसे corpus में जहाँ 1 लाख शब्द लगभग 12 समान inflection patterns पर खत्म होते हैं, यह merging बड़ी memory savings देती है
• इस मामले की मुख्य heuristic यह है कि मौके पर बनाए गए एक general-purpose डेटाबेस को हटाकर, ठीक वही काम करने वाली एक छोटी, static, specialized data structure लगाई जाए और 300 गुना memory reduction हासिल की जाए

अस्थायी SQLite समाधान की बची हुई भूमिका और distribution size

• 9 महीने पहले SQLite चुनना “अच्छी चीज़ न कर पाना” की बजाय “खराब लेकिन आसान” विकल्प लेने जैसा था, और यह वास्तव में काम कर गया
• SQLite के B-tree और Full Text Search extension की समझ होने के कारण, उस समय यह जल्दी experiment करने लायक समाधान था
• वही FTS extension tsk v2.0.0 alpha में मौजूद नहीं रहने वाली कुछ कम इस्तेमाल होने वाली features के लिए भी इस्तेमाल हुई, लेकिन अगर वह मौजूदा memory footprint को नुकसान पहुँचाती है तो उसे पूरी तरह हटाया भी जा सकता है
• v2 का Pro version सब कुछ मिलाकर लगभग 20MB का लक्ष्य रख रहा है, जो v1 के free version से 3 गुना छोटा है
• tsk की शुरुआत मूल रूप से एक TUI Go प्रोग्राम के रूप में हुई थी, और यह पहले के fzf-आधारित prototype finstem से विकसित हुआ, साथ ही the highest-ROI program I’ve written so far से जुड़ता है
• taskusanakirja का Finnish में अर्थ “pocket dictionary” है, और मानक यह बना रहा कि अगर वह पुराने laptop में भी फिट न हो, तो वह pocket dictionary नहीं बल्कि compile होने वाली पुरानी Oxford dictionary जैसा कुछ है
• “समस्या को दो बार हल करना ठीक है” जैसी एक बार-बार लौटने वाली सोच यहाँ दिखती है: बेहतर मौजूदा implementation न खोज पाने के अपराधबोध में रुकने की बजाय, कुछ wheels खुद दोबारा बनाना असली सीमाओं तक जल्दी पहुँचने में मदद कर सकता है
• यह नज़रिया Caplanian view के “practice” से जुड़ता है, और Do Ten Times as Much को असुविधाजनक लेकिन काम करने वाली सलाह के रूप में पेश किया गया है

[GN⁺]

Lobste.rs की राय

• लेख खुद भी दिलचस्प था, और यह देखना अच्छा लगा कि सही tool को सही काम पर लगाकर single-digit स्तर का सुधार हासिल किया गया, लेकिन मुख्य लेख से भी ज़्यादा आख़िरी footnote ने प्रभावित किया।
  यह उस दुविधा को बिल्कुल सटीक पकड़ता है जिसमें हम इस अपराधबोध से रुक जाते हैं कि जो tool हम अभी बना रहे हैं, शायद उसे 30~40 साल पहले कोई और हमसे बेहतर बना चुका होगा। लेकिन वही एक जाल है, और यह बात असरदार लगी कि पहिया बनाने की सीमाओं तक पहुँचने के लिए कुछ पहिए दोबारा बनाने पड़ते हैं। ज़्यादातर क्षेत्रों में चार-पाँच काफ़ी होते हैं, और गणित या computer science जैसे कठोर क्षेत्रों में भी शायद बीस-तेइस तक ही बात हो; और इस तरह खुद दोबारा बनाते हुए जो सवाल उठते हैं, वे साधारण पढ़ाई की तुलना में कहीं तेज़ी से आपको असली frontier तक ले जाते हैं

  • मुख्य लेख का एक अहम संबंधित बिंदु यह भी था कि SQLite DB से बना अक्षम brute-force implementation भी एक baseline implementation के रूप में मूल्यवान था।
    पहले से एक ऐसा reference implementation था जो काम करता था, इसलिए उसे बदलने वाला efficient implementation बनाना आसान हो गया
  • यह मेरी मौजूदा समस्या से बिल्कुल मेल खाता है। मैं अपने problem space के लिए optimized कुछ बनाना चाहता था, लेकिन यह जानकर रुका हुआ था कि generalized problem तो पहले ही हल हो चुकी है।
    लेकिन मौजूदा solutions को देखता हूँ तो उनमें बहुत-सा ऐसा बोझ जुड़ा है जिसकी मुझे ज़रूरत नहीं। अनुभव से जानता हूँ कि अपने idea को आगे बढ़ाने की क़ीमत है, फिर भी लगातार लगता रहा कि कहीं मैं कुछ मिस तो नहीं कर रहा। यह पढ़कर अब सोचा है कि बस करके देखता हूँ। असफल हुआ तो भी उस प्रक्रिया में कुछ सीखने को मिलेगा

• बहुत शानदार। Compressing Icelandic name declension patterns into a 3.27 kB trie याद आ गया

• Scrabble bot बनाते समय मुझे DAWG(Directed Acyclic Word Graph) नाम की एक संबंधित data structure के बारे में पता चला, और उस काम के लिए यह काफ़ी आम लगती है।
  fst crate से मुख्य अंतर यह दिखता है कि यह हर शब्द को किसी unique integer से map नहीं करता। इसी तरह size बहुत कम हो गया और performance भी जबरदस्त बेहतर हुई। Scrabble bot को मूल रूप से ..cat.. जैसे simple regex से मेल खाने वाले शब्दों के लिए पूरी dictionary को filter करना पड़ता है, लेकिन असल में उसे मौजूदा board पर संभव सभी simple regex संभालने होते हैं। जो काम पहले लगभग 1 मिनट लेता था, वह घटकर महसूस न होने वाली latency तक आ गया

  • Appel और Jacobson का 1988 का DAWG paper कुछ समय पहले भी पोस्ट हुआ था और उससे पहले भी साझा किया जा चुका है

• लिंक किया गया लेख भी पढ़ने लायक है: https://burntsushi.net/transducers/

• fst आखिरकार srgn के German support में भी इस्तेमाल होने वाला tool बना, और वह भी Andrew की सीधी सिफारिश के बाद।
  यह वही problem space है जहाँ common prefixes और suffixes को compress किया जाता है, और यह सचमुच बहुत अच्छा काम करता है। साथ ही, यह एक CLI tool था इसलिए startup cost को न्यूनतम रखना भी ज़रूरी था, और fst crate zero-copy loading सपोर्ट करता है, इसलिए runtime overhead नहीं होता। FST compile time पर बनाया जाता है

• वाकई शानदार, और काश German और English के लिए भी ऐसा कुछ हो। German compound words अब भी मुझे अक्सर उलझा देते हैं