आइसलैंडिक नामों के विभक्ति-पैटर्न को 3.27kB trie में संपीड़ित करना

 (alexharri.com)
2 पॉइंट द्वारा GN⁺ 2025-08-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • आइसलैंडिक व्यक्तिगत नामों की विभक्ति (डिक्लेंशन) हैंडलिंग संदर्भ के आधार पर चार अलग-अलग रूप लेती है
  • डेटा-आधारित JavaScript लाइब्रेरी के माध्यम से इनपुट किए गए नाम के लिए उपयुक्त व्याकरणिक केस लौटाने की सुविधा विकसित की गई
  • सभी नामों को सीधे स्टोर करने पर आकार बढ़ने और डेटा की कमी (missing data) की समस्या आती है, इसलिए trie संरचना और compression तकनीक का उपयोग कर इसे हल किया गया
  • trie compression की मदद से सामान्य पैटर्न-आधारित स्वचालित अनुमान संभव हुआ और कुल डेटा का 80% से अधिक कवर करने वाला बहुत छोटा डेटाबेस हासिल किया गया
  • सामान्य परिस्थितियों में 74% से अधिक सटीकता मिलती है, जबकि सार्वजनिक क्षेत्र और उच्च-सटीकता मामलों के लिए अलग strict संस्करण उपलब्ध है

समस्या की पृष्ठभूमि

  • आइसलैंडिक इंटरफ़ेस में व्यक्तिगत नाम दिखाते समय विभक्ति (declension) के कारण समस्या आती है
  • आइसलैंडिक नाम प्रथमा (nominative), कर्म (accusative), दत्तिव (dative), संबंध (genitive) सहित चार व्याकरणिक विभक्तियों के अनुसार अलग-अलग रूप लेते हैं
  • डेटाबेस में नाम आमतौर पर प्रथमा रूप में ही सेव होते हैं, इसलिए संदर्भ के अनुसार अलग केस की जरूरत होने पर कठिनाई होती है
  • गलत रूप उपयोग करने पर टेक्स्ट में ‘देशी/नेटिव’ जैसा प्राकृतिक एहसास नहीं मिलता और भाषा अटपटी लगती है

डेटा संग्रह और शुद्धिकरण

  • आइसलैंड में Árnastofnun द्वारा संचालित DIM (Database of Icelandic Morphology) डेटा सार्वजनिक किया गया
  • नामों के लिए विभक्ति डेटा को Kristín’s Format(K-format) CSV में प्रोसेस किया जा सकता है
  • DIM का पूरा डेटा 7 मिलियन पंक्तियों का है, जो बहुत बड़ा है; इसलिए केवल 4,500 आधिकारिक मान्य व्यक्तिगत नाम चुनकर करीब 3,600 नामों के लिए विभक्ति जानकारी प्राप्त की गई
  • प्रत्येक नाम के लिए प्रथमा से संबंध (genitive) तक के रूपों का ऐरे बनाया जा सकता है

लाइब्रेरी का मूल ढांचा

  • शुरुआत एक ऐसा applyCase फ़ंक्शन बनाकर की गई थी जो नाम और केस-वैरिएंट ऐरे से उपयुक्त रूप लौटाता था
  • लेकिन सरल ऐरे-लोडिंग तरीके में आकार (30kB gzipped) काफी बड़ा था
  • डेटासेट में मौजूद न होने वाले नामों के लिए कोई आउटपुट नहीं दे पाने की सीमा थी

डुप्लिकेट हटाना और पैटर्न निकालना

  • नाम के चार रूपों में मौजूद साझा उपसर्ग (common prefix) निकालकर प्रत्येक के लिए केवल suffix सेट (suffix encoding) संग्रहित किया गया ताकि दोहराव घटे
  • कई नामों में एक ही विभक्ति-पैटर्न का पालन होने का पता चला

