ग्रंथों का स्वत: विश्लेषण लगभग हमेशा शब्दकोशों के साथ काम से जुड़ा हुआ है। उनका उपयोग रूपात्मक विश्लेषण, व्यक्तियों के आवंटन (व्यक्तिगत नामों और उपनामों के शब्दकोश) और संगठनों के साथ-साथ अन्य वस्तुओं के लिए किया जाता है।

सामान्य तौर पर, एक शब्दकोश फॉर्म {स्ट्रिंग, इस स्ट्रिंग से जुड़े डेटा} के रिकॉर्ड का एक सेट है।

उदाहरण के लिए, रूपात्मक विश्लेषण के लिए, शब्दकोश में त्रिगुण {शब्द रूप, सामान्य रूप, रूपात्मक विशेषताएं} शामिल हैं। "माँ साबुन फ्रेम" वाक्य से "साबुन" शब्द का विश्लेषण करते समय आपको निम्नलिखित विश्लेषण विकल्प प्राप्त करने में सक्षम होना चाहिए:

सामान्य रूप	की विशेषताओं
सोप	एस (संज्ञा), लिंग (आनुवांशिक), ईडी (एकवचन), मेडम (नपुंसक), NEOD (Inanimateness)
सोप	एस (संज्ञा), एमआई (नाममात्र का मामला), एमएन (बहुवचन), मेडम (नपुंसक), एनईओडी (विसंगत)
सोप	S (संज्ञा), VIN (अभियोगात्मक मामला), MN (बहुवचन), MEDIUM (नपुंसक), NEOD (निर्जीव)
वाश	V (क्रिया), PASS (भूत काल), ED (एकवचन), FLASH (सांकेतिक), WIFE (स्त्रीलिंग), NESOV (अपूर्ण रूप)

हैश टेबल

पहली नज़र में, सब कुछ सरल है। आपको एक हैश तालिका का उपयोग करना चाहिए और अंत से निपटना चाहिए। जब शब्दकोश छोटा होता है तो यह समाधान बहुत सरल और प्रभावी होता है।

हालांकि, उदाहरण के लिए, रूसी भाषा के रूपात्मक शब्दकोष में लगभग 5 मिलियन शब्द हैं। यह पता चला है कि:

इन 5 मिलियन शब्द रूपों को संग्रहीत करना आवश्यक है
प्रत्येक शब्द रूप के लिए, रूपात्मक विशेषताओं के कई सेटों का लिंक होना चाहिए
प्रत्येक शब्द रूप के लिए, इसके प्रारंभिक रूप को संग्रहीत करें

डेटा को व्यवस्थित करने का यह तरीका एक प्रकार का है, क्योंकि सबसे पहले, शब्द नियमित रूप से झुके रहते हैं, और दूसरी बात यह है कि रूसी भाषा के मामले में, शब्द रूपों के उपसमूह को एक शब्दकोश प्रविष्टि के भीतर अलग किया जा सकता है, जिसमें रूप थोड़ा बदल जाता है या बिल्कुल भी नहीं बदलता है। ।

उदाहरण के लिए, शब्द "दीवार":

यू एच: "दीवारें" [उन्हें], "दीवारें" [जीनस], "दीवारें ई " [दिनांक], "दीवारें यू " [मदिरा], "दीवारें ओई " [प्राणी], "दीवारें ओई " [जीव], "वॉल्स ई " [प्रील];
pl। h: "दीवारों s " [im], "दीवारों" [जीनस], "दीवारों हूँ " [दिनांक], "दीवारों s " [मदिरा], "दीवारों ami " [प्राणी], "दीवारों आह " [वाक्य]।

यह देखा जा सकता है कि केवल अंत में परिवर्तन होता है, लेकिन पूरे शब्द को हैश तालिका में संग्रहीत किया जाना चाहिए।

आप मूल रूप से मूल (अपरिवर्तित भागों) और समाप्ति को संग्रहीत कर सकते हैं, लेकिन इस मामले में, शब्द को सत्यापित करना जटिल है।

