पेनिसलैंड, या स्पेलसेचर कैसे लिखना है

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







इसलिए, मैं इन समस्याओं को ठीक करना चाहता हूं। अर्थात्, छोटे वाक्यांशों या प्रश्नों के लिए एक सुधारक लिखें:

• अनुरोध में तीन (या अधिक) त्रुटियों की पहचान करने में सक्षम हो;
• "टूटे हुए" या "एक साथ अटक" वाक्यांशों के लिए जाँच करने में सक्षम होगा, उदाहरण के लिए expertsexchange - expert_exchange, ma na ger - manager
• लागू करने के लिए बहुत सारे कोड की आवश्यकता नहीं थी
• अन्य भाषाओं और अन्य प्रकार की त्रुटियों में त्रुटियों को ठीक करने से पहले पूरा किया जा सकता है

बाकी कटौती के तहत है।

त्रुटि का निर्धारण कैसे करें

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

• शब्दकोश में शब्द पर विश्वास करें
• यदि नहीं, तो एकल-अक्षर त्रुटियां उत्पन्न करें, और शब्दकोश में जांचें
• यदि विफलता फिर से, दो-अक्षर त्रुटियों को उत्पन्न करें, और फिर से शब्दकोश में

त्रुटि पीढ़ी के तहत यहां एक काफी सरल बात समझी जाती है। चेक किए जा रहे शब्द के लिए, शब्दों का एक समूह बनाया गया है, जो 4 ऑपरेशनों को लागू करके प्राप्त किया जाता है: हटाएं, डालें, बदलें और पुन: व्यवस्थित करें। उदाहरण के लिए, 'एर' शब्द के स्थान पर 'ओ' को 'एरर' में बदलने की त्रुटियां निम्नलिखित शब्दों द्वारा दी जाएंगी: एरर, एरर, आशाबाका, आशिका, आशिबा, एरर। यह स्पष्ट है कि यह वर्णमाला के सभी अक्षरों के लिए किया जाता है। इसी तरह, शब्द डालने, हटाने और पुनर्व्यवस्थित करने के लिए शब्द उत्पन्न होते हैं।



इस दृष्टिकोण में एक खामी है। यदि आप गिनते हैं, तो 5 वर्णों की लंबाई वाले अंग्रेजी वर्णमाला और शब्दों के लिए, हमें एक त्रुटि के लगभग 400 वेरिएंट मिलते हैं। दो त्रुटियों के लिए - 160,000। तीन त्रुटियों के लिए - छह मिलियन से अधिक। और यहां तक ​​कि अगर कोई शब्दकोश चेक एक स्थिर समय में होता है, तो इस तरह के कई विकल्प उत्पन्न करना बहुत लंबा है। और यह शालीनता से स्मृति को खा जाता है।



हम दूसरे तरीके से जा सकते हैं: समानता के कुछ माप का उपयोग करते हुए, शब्दकोश से प्रत्येक शब्द के साथ चेक किए जा रहे शब्द की तुलना करें। यहाँ, लेवेंसहाइट दूरी हमारी मदद करेगी। संक्षेप में, लेवेंशेटिन दूरी संपादन कार्यों की न्यूनतम संख्या है जिसे दूसरी प्राप्त करने के लिए पहली पंक्ति में लागू करने की आवश्यकता होती है। क्लासिक संस्करण में, तीन ऑपरेशनों पर विचार किया जाता है: सम्मिलित करें, हटाएं और बदलें। उदाहरण के लिए, "बिल्ली" शब्द से "कैफे" प्राप्त करने के लिए, हमें दो कार्यों की आवश्यकता है: एक प्रतिस्थापन (टी-> एफ) और एक डालें (-> ई)।



ca t

सीए फ



लेकिन एक पकड़ है। लेवेंसहाइट दूरी को O (n * m) माना जाता है, जहाँ n, m संबंधित रेखाओं की लंबाई हैं। इस प्रकार, एक लोबान की लेवेनशेटिन दूरी की गणना करना संभव नहीं है। हालाँकि, आप डिक्शनरी को स्टेट मशीन में बदलकर इसके साथ काम कर सकते हैं।

राज्य की मशीनें

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







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



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







यहां स्ट्रिंग 'कैट' को स्ट्रिंग 'लोमड़ी' में बदलने का एक उदाहरण है।

ऑटोमेटा रचना

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

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



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

रचना के माध्यम से लेवेंसहिन दूरी

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

• पहला शब्द ट्रांसड्यूसर
• त्रुटि ट्रांसड्यूसर
• दूसरा शब्द ट्रांसड्यूसर

पहले दो ट्रांसड्यूसर आने वाली लाइनों का प्रतिनिधित्व करते हैं (आंकड़े देखें)। वे बिल्ली और स्नान शब्द का उपयोग करते हैं।











त्रुटि मॉडल रिफ्लेक्टिव (स्वयं के लिए बंद) संक्रमण वाला एक राज्य है। संक्रमण के अपवाद के साथ उनमें से सभी: ए, संपादन कार्यों का प्रतिनिधित्व करते हैं:

• a: a - चरित्र को अपरिवर्तित छोड़ दें
• ए: बी - चरित्र प्रतिस्थापन; यहाँ 'a' से 'b'
• eps: a - इन्सर्ट कैरेक्टर
• a: eps - वर्ण प्रतीक हटाएं

चित्र को अव्यवस्थित नहीं करने के लिए, यह केवल दो अक्षरों के लिए सुधार दिखाता है। यह ध्यान दिया जाना चाहिए कि प्रत्येक संक्रमण एक संख्या के साथ चिह्नित है। ये वजन सुधार के पदनाम हैं। यानी डालने, बदलने, संचालन को हटाने के लिए, वजन 1. प्रकार है: एक संक्रमण के प्रकार के लिए एक: एक, जो केवल सुधार के बिना मूल चरित्र का अनुवाद करता है, वजन 0. है नतीजतन, अंतिम रचना निम्न रूप लेगी।