पैटर्न मैचिंग के लिए trie का प्रयोग

  • trie संरचना (साफ़िक्स-आधारित उल्टा insertion) के जरिए समान पैटर्न साझा करने वाले नाम समूहों में मान-मैपिंग का ऑप्टिमाइज़ेशन किया गया
  • सामान्य नाम-अंत (name endings) के तहत विभक्ति जानकारी केवल एक बार स्टोर करके नए नामों पर भी उच्च अनुमान क्षमता मिलती है

trie compression और ऑप्टिमाइज़ेशन प्रक्रिया

  • जहाँ किसी subtree के प्रत्येक leaf का मान समान था, वहाँ वह मान parent नोड को दे दिया गया और बच्चों को हटाकर tree compress किया गया
  • इससे नोड की संख्या 15.4% तक घटी और आकार 4.01kB तक कम हुआ
  • सिब्लिंग leaf नोड्स जिनका मान समान था, उन्हें एक नोड में मर्ज करने वाली दूसरी compression से 3.27kB तक पहुँचा गया

trie परफॉरमेंस और जनरलाइजेशन

  • नए नाम इनपुट करने पर, समान पैटर्न-आधारित स्वचालित विभक्ति अनुमान संभव हो जाता है
  • वास्तविक अज्ञात नामों पर 74% सही विभक्ति और 26% गलत परिणाम आए; वास्तविक उपयोगकर्ता आधार पर त्रुटि दर केवल 0.34% रही
  • डेटा की regularity और comprehensiveness जितनी अधिक हो, compression तथा स्वचालित अनुमान की सटीकता में उसी अनुपात में सुधार होता है

वास्तविक लाइब्रेरी और अपनाना

  • अंतिम रूप से compressed trie इस्तेमाल करने वाली beygla लाइब्रेरी जारी की गई
  • न्यूनतम आकार (4.46kB) और अधिक कठोर, पूर्णतः सही strict मॉड्यूल (15kB) के साथ उपलब्ध कराया गया
  • जहाँ 100% accuracy जरूरी है (जैसे सार्वजनिक दस्तावेज़), वहाँ strict संस्करण, जबकि सामान्य वेब ऐप्स के लिए हल्का संस्करण चुना जा सकता है

निष्कर्ष और स्केलेबिलिटी

  • trie-आधारित भाषायी विभक्ति-पैटर्न डेटा compression सिर्फ आइसलैंडिक ही नहीं, अन्य विभक्ति-प्रधान भाषाओं के नाम, पते और अन्य संज्ञाओं के स्वचालित प्रोसेसिंग में भी लागू की जा सकती है
  • अत्यधिक नियमित डेटा और trie compression का संयोजन रूपांतरण/विभक्ति-प्रोसेसिंग के स्वचालन में डेटा और परफॉरमेंस दोनों की बेहतर दक्षता देता है

संदर्भ/आभार

  • beygla के निर्माण में कई विशेषज्ञ फीडबैक और अतिरिक्त ऑप्टिमाइज़ेशन किए गए
  • trie की अतिरिक्त compression से आकार 3.43kB से 3.27kB तक घटाया गया

सारांश

  • आइसलैंडिक नाम विभक्ति स्वतःकरण को पैटर्न-आधारित trie डेटा संरचना से छोटा और स्वचालित बनाने का उदाहरण प्रस्तुत किया गया है
  • सही आकार-और-सटीकता के trade-off को ध्यान में रखते हुए व्यावहारिक डेटा हैंडलिंग रणनीति के लिए यह एक मजबूत संकेत देता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-08-04