उपसर्ग वृक्ष से राज्य मशीनों तक

उदाहरणों की स्पष्टता के लिए, हम एक सरल समस्या पर विचार करेंगे, जब विश्लेषण में प्रत्येक शब्द के लिए केवल अपनी रूपात्मक विशेषताओं को प्राप्त करना आवश्यक है। सामान्य रूप को कैसे रखा जाए, इसका वर्णन अंत में किया जाएगा।

हैश तालिकाओं की तुलना में, एक अधिक कॉम्पैक्ट प्रतिनिधित्व उपसर्ग वृक्ष (ट्राइ) है:

एक महत्वपूर्ण नोट - पेड़ के प्रत्येक पत्ती नोड (या राज्य मशीन की स्थिति) से जुड़ी सुविधाओं के सेट को आंकड़ों में नहीं दिखाया जाएगा। उदाहरण के लिए, आकृति में, नोड 6, जहां हम लाइन "दीवारों" के साथ मिलते हैं, वास्तव में 3 पर्स होंगे:

एकवचन, जनन;
बहुवचन, नाममात्र;
बहुवचन आरोपण।

उपसर्ग वृक्ष को एक परिमित राज्य मशीन माना जा सकता है।

मशीन में तीन प्रकार के राज्य होते हैं:

प्रारंभिक - जो काम मशीन के साथ शुरू होता है। एक नियतात्मक automaton में, ऐसा राज्य एक है, लेकिन गैर-नियतात्मक automaton में कई हो सकते हैं। आंकड़ों में, यह 0 नंबर के साथ सबसे बाईं ओर की स्थिति है।
अंतिम - ऐसे राज्य, जिसकी उपलब्धि का मतलब है कि ऐसा शब्द शब्दकोश में है। वे एक डबल सर्कल द्वारा इंगित किए जाते हैं।
सरल अवस्थाएं जो न तो प्रारंभिक हैं और न ही अंतिम हैं

भविष्य में, निम्नलिखित संकेतन का उपयोग किया जाएगा:

स्ट्रिंग w द्वारा चिह्नित है
w [i] इस शब्द का i-th अक्षर है (0 से शुरू)।
s [i] ट्री (या ऑटोमेटन का राज्य) का i-th नोड है, राज्यों को गैर-नकारात्मक पूर्णांक द्वारा क्रमांकित किया जाता है, हम यह भी मानते हैं कि s [0] प्रारंभिक अवस्था है।
s [i] [j] - प्रतीक j द्वारा राज्य s [i] से संक्रमण। हम मानते हैं कि यदि कोई परिवर्तन होता है, तो ऐसी अभिव्यक्ति राज्य संख्या वापस कर देगी; यदि नहीं, तो यह -1 वापस आ जाएगी।

मैं उपसर्ग पेड़ / राज्य मशीन के लिए बुनियादी एल्गोरिदम दूंगा:

//      //    ()  int[] prefix(w) { int[] stateList; //         stateList[0] = 0; int current = 0; for(int i = 0; i < length(w); i++) { int next = s[current][w[i]] //   ,   if(next == -1) break; stateList[i+1] = next; } return stateList; } //      //      stateList void addSuffix(w, int[] stateList) { //        int current = stateList[length(stateList) - 1]; for(int i = length(stateList) - 1; i < length(w); i++) { //      int newState = addState(); //    s[current][w[i]] = newState; current = newState; //      stateList[i + 1] = current; } //     s[current] setFinal(current); } //     trie void add(w) { //     int[] prefixStates = prefix(w); //      addSuffix(w, prefixStates) }

परिमित राज्य मशीन के रूप में एक उपसर्ग वृक्ष के प्रतिनिधित्व में महत्वपूर्ण गुण हैं:

