ऑटोमेटा आकृति विज्ञान विश्लेषक

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



यहां मैं राज्य मशीनों पर आधारित एक संस्करण देता हूं जहां मैं इन समस्याओं से बचने की कोशिश करूंगा। यह कैसे काम करता है यहां देखा जा सकता है ।



तो हम आकृति विज्ञान से क्या चाहते हैं। आमतौर पर, एक आकृति विज्ञान विश्लेषण मॉड्यूल की आवश्यकता होती है:

• दिए गए शब्द के लिए एक लेम्मा प्राप्त करना
• किसी दिए गए शब्द के लिए रूपात्मक जानकारी प्राप्त करना
• आकृति विज्ञान की भविष्यवाणी

हम यह सब दो अवयवों से तैयार करेंगे: एक रूपात्मक शब्दकोश और ऑटोमेटा का एक पुस्तकालय। पहला जो हम aot.ru प्रोजेक्ट से लेते हैं (जैसा कि पहले ही स्वीकार कर लिया गया है), LGPL के लिए उनके लिए धन्यवाद। और ऑटोमेटन लाइब्रेरी यहाँ से है: openfst.org । कोड कम से कम किया जाएगा: सभी आवश्यक संचालन पहले से ही पुस्तकालय में कार्यान्वित किए जाते हैं।

पहला कदम। पारसिम रूपात्मक शब्दकोश।

रूपात्मक शब्द में प्रपत्र की पंक्तियाँ होती हैं:







यहाँ 'धुंध' शब्द के लिए एक उदाहरण दिया गया है। पत्र एमजीएल शब्द की जड़ हैं। शेष अंत (विभक्ति) है। हम इस मामले में, मूल और पहले विभक्ति को जोड़कर एक लेम्मा, या एक सामान्यीकृत शब्द प्राप्त कर सकते हैं, एमजीएलए। छोटे दो-अक्षर संयोजन एक एनोड हैं। यानी यह एक कोड है जो शब्द रूप की आकृति विज्ञान को विशिष्ट रूप से परिभाषित करता है। उदाहरण के लिए, 'गा' के लिए यह एक 'संज्ञा, स्त्रीलिंग, एकवचन, नाममात्र' है।



चलो कार्रवाई पर चलते हैं। शब्दकोश की प्रत्येक पंक्ति के लिए हम इस संरचना का निर्माण करते हैं।





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



सामान्य तौर पर, आप मानक रचना ऑपरेशन का उपयोग करके इनपुट द्वारा आउटपुट शब्द प्राप्त कर सकते हैं:

यदि D एक शब्दकोश है, जैसा कि ऊपर की तस्वीर में है,

W शब्द है, जहां W = <(M, M) (G, D) (L, L) (O, O) (Y, Y), (I, I)>

तब एम - रचना का परिणाम - बराबर (शून्य से खाली वर्ण) होगा

एम = डब्ल्यू ओ डी = <(एम, एम) (जी, डी) (ए, ए) (ए, ए) (ए) (ए) (एम, एम)

चरण दो अनुकूलन।

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



और इसलिए, पहले हम आउटगोइंग प्रतीकों को प्रारंभिक अवस्था की ओर स्थानांतरित करते हैं। इससे खाली पात्रों की संख्या कम हो जाएगी। ओपनफ़ास्ट लाइब्रेरी इस तरह के एक ऑपरेशन को लागू करता है। इसे fstpush कहा जाता है।



जैसा कि आप आकृति में देख सकते हैं, निशान के साथ आर्क्स "-: -" दिखाई दिया। उन्हें पैकेजिंग प्रक्रिया के दौरान हटा दिया जाएगा।

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

इस समस्या को हल करने के लिए, आप कर सकते हैं

• कनवर्टर को राज्य मशीन में लाएं
• मशीन पैक करें (मानक एल्गोरिथ्म के अनुसार)
• परिणामी मशीन को कनवर्टर में लाएं

ये सभी ऑपरेशन मानक हैं; कोड लिखने की कोई आवश्यकता नहीं है। नीचे दी गई छवि में "धुंध" शब्द के लिए परिणाम।





जैसा कि आंकड़े से देखा जा सकता है, राज्यों और संक्रमणों की संख्या में स्पष्ट रूप से कमी आई है। और यही हमारा लक्ष्य है।

चरण तीन अज्ञात शब्द की आकृति विज्ञान की भविष्यवाणी।

यहां सब कुछ सरल है। आने वाले शब्द W के लिए दो कन्वर्टर्स के साथ एक कंपोज़िशन तैयार करना और अंतिम अवस्था का सबसे छोटा रास्ता खोजना होगा:

P = सबसे छोटा (W o T o D)

जहां, डी एक शब्दकोश है

टी वजन के साथ एक विशेष कनवर्टर है जो शब्द को उपसर्ग को अवशोषित करता है, जबकि प्रत्येक "खाया" चरित्र को दंडित करता है।





मैंने अभी तक उदाहरण में भविष्यवाणी को लागू नहीं किया है। शायद बाद में।

निष्कर्ष

मेरी राय में, यह आकृति विज्ञान के साथ काम करने का एक दिलचस्प तरीका है। मैं दो महत्वपूर्ण लाभों को उजागर कर सकता हूं:

• गति और संसाधन
• विकास में आसानी
• एल्गोरिदम की सार्वभौमिकता

इस उदाहरण में गति के बारे में, मैं झपट्टा से अच्छे परिणाम प्राप्त करने में सक्षम नहीं था। यह 2000 शब्दों / सेकंड की तरह निकला। लेकिन मैंने मानक पुस्तकालय का उपयोग किया और वास्तव में अनुकूलन की परवाह नहीं की। शायद, यदि आप अन्य प्रकार के ट्रांसड्यूसर का उपयोग करते हैं, तो गति बढ़ सकती है। शब्दकोश का वजन लगभग 35M है (हालाँकि, यदि आप कॉम्पैक्ट प्रतिनिधित्व का उपयोग करते हैं, तो इसे 3 बार संपीड़ित किया जाता है)।



सादगी की कीमत पर: यहां बहुत सारे कोड की आवश्यकता नहीं है। यह मानक संचालन का उपयोग करने के लिए पर्याप्त है: सबसे छोटा रास्ता, संरचना, संयोजन, संयोजन और खोज। शब्दकोश के निर्माण में कोड की लगभग 50 लाइनें थीं। स्रोत कोड और अजगर बाइंडिंग के साथ तारबॉल उदाहरण यहां डाउनलोड किए जा सकते हैं ।



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

शायद बस इतना ही। मुझे उम्मीद है कि यह दिलचस्प था।