Hacker News राय

  • जब मैंने हाई स्कूल में पहली बार स्पैनिश सीखी थी, तब मैं Windows सॉफ़्टवेयर इस्तेमाल करता था जिसमें infinitive verbs और tenses लगातार आते थे, और मुझे उनके मुताबिक verb forms भरने होते थे। इस तरह की ट्रेनिंग से grammar rules मेरे भीतर अच्छी तरह बैठ गए और मैं काफ़ी निपुण हो गया। लेकिन जब मैंने Russian सीखी, तो case inflection अचानक बहुत कठिन लगा, और ऐसा कोई app नहीं मिला जो इसी तरह के patterns को समझाए या practice कराए। अगर किसी को इस काम के लिए कोई app (web या macOS/iOS) पता हो, तो जानना चाहूँगा

    • Anki में "KOFI(Konjugation First)" नाम की विधि इस्तेमाल करने वाला एक flashcard deck है। KOFI का मतलब है कि language learning शुरू करने से पहले सभी conjugation patterns पहले सीख लिए जाएँ। French पढ़ने के बाद मुझे लगा कि मेरी conjugation skill कमज़ोर है, इसलिए बाद में मैंने यह तरीका आज़माया। grammar की गलतियों के साथ बोलने पर भी रोज़मर्रा की communication में दिक्कत नहीं होती, लेकिन मैं जिस स्तर तक पहुँचना चाहता था, वह नहीं था। इस तरीके का लक्ष्य है कि भाषा सीखने से पहले कम समय में सभी conjugation patterns सीख लिए जाएँ। कभी किसी नई भाषा पर इसे गंभीरता से लागू करना चाहूँगा। French में मेरी दिलचस्पी कम हो गई, इसलिए बीच में छोड़ दिया। संबंधित Anki deck लिंक

    • Russian सीखते समय मैंने spaCy Python module और Russian के बड़े module को जोड़कर एक script बनाई थी, जो context-based lemmatization और grammar tag extraction करती थी। लेकिन जब मेरी Russian वास्तव में बेहतर होने लगी, तब inflections को तार्किक रूप से तोड़कर समझने की कोशिश छोड़ना, और usage experience तथा repetition के ज़रिए दिमाग़ में patterns (exceptions सहित) की library बनाना, कहीं ज़्यादा प्रभावी साबित हुआ। यहाँ context से मतलब वाक्य के भीतर का अर्थ है

    • 25 साल पहले जब मैं खुद से Spanish सीख रहा था, तब मैंने एक Spanish/English dictionary इस्तेमाल की थी। infinitive verbs के साथ number index दिया जाता था, जिससे उन्हें समान conjugation pattern वाले समूहों में रखा गया था। dictionary के शुरुआती हिस्से में हर group के प्रतिनिधि verb की सभी tenses की conjugation table थी। irregular verbs के लिए अलग index था, और वैसे ही मिलते-जुलते irregular verbs को एक ही group में रखा गया था (उदाहरण: tener, detener)। सारे verbs कुछ दर्जन unique patterns में साफ़-सुथरे ढंग से व्यवस्थित थे। मैंने सोचा भी था कि इस system का इस्तेमाल करके quiz software बनाऊँ, लेकिन बना नहीं पाया। सोच रहा हूँ कि लेख में बताए गए reverse-string trie pattern का इस्तेमाल इस तरह की classification में भी हो सकता है या नहीं

    • Russian के case inflection याद करने के लिए मेरे मन में यह विचार था कि preposition+adjective+noun combinations वाले flashcards बनाकर memorization speed बढ़ाई जाए। मैंने पहले Latin सीखी थी, लेकिन Latin declension को जल्दी याद कर लेने की उम्मीद नहीं थी (शायद अगर कोई monk हो तो अलग बात है?), जबकि Russian मैं जल्दी सीखना चाहता था। लेकिन यह अंततः किसी project में नहीं बदल पाया

    • Spanish conjugation practice के लिए मैं iOS पर ConjuGato इस्तेमाल कर रहा हूँ। game mode में infinitive verb/tense/person दिया जाता है और आपको उसका conjugated form याद करना होता है। irregular verbs को अलग से practice किया जा सकता है, इसलिए exceptions सीखने में यह काफ़ी प्रभावी है

  • database में जिन 800 names के case inflection data missing हैं, उनके लिए manually declension देना सबसे सीधा समाधान लगता है। अगर कोई native speaker हो, तो वह इसे कुछ घंटों में पूरा कर सकता है, और पूरी तरह अनजान names के लिए भी कम से कम ऐसा रूप अनुमानित कर सकता है जो साफ़ तौर पर अटपटा न लगे। या फिर LLM से भी यह बहुत सस्ते में कराया जा सकता है। result को इस तरह की trie structure में encode करके distribute करना अब भी अच्छा विचार है। बस trie को declension predictor तक बनाना ज़रूरी नहीं है

    • और ज़्यादा names को कवर करना बेहतर होगा—DIM में यह लगातार सुधार की ज़रूरत वाला हिस्सा है। Iceland में approved names list में नए names अक्सर जोड़े जाते हैं, इसलिए gaps बने रहना लगभग तय है। मुझे खुद data जोड़ने को लेकर पर्याप्त भरोसा नहीं है, और 100 unverified names के results देखते समय कई बार लगा, “क्या यह सही है?” DIM में मिलते-जुलते names देखकर भी मैंने कई बार सोचा, “मैं इसे इस तरह decline नहीं करता।” इसलिए मैं DIM data को language experts द्वारा maintained ‘source of truth’ मानता हूँ

    • manual work अच्छा है, लेकिन official list में न होने वाले names (जैसे foreign names) के लिए इसकी सीमा बनी रहती है। मैं भी ऐसे देश में रहता हूँ जहाँ centralized name list है, लेकिन exceptions का अनुरोध किया जा सकता है, और list बनने से पहले पैदा हुए लोग या immigrants जैसे मामलों में नाम list में नहीं भी हो सकते हैं। ऐसे कई मिश्रित हालात में ‘लगभग सही declension prediction’ feature अब भी उपयोगी है

    • मुझे ऐसा कोई प्रमाण नहीं मिला कि LLM, trie से बेहतर declension prediction करता है (अगर वास्तविक example LLM के training data में न हो, तो web search शायद बेहतर होगा)

    • इससे यह जिज्ञासा भी होती है कि क्या मौजूदा LLMs पहले से ऐसे patterns सीख चुके हैं

  • यक़ीन नहीं कि Rails यह समस्या अपने आप संभालता है या नहीं, लेकिन पहले यह इस तरह का जादू खूब करता था। मैंने पहले pluralise का source code देखा था, और उसमें Welsh की irregular plural rules तक encode थीं

    • Rails वाकई बहुत अच्छा है, क्योंकि लगभग हर काम के लिए कोई न कोई method पहले से मौजूद होता है

  • एक optimization idea यह है कि trie सीधे suffix strings पर map करने के बजाय, unique suffixes का एक array बनाया जाए और trie उसमें index के ज़रिए पहुँचे। उदाहरण के लिए:

    const suffixes = [",,,", "a,u,u,u", ",,i,s", ",,,s", "i,a,a,a", ...];

    और फिर index को इस तरह refer किया जाए:

    var serializedInput = "{e:{n:{ein:0_r: ..."

    • Claude Code से खुद आज़माकर देखा तो gzip के बाद उल्टा 100 bytes बढ़ गए (3456 -> 3556), और केवल uncompressed size ही 20% कम हुई। शायद इसलिए कि gzip खुद ही repeated patterns के लिए पहले से काफ़ी अच्छी तरह optimized है

    • एक कदम आगे बढ़कर suffixes को खुद trie में डालना, और identical subtrees को पहचानकर deduplicate करना भी संभव हो सकता है। अगर gzip इस्तेमाल किया जा सकता है, तो suffix array का उपयोग करके कोई और smart optimization ज़रूर हो सकती है। binary optimized format इस्तेमाल करें तो और बेहतर हो सकता है

  • मुझे बार-बार लगता है कि शायद uncompressed अवस्था में इसे <1kb में करने का कोई जादुई तरीका हो। 100% accuracy के साथ names को classify करने वाली minimized regular expression list? बहुत बड़ा bloom filter? या सामान्य hash की जगह specialized features का उपयोग?

  • यह किसी nightmare interview problem जैसा लगता है। reverse trie का उपयोग ज़िंदगी में शायद सिर्फ एक बार काम आए, लेकिन अगर उस एक बार आपने इसे इस्तेमाल कर लिया, तो लोग आपको जादूगर कहेंगे

    • इसे reverse trie कहना उतना सही नहीं लगता, बल्कि यह कहना ज़्यादा सही होगा कि names को उल्टा डाल दिया गया है

  • इसे JS में करने के बजाय, database से सभी name-case combinations लौटवाकर, display के समय केवल ज़रूरी वाला चुना जा सकता है। यानी localization layer में इसका समाधान। cross-language situations में यह कैसे काम करेगा, यह जानने की उत्सुकता है। Icelandic UI अगर French name संभाल रहा हो, तो शायद हमेशा nominative ही इस्तेमाल करेगा, और English UI अगर Icelandic name संभाल रहा हो, तब भी शायद यही होगा। आखिरकार इसकी ज़रूरत मुख्यतः user को सीधे संबोधित करने वाले context या admin panel जैसी जगहों पर ही ज़्यादा होगी ("user x ने user y को reply किया")

  • “idur”, “tur”, “ður” पर खत्म होने वाले एक विशेष declension pattern के 88 names हैं, लेकिन एक ही suffix हमेशा उसी declension pattern का पालन नहीं करता। समस्या ऊपर से simple rule जैसी लगती है, लेकिन वास्तव में बहुत रोचक है। क्या suffix pattern उससे ठीक पहले वाले syllable के pronunciation से जुड़ा हो सकता है? अगर unknown names को बेहतर handle करना हो, तो क्या केवल letters के बजाय name का pronunciation representation NLP से निकालकर trie आदि में lookup करना चाहिए?

    • इस तरह सोचते-सोचते Dependent Types वाली चर्चा में पहुँच जाने से सावधान रहना चाहिए

    • यह काफ़ी पैनी insight है। वास्तव में एक ही pronunciation वाले names के declension patterns अलग हो सकते हैं। उदाहरण के लिए:

      • Ástvaldur -> ur,,i,ar
      • Baldur -> ur,ur,ri,urs “aldur” पर खत्म होने वाले ये दोनों names एक जैसे उच्चरित होते हैं, लेकिन declension patterns अलग हैं। अगर “Ástvaldur” का pattern “Baldur” पर लगा दिया जाए, तो आख़िरी तीन forms सचमुच बहुत अटपटे लगते हैं (मैंने अपने Icelandic partner से वास्तव में पूछकर देखा)। Icelandic में spelling और pronunciation लगभग मेल खाते हैं, इसलिए pronunciation-based trie इस्तेमाल करने पर भी शायद बहुत बड़ा फ़र्क़ नहीं पड़ेगा

  • beygla/strict स्थिति में perfect hashing को एक विकल्प के रूप में सोचा जा सकता है

    • जहाँ सभी values unique नहीं हैं, वहाँ सामान्य perfect hashing से भी ज़्यादा compression संभव हो सकता है। एक hash bucket में कई name->suffix pairs डाले जा सकते हैं। हालाँकि इस स्थिति में “unhandleable name” की पहचान करने की क्षमता खत्म हो जाएगी

  • यह देखकर हैरानी होती है कि Icelandic name declension इतने deterministic patterns रखता है कि यह तरीका अच्छी तरह काम कर जाता है। भाषाएँ आम तौर पर काफ़ी जटिल होती हैं

    • शायद इसमें Iceland की छोटी आबादी और यह तथ्य असर डालते हैं कि वहाँ भाषा का सक्रिय रूप से राज्य-स्तर पर प्रबंधन किया जाता है