इस तरह के एक ऑटोमेटन का निर्धारण किया जाता है - प्रत्येक राज्य से एक निश्चित प्रतीक द्वारा एक से अधिक संक्रमण संभव नहीं है
इसमें कोई चक्र नहीं हैं - ऑटोमेटन को बायपास करने की किसी भी विधि के साथ, किसी भी राज्य का एक से अधिक बार दौरा नहीं किया जाता है।

इस तरह के एक विशेष ऑटोमेटन को DAFSA (नियतात्मक एसाइक्लिक परिमित राज्य ऑटोमेटन) कहा जाता है।

बनाने के लिए एक महत्वपूर्ण बिंदु। प्रस्तुति की सुविधा के लिए और व्यावहारिक उपयोग के लिए, हम मानते हैं कि राज्य को न केवल संक्रमण तालिका द्वारा वर्णित किया गया है, बल्कि अंतिम स्थिति पर डेटा द्वारा भी वर्णित किया गया है। और हम विचार करेंगे कि राज्य अंतिम है, अगर इसमें ऐसा डेटा है, और नहीं तो यह अनुपस्थित है।

न्यूनतम राज्य मशीनें

उपसर्ग पेड़ों का उपयोग उपसर्गों की अतिरेक को समाप्त करता है। वास्तव में, इसका मतलब है कि शब्द के अपरिवर्तित हिस्से के लिए भंडारण स्थान कम हो गया है। हालांकि, उदाहरण के लिए, रूसी में, शब्द अंत ज्यादातर नियमित रूप से बदलते हैं।

उदाहरण के लिए, शब्द "तीर" और "दीवार" एक ही तरह से बदलते हैं:

दीवार: इकाइयों एच: "दीवार" [उन्हें], "दीवार" [जीनस], "दीवार" [दिनांक], "दीवार" [मदिरा], "दीवार" [प्राणी], "दीवार" [प्राणी], "दीवार" [प्रस्ताव] ; pl। h: "दीवारों" [उन्हें], "दीवारों" [जीनस], "दीवारों" [दिनांक], "दीवारों" [मदिरा], "दीवारों" [प्राणी], "दीवारों" [प्रस्ताव]।

तीर: इकाइयों एच: "तीर" [उन्हें], "तीर" [जीनस], "तीर" [दिनांक], "तीर" [मदिरा], "तीर" [जीव], "तीर" [प्राणी], "तीर" [प्रस्ताव] ; pl। h: "तीर" [उन्हें], "तीर" [जीनस], "तीर" [दिनांक], "तीर" [मदिरा], "तीर" [जीव], "तीर" [पूर्व]।

यह देखा जा सकता है कि 4 और 17 राज्यों, जिसके साथ अंत शुरू होता है, दोनों शब्दों के लिए बराबर हैं। जाहिर है, शब्दकोश में समान विभक्ति नियमों के साथ कई शब्द होंगे। तो, आप राज्यों की संख्या को काफी कम कर सकते हैं।

दरअसल, ऑटोमेटा के सिद्धांत में एक न्यूनतम ऑटोमेटन की एक अवधारणा है - ऐसे ऑटोमेटन जिसमें राज्यों की न्यूनतम संभव संख्या शामिल है, लेकिन यह इसके बराबर होगा।

उदाहरण के लिए, उपरोक्त मशीन के लिए, न्यूनतम इस तरह दिखता है:

परिमित राज्य मशीनों को कम करने के लिए एल्गोरिदम हैं, लेकिन उन सभी में एक महत्वपूर्ण कमी है - उनके काम के लिए, आपको पहले एक गैर-न्यूनतम ऑटोमेटन का निर्माण करना होगा।

एक और, कम स्पष्ट दोष यह है कि निर्मित न्यूनतम ऑटोमेटन को बदलना इतना आसान नहीं है। यह एक नया शब्द जोड़ने की सरल प्रक्रिया में फिट नहीं होता है, जिसका उपयोग उपसर्ग वृक्ष के लिए किया जाता है।