और यहाँ परिणाम है: सबसे कम पथ के साथ वजन का योग लेवेंसाइटिन दूरी होगी । इस उदाहरण में, यह तरीका है: 0 - 1 - 4 - 10 - 17 । इस पथ के साथ भार का योग 2 है। और अब हम इस पथ के साथ निशान का पालन करेंगे: c: ba: at: t eps: h। यह एडिटिंग ऑपरेशन के अलावा और कुछ नहीं है। यानी शब्द को बिल्ली से स्नान करने के लिए , हमें पहले अक्षर को बदलने और आखिरी में 'एच' जोड़ने की जरूरत है।



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

भाषा मॉडल

व्यक्तिगत शब्दों में त्रुटियों को कैसे ठीक किया जाए यह पहले से ही स्पष्ट है। लेकिन जब दो शब्द एक साथ फंस गए तो गलती कैसे ठीक की जाए। उदाहरण के लिए, अगर किसी ने पेन आइलैंड की जगह पेनिसलैंड लिखा है। इसके अलावा, आपको इन शब्दों को सही ढंग से अलग करने की आवश्यकता है ताकि उपयोगकर्ता के मानस को घायल न करें। वैसे, यांडेक्स और रैम्बलर दोनों ही अच्छा काम करते हैं, जबकि mail.ru कट जाता है ।



तार को सही ढंग से खंडित या संयोजित करने के लिए, आपको यह जानना होगा कि कौन सा वाक्यांश सबसे अधिक संभावना है। सांख्यिकीय भाषाविज्ञान में, इसके लिए तथाकथित भाषा मॉडल का उपयोग किया जाता है, जो आमतौर पर एनग्राम मॉडल (या बायेसियन नेटवर्क) के आधार पर बनाया जाता है। यहां मैं विस्तार से नहीं बताऊंगा कि यह क्या है। पाठक मेरी पिछली पोस्ट पर एक नज़र डाल सकते हैं, जहां इस तरह का एक मॉडल एक साधारण पाठ जनरेटर के लिए बनाया गया है।



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







आकृति कुछ शब्दों के लिए एक भाषा मॉडल दिखाती है। चित्र थोड़ा भ्रमित करने वाला लगता है, लेकिन इसके निर्माण के लिए एल्गोरिथ्म सरल है। हालाँकि, भाषा मॉडल एक अलग लेख की आवश्यकता वाला विषय है। निकट भविष्य में मुझे यह लिखने की उम्मीद है।



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

यह सब एक साथ रखना

एक स्पैनिश बनाने के लिए हमारे पास सब कुछ है। आपको बस चार ट्रांसड्यूसर रचना करने की आवश्यकता है:

आर = एस ओ ई ओ एल एल एम

• एस - स्रोत स्ट्रिंग
• ई - त्रुटि मॉडल
• एल - लेक्सिकन
• एम - भाषा मॉडल

और परिणामी ट्रांसड्यूसर आर में सबसे छोटा रास्ता खोजें। शब्दों के एक सेट का प्रतिनिधित्व करने वाला एक पथ वांछित फिक्स होगा।



ऐसे कुछ बिंदु हैं, जिन्हें स्पष्टीकरण की आवश्यकता है। सबसे पहले, एल कनवर्टर। यह एक बल्कि तुच्छ ट्रांसड्यूसर है, "gluing" अक्षरों से एक शब्द मॉडल में एक पूरे शब्द को स्थानांतरित करने के लिए। इस तरह, यह त्रुटि मॉडल के अक्षरों और प्रतीकों से भाषा मॉडल में शब्दों को स्थानांतरित करने में मदद करता है। दूसरा बिंदु ट्रांसड्यूसर का संतुलन है। सही रचना का उत्पादन करने के लिए, यह आवश्यक है कि सभी ट्रांसड्यूसर के वजन का एक अर्थ है। स्रोत लाइन और लेक्सिकॉन में वज़न नहीं है, भाषा मॉडल संभावनाओं का प्रतिनिधित्व करता है, लेकिन त्रुटि मॉडल लेवेन्सहाइटिन देता है। हमें इस अनुमान से संभावनाओं की ओर बढ़ने की जरूरत है। यह प्रक्रिया shamanism के करीब है, लेकिन फिर भी उन वज़न को चुनना संभव है जो वास्तविक गलतियों के लिए सबसे उपयुक्त हैं।



वह, शायद, सब है। आप सही पूछ सकते हैं, कोड कहां है? लेकिन वह नहीं है। सब कुछ कन्वर्टर्स पर संचालन का उपयोग करके किया जाता है। और ये ऑपरेशन पुस्तकालयों में पहले से ही लागू हैं। उदाहरण के लिए, इसमें: openfst.org आप सभी की जरूरत स्रोत वस्तुओं का निर्माण करने के लिए है।

निष्कर्ष, प्रो एट गर्भनिरोधक

मुझे यह दृष्टिकोण बहुत दिलचस्प लगता है। उसके पास कई ताकतें हैं। पहली ताकत यह है कि हम कोड नहीं लिखते हैं, लेकिन बस गणितीय वस्तुओं पर काम करते हैं। यह पाठ उपकरण के विकास को सरल करता है और बहुत समय बचाता है।



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



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



आशा है कि लेख उपयोगी था। कुछ स्पष्ट न होने पर प्रश्न पूछें। मैं आनंद से उत्तर दूंगा।