उदाहरण के लिए, हमने "लोमड़ी" और "बॉक्स" शब्दों के लिए एक ऑटोमेटन बनाया, और फिर हमने इसे छोटा कर दिया।

यदि शब्द "लोमड़ियों" को पूर्ण पुनर्निर्माण के बिना इस मशीन में जोड़ा जाता है, तो हमें निम्नलिखित चित्र मिलता है:

यह पता चला है कि "लोमड़ियों" के साथ जगह में और "बक्से" को जोड़ा गया था, जिसे हमने नहीं जोड़ा था।

नतीजतन, शास्त्रीय न्यूनता एल्गोरिदम का उपयोग करने की योजना इस प्रकार है: शब्दकोश में किसी भी बदलाव के लिए, यह आवश्यक है:

एक उपसर्ग ट्री बनाएँ (या वैकल्पिक रूप से स्टोर करें)
मशीन को छोटा करें

यदि शब्दकोश बड़ा है, तो ये प्रक्रियाएँ काफी समय और स्मृति ले सकती हैं।

नियतात्मक एसाइक्लिक परिमित राज्य मशीनों की वृद्धि न्यूनतम

ऑटोमेटा को कम करने के साथ कठिनाइयों का समाधान काम में प्रस्तुत किया गया है: जान डासियुक; ब्रूस डब्ल्यू वाटसन; स्टोयन मिहोव; रिचर्ड ई। वॉटसन। "न्यूनतम अम्लीय परिमित-राज्य ऑटोमेटा का वृद्धिशील निर्माण । " यह नियतात्मक एसाइक्लिक परिमित राज्य मशीनों के लिए एक वृद्धिशील न्यूनतम एल्गोरिथ्म प्रस्तुत करता है। यह आपको पहले से निर्मित न्यूनतम ऑटोमेटन को बदलने की अनुमति देता है। नतीजतन, एक पूर्ण ऑटोमेटोन बनाने की आवश्यकता नहीं है, और फिर इसे कम से कम करें।

फिर से, हमारे मशीन दीवार + तीर पर विचार करें:

एल्गोरिथ्म की एक महत्वपूर्ण अवधारणा "स्ट्रिंग की स्थिति" है - यह उन राज्यों का एक क्रम है जो मशीन द्वारा दिए गए स्ट्रिंग के आसपास जाने पर प्राप्त होता है।

उदाहरण के लिए, जब एक तीर के साथ एक रेखा खींचती है, तो हमें राज्यों के निम्नलिखित अनुक्रम मिलते हैं [0, 1, 2, 14, 15, 4, 9, 10]।

इस एल्गोरिथ्म की एक अन्य महत्वपूर्ण अवधारणा किसी दिए गए राज्य (संगम) में संक्रमण की संख्या है। यदि संक्रमण की संख्या एक से अधिक है, तो इस स्थिति को बदलना असुरक्षित है। आकृति में, यह अवस्था 4 है: इसमें 2 आवक तीर हैं।

इसके अलावा, एल्गोरिथ्म मानता है कि एक राज्य रजिस्टर है जो आपको जल्दी से इस के बराबर एक राज्य प्राप्त करने की अनुमति देता है।

नतीजतन, शब्द w जोड़ने के लिए एल्गोरिथ्म इस तरह दिखता है:

 void addMinWord(w) { //    w     int[] stateList = commonPrefix(w); //         int confIdx = findConfluence(stateList); //       if(confIdx > -1) { int idx = confIdx; while(idx < length(stateList)) { int prev = stateList[idx - 1]; int cloned = cloneState(stateList[idx]); stateList[idx] = cloned; //     //        s[prev][w[idx - 1]] = cloned; idx++; confIdx++; } } //   addSuffix(w, stateList); //    ,    . //  ,     replaceOrRegister(w, nodeList); } void replaceOrRegister(w, int[] stateList) { int stateIdx = length(stateList) - 1; int wordIdx = length(w) - 1; //      while(stateIdx > 0) { int state = stateList[stateIdx]; //    ,  state int regState = registerGet(state); if(regState == state) { //    state  ,     continue; } else if(regState == -1) { //     ,      registerAdd(state); } else { //  ,     ,  state int in = w[wordIdx]; //   s[stateList[stateIdx - 1]][in] = regState; //      stateList[stateIdx] = regState; //      removeState(state); } wordIdx--; stateIdx--; } }

एल्गोरिथ्म ऑपरेशन चित्रण

साधारण स्थिति पर विचार करें जब अंतिम स्थिति एक द्विआधारी संकेत है। हालत या तो अंतिम है या नहीं।

स्ट्रिंग "लोमड़ी" के लिए स्वचालित।

यह देखा जा सकता है कि ऑटोमेटन न्यूनतम है, सभी राज्य रजिस्ट्री में हैं [0,1,2,3]

इसमें "बॉक्स" शब्द जोड़ें। चूंकि उनके पास एक सामान्य उपसर्ग नहीं है, हम पूरी पंक्ति को एक प्रत्यय के रूप में जोड़ते हैं। नतीजतन, हम प्राप्त करते हैं:

आप देख सकते हैं कि 3 और 6 राज्य समान हैं। 6 को 3 से बदलें:

अब हम देखते हैं कि वे 2 के बराबर हैं और 5. 5 को 2 से बदलें:

और अब हम देखते हैं कि वे 1 और 4 के बराबर हैं। 4 को 1 से बदलें:

लाइन "लोमड़ियों" जोड़ें। उपसर्ग की गणना करते समय, यह पाया गया कि राज्य [0, 1, 2, 3] उपसर्ग का मार्ग हैं।
इसके अलावा, यह पाया गया कि राज्य 1 में एक से अधिक संक्रमण शामिल हैं। परिणामस्वरूप, "लोमड़ी" शब्द को दरकिनार करने के मार्ग के साथ 1, 2 और 3 राज्यों को क्लोन करना आवश्यक है, क्योंकि यदि आप "लोमड़ियों" को पिछली मशीन में जोड़ते हैं, तो स्ट्रिंग "बक्से" को मान्यता दी जाएगी, जिसे हम निर्दिष्ट नहीं करते हैं।

अब "बॉक्स" जोड़ें:

"बक्से" जोड़कर, मशीन छोटी हो गई है। यह पहली नज़र में एक अप्रत्याशित व्यवहार है जब, जब नई लाइनें जोड़ी जाती हैं, तो मशीन वास्तव में घट जाती है। विपरीत व्यवहार भी है - जब एक लाइन हटाए जाने पर मशीन बढ़ती है।

एल्गोरिथ्म को सही ढंग से काम करने के लिए, रजिस्ट्री के साथ सही ढंग से काम करना महत्वपूर्ण है। राज्य को राज्य परिवर्तन तालिका और अंतिम संकेत में किसी भी परिवर्तन पर रजिस्ट्री से हटा दिया जाता है।

इसके अलावा, एक नियमित सेट या टेबल के विपरीत, रजिस्ट्री से जुड़ाव / निष्कासन इस स्थिति के साथ सटीक रूप से संचालित होता है, और अनुरोध एक समान स्तर पर किया जाता है।

व्यावहारिक उपयोग

प्रस्तुत एल्गोरिथ्म का उपयोग एओटी परियोजना और ईटीएपी -3 प्रणाली में तेजी से रूपात्मक विश्लेषण के आयोजन के लिए किया जाता है। परिमित राज्य मशीनों का उपयोग करके, प्रति सेकंड लगभग 1-1.5 मिलियन शब्दों की विश्लेषण गति प्राप्त की जाती है। इसी समय, विशेष चाल के बिना मशीन का आकार 8 एमबी में फिट बैठता है।

पंक्ति डेटा के संग्रहण को पहले अंतिमता के संकेत के रूप में वर्णित किया गया था। इस दृष्टिकोण पर अधिक विस्तार से विचार करें।

मशीन की स्थिति में डेटा भंडारण

दृष्टिकोण मानता है कि इन तारों को किसी प्रकार की परमाणु वस्तु के रूप में माना जाता है। यह बदले में ऑटोमेटन को कम करने की दक्षता पर प्रतिबंध लगाता है।

उदाहरण के लिए, एक न्यूनतम संख्या एक स्ट्रिंग के साथ जुड़ा होने पर, सटीक हैशिंग के लिए एक न्यूनतम ऑटोमेटोन के निर्माण की प्रक्रिया अर्थहीन है। क्योंकि इस मामले में, प्रत्येक प्रत्यय अद्वितीय होगा, और तदनुसार, कोई न्यूनतम नहीं होगा, क्योंकि प्रत्येक अंतिम स्थिति अद्वितीय है।

रूपात्मक विश्लेषण के लिए, रूपात्मक विशेषताओं के सेट को संबंधित डेटा के रूप में उपयोग किया जा सकता है। यह अच्छी तरह से काम करता है क्योंकि शब्द के कुल रूपों के सापेक्ष ऐसे कुछ सेट हैं। उदाहरण के लिए, रूसी में, गोद लिए गए मॉडल के आधार पर, ऐसे सेटों की संख्या 500-900 है। एक शब्द का रूप 4-5 मिलियन है।

हालांकि, न्यूनतमकरण की प्रभावशीलता शून्य हो जाती है, यदि विशेषताओं के अतिरिक्त, पूर्ण सामान्य रूप बनाए रखा जाता है। ऐसा इसलिए है क्योंकि जोड़ी {सामान्य रूप, रूपात्मक विशेषताएं} लगभग अद्वितीय है।

ETAP-3 प्रणाली रूपात्मक जानकारी संग्रहीत करने के लिए इस तरह के दृष्टिकोण का उपयोग करती है। मशीन में ही रूपात्मक पात्रों के सेट संग्रहीत किए जाते हैं। और सामान्य रूप को संग्रहीत करने के लिए, निम्नलिखित चाल का उपयोग किया जाता है। ऑटोमेटन के निर्माण के चरण में, एक वर्ण नहीं, लेकिन दो का उपयोग इनपुट प्रतीक के रूप में किया जाता है। उदाहरण के लिए, जब एक "दीवार" (वाद्य मामले में दीवार) के साथ शब्द रूप को जोड़ते हैं, तो वर्णों के जोड़े का निम्नलिखित क्रम जोड़ा जाएगा: "c: C", "t: T", "e: E", "n: N", "o: A" , "गु: _"।

ऐसी मशीन में "दीवार" और "तीर" शब्दों के सभी शब्द इस तरह दिखेंगे:

सामान्य रूप में रिकॉर्डिंग करने के इस दृष्टिकोण का एक महत्वपूर्ण लाभ है। यह आपको दो दिशाओं में आकृति विज्ञान के साथ काम करने की अनुमति देता है। आप इसका विश्लेषण शब्द रूप - विश्लेषण में प्राप्त कर सकते हैं। और आप इसके सभी शब्द रूपों को एक सामान्य रूप में प्राप्त कर सकते हैं - संश्लेषण।

इस दृष्टिकोण का नुकसान यह है कि इस तथ्य के बावजूद कि ऑटोमेटन संकेतों की एक जोड़ी के लिए निर्धारक है, यह अब इनपुट एक के लिए एक ऑटोमेटन नहीं है और इस राज्य से सभी संक्रमणों को हल किया जाना चाहिए। उदाहरण के लिए, राज्य एम, ऊपर की आकृति में। शब्द "a" के संकेत के अनुसार इसके कई संक्रमण हैं।

संक्रमण में डेटा भंडारण। एनोटेशन का उपयोग करना

मूल कार्य में अतिरिक्त डेटा संग्रहीत करने के लिए एक और विधि का वर्णन किया गया था। इसमें स्वयं लाइनों को बदलना शामिल है, जो मशीन में संग्रहीत होते हैं।

एक डिजाइन योजना प्रस्तावित है। लक्ष्य रेखा के बजाय, मशीन में एक विस्तारित रेखा लिखी जाती है, जिसमें एक लक्ष्य रेखा, एक डेटा स्टार्ट कैरेक्टर (एक एनोटेटिंग कैरेक्टर) और स्वयं डेटा होता है।

उदाहरण के लिए, इस मामले में रूपात्मक विशेषताओं को निम्नानुसार लिखा जा सकता है: "दीवार | + संज्ञा + महिला + इम, ..., जहां '|' - एक एनोटेटिंग चरित्र, और "+ मौजूदा", "+ महिलाएं", "+ उन्हें" - विशेष डेटा वर्ण।

एओटी प्रणाली में इस दृष्टिकोण का उपयोग किया जाता है। इसमें, वास्तव में, दो संदर्भों को डेटा के रूप में संग्रहीत किया जाता है: रूपात्मक विशेषताओं और विभक्ति नियम संख्या के लिए। परिणामस्वरूप, जब विश्लेषण करते हुए शब्द रूप का उपयोग करके अपनी रूपात्मक विशेषताओं और प्रारंभिक रूप दोनों को प्राप्त करना संभव है।

इस दृष्टिकोण की एक विशेषता यह है कि ऑटोमेटन का मॉडल कुछ अधिक जटिल है। संक्रमण प्रतीक की व्याख्या अलग-अलग तरीके से की जाती है, जो इस बात पर निर्भर करता है कि वह प्रतीक चिन्ह के पहले या बाद में था।

एक और विशेषता यह है कि लाइन-बाय-लाइन ट्रैवर्सल के लिए थोड़ा अधिक जटिल है। सबसे पहले, मशीन में एक रेखा मौजूद होती है यदि, उसके बाद पता लगाया जाता है, तो हम खुद को एक ऐसी स्थिति में पाते हैं जहां से एक एनोटेटिंग प्रतीक द्वारा एक संक्रमण होता है। दूसरी बात, एनोटेटिंग सिंबल के बाद सभी एनोटेशन को इकट्ठा करने के लिए एक प्रक्रिया की आवश्यकता होती है। तीसरा, एक एनोटेशन डिकोडिंग प्रक्रिया की आवश्यकता है।

मेमोरी अनुकूलन

स्मृति की मात्रा का अनुकूलन करने के लिए, परिमित ऑटोमेटा के दो अभ्यावेदन का उपयोग किया जाता है: एक न्यूनतम ऑटोमेटन के निर्माण के लिए, और दूसरा विश्लेषण के लिए। दोनों के बीच अंतर यह है कि विश्लेषण मशीन परिवर्तन नहीं करती है और इसलिए इसे स्मृति में अधिक कुशलता से रखा जा सकता है।

विश्लेषण मशीन में तीन संरचनाएँ होती हैं:

रूपांतरण तालिका - पूर्णांक जोड़े {संक्रमण प्रतीक, लक्ष्य स्थिति}
राज्य संक्रमणों की श्रेणी की शुरुआत और अंत के संकेत
अंतिम राज्य डेटा तालिका

ऑटोमेटा पर्याप्त कॉम्पैक्ट हैं। उदाहरण के लिए, विशेष ट्रिक्स के बिना AOT डिक्शनरी में लगभग 8Mb लगता है। रूपात्मक विश्लेषण प्रणाली का पूरा डेटा, जिसमें न केवल शब्दकोश विश्लेषण शामिल है, बल्कि पूर्वानुमान शब्द विश्लेषण भी 16Mb में फिट है।

मिनीमाइजेशन एल्गोरिदम स्वयं गिथुब पर मेरी परियोजना में लागू किए गए हैं: github.com/kzn/fsa

स्वचालित वर्ड प्रोसेसिंग के लिए शब्दकोश प्रस्तुत करने के तरीके