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

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



ऐसा लग सकता है कि हमने उपयोगकर्ता को ऊर्ध्वाधर वास्तविकता के अपने सपने से इनकार कर दिया है, लेकिन वास्तव में अक्षर K केवल अक्षर B के बगल में कीबोर्ड पर खड़ा है।

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

समस्या का बयान

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

• शब्द दिया $$$एस$ त्रुटियों के साथ हमारे लिए प्रेषित;
• एक शब्दकोश है $$$\ सिग्मा$ सही शब्द;
• शब्दकोश में सभी शब्दों के लिए सशर्त संभावनाएं हैं $$$P (w | s)$ शब्द से क्या मतलब था $$$w$ बशर्ते कि हमें शब्द मिले $$$एस$ ;
• आपको अधिकतम संभाव्यता के साथ शब्द w से खोजने की आवश्यकता है $$$P (w | s)$ ।

यह कथन - सबसे प्राथमिक - यह बताता है कि यदि हमें कई शब्दों का अनुरोध मिला है, तो हम प्रत्येक शब्द को व्यक्तिगत रूप से सही करते हैं। वास्तविकता में, निश्चित रूप से, हम आसन्न शब्दों की अनुकूलता को देखते हुए, पूरे वाक्यांश को एक पूरे के रूप में सही करना चाहेंगे; मैं बाद में इस बारे में बात करूंगा कि "वाक्यांशों को कैसे सही करें"।

दो अस्पष्ट क्षण हैं - जहां शब्दकोश प्राप्त करना है और कैसे गिनना है $$$P (w | s)$ । पहला प्रश्न सरल माना जाता है। 1990 [1] में, इस शब्द को वर्तनी उपयोगिता डेटाबेस और इलेक्ट्रॉनिक रूप से उपलब्ध शब्दकोशों से संकलित किया गया था; 2009 में, Google [4] ने सरल किया और बस इंटरनेट पर सबसे लोकप्रिय शब्द (लोकप्रिय गलत वर्तनी के साथ) ले लिया। मैंने अपना अभिभावक बनाने के लिए यह तरीका अपनाया।

दूसरा प्रश्न अधिक जटिल है। यदि केवल इसलिए कि उसका निर्णय आमतौर पर बेयस फॉर्मूला के आवेदन से शुरू होता है!

$$

$$P (w | s) = \ mathrm {const} \ cdot P (s | w) \ cdot P (w)$$

अब, प्रारंभिक अकल्पनीय संभावना के बजाय, हमें दो नए, थोड़ा और अधिक समझने योग्य मूल्यांकन करने की आवश्यकता है: $$$P (s | w)$ - संभावना है कि एक शब्द टाइप करते समय $$$w$ सील और प्राप्त किया जा सकता है $$$एस$ , और $$$पी (डब्ल्यू)$ - सिद्धांत रूप में, उपयोगकर्ता शब्द का उपयोग करने की संभावना $$$w$ ।

कैसे रेट करें $$$P (s | w)$ ? जाहिर है, उपयोगकर्ता को ओ के साथ बी के साथ ए के साथ भ्रमित करने की अधिक संभावना है। और अगर हम स्कैन किए गए दस्तावेज़ से मान्यता प्राप्त पाठ को सही करते हैं, तो आरएन और एम के बीच भ्रम की संभावना अधिक है। एक तरह से या किसी अन्य, हमें किसी प्रकार के मॉडल की आवश्यकता है जो त्रुटियों और उनकी संभावनाओं का वर्णन करता है।

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

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

त्रुटि मॉडल

पहले त्रुटि मॉडल पर विचार किया गया था $$$P (s | w)$ , प्रशिक्षण सेट में प्राथमिक प्रतिस्थापन की संभावनाओं की गणना: ई के बजाय कितनी बार उन्होंने लिखा और, टी के बजाय टी ने कितनी बार लिखा - टी - टी के बजाय और इसी तरह [1]। यह एक छोटी संख्या में मापदंडों के साथ एक मॉडल निकला जो कुछ स्थानीय प्रभाव सीख सकता है (उदाहरण के लिए, लोग अक्सर ई और आई को भ्रमित करते हैं)।

हमारे शोध में, हम 2000 में ब्रिल और मूर द्वारा प्रस्तावित एक अधिक विकसित त्रुटि मॉडल पर बसे [2] और बाद में पुन: उपयोग (उदाहरण के लिए, Google विशेषज्ञों द्वारा [4])। कल्पना करें कि उपयोगकर्ता अलग-अलग वर्णों में नहीं सोचते हैं (ई और आई को भ्रमित करें, वाई के बजाय K दबाएं, एक नरम चिह्न छोड़ें), लेकिन किसी शब्द के मनमाने टुकड़े को किसी अन्य को बदल सकते हैं - उदाहरण के लिए, TSYA को TYSYA, Y के साथ K, SHA के साथ SHCHYA, SS के साथ बदलें। सी और इतने पर। उपयोगकर्ता द्वारा सील किए जाने की संभावना और TSYA के बजाय हमने THY लिखा है, हम निरूपित करते हैं $$$P (\ text {हजार} \ rightarrow \ text {हजार})$ हमारे मॉडल का एक पैरामीटर है। यदि सभी संभव टुकड़ों के लिए $$$\ अल्फा, \ बीटा$ हम गिन सकते हैं $$$P (\ Alpha \ rightarrow \ beta)$ , तो वांछित संभावना $$$P (s | w)$ शब्द का एक सेट जब ब्रिल और मूर मॉडल में शब्द w टाइप करने का प्रयास किया जा सकता है, तो हम w को तोड़ते हैं और सभी संभव तरीकों से छोटे टुकड़ों में तोड़ते हैं, ताकि दो शब्दों में समान संख्या में टुकड़े हों। प्रत्येक विभाजन के लिए, हम इसी अंशों में बदलने के लिए सभी टुकड़ों की संभावनाओं की गणना करते हैं। ऐसे सभी विभाजनों के लिए अधिकतम मूल्य के रूप में लिया जाएगा $$$P (s | w)$ :

$$

$$P (s। W) = \ max_ {s = \ Alpha_1 \ Alpha_2 \ ldots \ Alpha_k, w = \ Beta_1 \ Beta_2 \ ldots \ Beta_k} P (\ Alpha_1 \ rightarrow's beta_1) \ cdot P (\ alpha_2 \ rightarrow) \ Beta_2) \ cdot \ ldots \ cdot P (\ Alpha_k \ rightarrow \ beta_k) \ _ $$$

आइए विभाजन के एक उदाहरण को देखें जो "एक्सेसरी" के बजाय "एक्सेसरी" को प्रिंट करने की संभावना की गणना करते समय होता है:

$$

$$\ _ {मैट्रिक्स} \ टेक्स्ट {ak} & \ text {cec} & \ text {sou} & \ text {a} & \ text {p} \\ \ downarrow & \ downarrow & \ downarrow & \ downarrow & \ _ downarrow \\ \ text {a} & \ text {cc} & \ text {e} & \ text {soua} & \ text {p} \ end {मैट्रिक्स}$$

जैसा कि आपने शायद देखा है, यह एक बहुत सफल विभाजन का उदाहरण नहीं है: यह स्पष्ट है कि शब्दों के भाग एक दूसरे के नीचे झूठ नहीं बोलते थे जितनी सफलतापूर्वक हो सकते हैं। यदि मात्राएँ $$$P (\ text {ak} \ rightarrow \ text {a})$ और $$$P (\ text {p} \ rightarrow \ text {p})$ अभी भी इतना बुरा नहीं है $$$P (\ text {sou} \ rightarrow \ text {e})$ और $$$P (\ text {a} \ rightarrow \ text {soua})$ सबसे अधिक संभावना है कि वे इस विभाजन के अंतिम "स्कोर" को पूरी तरह से दुखी करेंगे। एक अधिक सफल विभाजन कुछ इस तरह दिखता है:

$$

$$\ _ {मैट्रिक्स} \ पाठ {ak} & \ {{{}} पाठ और पाठ {ss} & \ {पाठ {y} & \ {पाठ {ar} \\ \ downarrow और \ downarrow और \ downarrow और \ downrowrow और \ downarrow \\ \ text {ak} & \ text {Ce} & \ text {c} और \ text {y} & \ text {ar} \ end {मैट्रिक्स}$$

यहां, सब कुछ तुरंत जगह में गिर गया, और यह स्पष्ट है कि अंतिम संभावना मुख्य रूप से मूल्य से निर्धारित की जाएगी $$$P (\ text {ss} \ rightarrow \ text {s})$ ।

गणना कैसे करें $$$P (s | w)$

इस तथ्य के बावजूद कि दो शब्दों के लिए संभावित विभाजन के आदेश हैं $$$O (2 ^ {| s | + | w |} |)$ गतिशील प्रोग्रामिंग गणना एल्गोरिथ्म का उपयोग करना $$$P (s | w)$ के लिए बहुत तेजी से बनाया जा सकता है $$$O (| s | ^ 2 | w | ^ 2)$ । एल्गोरिथ्म खुद लेवेंसहाइट दूरी की गणना करने के लिए वैगनर-फिशर एल्गोरिदम से दृढ़ता से मिलेंगे।

हम एक आयताकार तालिका बनाएंगे, जिसमें से पंक्तियाँ सही शब्द के अक्षरों के साथ मेल खाती हैं, और कॉलम एक को सील कर दिया जाएगा। एल्गोरिथ्म के अंत तक पंक्ति i और स्तंभ j के चौराहे पर सेल के पास w[:i] प्रिंट करने का प्रयास करते समय s[:j] होने की पूरी संभावना होगी। इसकी गणना करने के लिए, पिछली पंक्तियों और स्तंभों में सभी कोशिकाओं के मूल्यों की गणना करना और उन पर जाना, इसके अनुरूप गुणा करना पर्याप्त है $$$P (\ Alpha \ rightarrow \ beta)$ । उदाहरण के लिए, यदि हमारे पास एक तालिका भरी हुई है


, फिर चौथी पंक्ति में सेल को भरने के लिए और तीसरा कॉलम (ग्रे) आपको अधिकतम लेने की आवश्यकता है $$$0.8 \ cdot P (\ text {cc} \ rightarrow \ text {c})$ और $$$0.16 \ cdot P (\ text {c} \ rightarrow \ text {k})$ । उसी समय, हम चित्र हरे रंग में हाइलाइट किए गए सभी कोशिकाओं के माध्यम से भाग गए। अगर हम फॉर्म के संशोधनों पर भी विचार करते हैं $$$P (\ Alpha \ rightarrow \ text {खाली लाइन})$ और $$$P (\ text {खाली लाइन} \ rightarrow \ beta)$ , तो आपको पीले रंग में हाइलाइट की गई कोशिकाओं के ऊपर जाना होगा।

इस एल्गोरिथ्म की जटिलता, जैसा कि मैंने ऊपर उल्लेख किया है, है $$$O (| s | ^ 2 | w | ^ 2)$ : हम तालिका में भरते हैं $$$| s | \ बार | w | $$ , और सेल को भरने के लिए (i, j) जो आपको चाहिए $$$O (i \ cdot j)$ संचालन। हालाँकि, अगर हम अपने विचार को कुछ सीमित लंबाई से अधिक नहीं सीमित करते हैं $$$एल$ (उदाहरण के लिए, दो अक्षरों से अधिक नहीं, जैसा कि [4]) में जटिलता घट जाएगी $$$O (| s | \ cdot | w | \ cdot L ^ 2)$ । अपने प्रयोगों में रूसी भाषा के लिए मैंने लिया $$$L = 3$ ।

अधिकतम कैसे करें $$$P (s | w)$

हमने ढूंढना सीखा $$$P (s | w)$ बहुपद के लिए समय अच्छा है। लेकिन हमें यह जानने की ज़रूरत है कि पूरे शब्दकोश में सबसे अच्छे शब्दों को कैसे जल्दी से खोजा जाए। और सर्वश्रेष्ठ नहीं हैं $$$P (s | w)$ , लेकिन $$$P (w | s)$ ! वास्तव में, हमारे लिए कुछ उचित शीर्ष (उदाहरण के लिए, सबसे अच्छा 20) शब्द प्राप्त करना पर्याप्त है $$$P (s | w)$ , जो तब हम सबसे उपयुक्त सुधार (नीचे इस पर और अधिक) का चयन करने के लिए भाषा मॉडल को भेजेंगे।

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

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

यह एल्गोरिदम, कुछ अतिरिक्त अनुकूलन के साथ, हमें एक सौ मिलीसेकंड [2] के भीतर 50-100 हजार शब्दों में एक विशिष्ट यूरोपीय भाषा के शब्दकोश को छाँटने की अनुमति देता है। और परिणामों को कैशिंग करने से प्रक्रिया और भी तेज हो जाएगी।

कैसे मिलेगा? $$$P (\ Alpha \ rightarrow \ beta)$

गणना $$$P (\ Alpha \ rightarrow \ beta)$ विचाराधीन सभी टुकड़ों के लिए - एक त्रुटि मॉडल के निर्माण का सबसे दिलचस्प और गैर-तुच्छ हिस्सा। यह इन मात्राओं से है कि इसकी गुणवत्ता निर्भर करेगी।

[२, ४] में प्रयुक्त दृष्टिकोण अपेक्षाकृत सरल है। चलिए बहुत सारे कपल ढूंढते हैं $$$(s_i, w_i)$ जहाँ $$$w_i$ शब्दकोश से सही शब्द है, और $$$s_i$ - इसका सील संस्करण। (कैसे उन्हें खोजने के लिए वास्तव में थोड़ा कम है।) अब हमें इन जोड़ियों से विशिष्ट टाइपो की संभावनाओं को निकालने की आवश्यकता है (कुछ टुकड़ों को दूसरों के साथ बदलना)।

प्रत्येक जोड़ी के लिए हम इसके घटक लेते हैं $$$w$ और $$$एस$ और उनके पत्रों के बीच एक पत्राचार का निर्माण, Levenshtein दूरी को कम करने:

$$

$$\ _ {मैट्रिक्स} \ टेक्स्ट {एई} और \ टेक्स्ट {लेट} और \ टेक्स्ट {} & \ टेक्स्ट {} और \ टेक्स्ट {} और \ टेक्स्ट {} & \ टेक्स्ट {you} और \ टेक्स्ट {a} & \ text {p} \\ \ text {a} & \ text {k} & \ text {c} और \ text {e} & \ text {c} & \ text {} और \ text {y } और \ टेक्स्ट {ए} और \ टेक्स्ट {पी} \ एंड {मैट्रिक्स}$$

अब हम तुरंत प्रतिस्थापन देखते हैं: एक → ए, ई → और, सी → सी, सी → एक खाली स्ट्रिंग और इसी तरह। हम दो या दो से अधिक वर्णों के प्रतिस्थापन भी देखते हैं: ak → ak, ce → si, ec → is, ss → s, ses → sis, Ess → is और अन्य, और इसी तरह। इन सभी प्रतिस्थापनों को गिना जाना चाहिए, और प्रत्येक के रूप में शब्द के रूप में कई बार कॉर्पस में होता है (यदि हमने शब्द को कॉर्पस से लिया है, जो बहुत संभावना है)।

सभी जोड़े में पास होने के बाद $$$(s_i, w_i)$ संभाव्यता के लिए $$$P (\ Alpha \ rightarrow \ beta)$ हमारे जोड़े में होने वाले प्रतिस्थापन α → β की संख्या को स्वीकार किया जाता है (खंडों की पुनरावृत्तियों की संख्या से विभाजित) (संबंधित शब्दों की घटना को ध्यान में रखते हुए)।

कपल्स कैसे पाएं $$$(s_i, w_i)$ ? [४] में, यह दृष्टिकोण प्रस्तावित किया गया था। उपयोगकर्ता-जनित सामग्री (UGC) के बड़े निकाय को लें। Google के मामले में, यह सिर्फ लाखों-करोड़ों वेब पेजों का पाठ था; हमारे उपयोगकर्ता की लाखों उपयोगकर्ता खोजें और समीक्षाएं हैं। यह माना जाता है कि आमतौर पर सही शब्द कॉर्पस में किसी भी गलत संस्करण की तुलना में अधिक बार पाया जाता है। तो, आइए लेवेंसहेटिन के पास से प्रत्येक शब्द के लिए शब्द को कोरपस से ढूंढें, जो बहुत कम लोकप्रिय हैं (उदाहरण के लिए, दस बार)। लोकप्रिय ले लो $$$w$ , कम लोकप्रिय - के लिए $$$एस$ । इसलिए हमें एक शोरगुल मिलता है, लेकिन जोड़े का एक बड़ा सेट जिस पर प्रशिक्षित होना है।

यह युग्म मिलान एल्गोरिथ्म सुधार के लिए बहुत जगह छोड़ता है। [4] में, केवल एक फ़िल्टर घटना होती है ( $$$w$ से दस गुना अधिक लोकप्रिय है $$$एस$ ), लेकिन इस लेख के लेखक भाषा के किसी भी पूर्व ज्ञान का उपयोग किए बिना, एक गपशप बनाने की कोशिश कर रहे हैं। यदि हम केवल रूसी भाषा पर विचार करते हैं, तो हम उदाहरण के लिए, रूसी शब्द रूपों के शब्दकोशों का एक सेट ले सकते हैं और शब्द के साथ केवल जोड़े छोड़ सकते हैं $$$w$ शब्दकोश में पाया (एक अच्छा विचार नहीं है, क्योंकि शब्दकोश में सबसे अधिक संभावना सेवा के लिए विशिष्ट शब्दावली नहीं होगी) या, इसके विपरीत, शब्दकोश में पाए गए शब्द के साथ जोड़े को त्यागें (यही है, यह लगभग सील नहीं होने की गारंटी है)।

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

भाषा मॉडल

इसलिए, अब दिए गए शब्द w के लिए, हमें गणना करने की आवश्यकता है $$$पी (डब्ल्यू)$ - उपयोगकर्ता द्वारा इसके उपयोग की संभावना। किसी भी तरह के बड़े मामले में एक शब्द की घटना को लेना सबसे सरल उपाय है। सामान्य तौर पर, शायद, किसी भी भाषा का मॉडल ग्रंथों के एक बड़े कोष को इकट्ठा करने और उसमें शब्दों की घटना को गिनने के साथ शुरू होता है। लेकिन हमें खुद को इस तक सीमित नहीं करना चाहिए: वास्तव में, पी (डब्ल्यू) की गणना करते समय, हम उस वाक्यांश को भी ध्यान में रख सकते हैं जिसमें हम शब्द को सही करने की कोशिश कर रहे हैं, और कोई अन्य बाहरी संदर्भ। कार्य एक गणना कार्य में बदल जाता है $$$P (w_1w_2 \ ldots w_k)$ जहां से एक $$$w_i$ - जिस शब्द में हमने टाइपो को ठीक किया है और जिसके लिए अब हम गिनती कर रहे हैं $$$पी (डब्ल्यू)$ और बाकी $$$w_i$ - उपयोगकर्ता अनुरोध में सही शब्द के आसपास के शब्द।

उन्हें कैसे खाते में लेना है, यह जानने के लिए फिर से कोष के माध्यम से जाने और एन-ग्राम, शब्द अनुक्रमों के आंकड़ों को संकलित करने के लायक है। आमतौर पर सीमित लंबाई के अनुक्रम लेते हैं; मैंने अपने आप को ट्रिगर्स तक सीमित कर दिया ताकि सूचकांक को न बढ़ाया जाए, लेकिन यह सब आपके दिमाग की ताकत (और मामले के आकार - एक छोटे से मामले पर भी ट्रिगर्स पर आंकड़े बहुत शोर होगा) पर निर्भर करता है।

पारंपरिक एन-ग्राम भाषा मॉडल इस तरह दिखता है। वाक्यांश के लिए $$$w_1w_2 \ ldots w_k$ इसकी संभावना सूत्र द्वारा गणना की जाती है

$$

$$P (w_1w_2 \ ldots w_k) = P (w_1) \ cdot P (w_2 | w_1) \ cdot P (w_3 | w_1w_2) P (w_k | w_1w_2_ {k-1}) \ _,$$

जहाँ $$$P (w_1)$ - सीधे शब्द की आवृत्ति, और $$$P (w_3 | w_1w_2)$ - शब्द संभावना $$$w_3$ बशर्ते उसके जाने से पहले $$$w_1w_2$ - ट्रिग्राम फ्रीक्वेंसी के अनुपात के अलावा और कुछ नहीं $$$w_1 w_2 w_3$ to bigram फ्रीक्वेंसी $$$w_1 w_2$ । (ध्यान दें कि यह सूत्र केवल बार सूत्र के बार-बार उपयोग का परिणाम है।)

दूसरे शब्दों में, यदि हम गणना करना चाहते हैं $$$पी (\ पाठ {माँ साबुन फ्रेम})$ , एक मनमाने ढंग से n- ग्राम की आवृत्ति को दर्शाता है $$$च$ हमें सूत्र मिलता है

$$

$$P (\ पाठ {माँ साबुन फ्रेम}) = f (\ पाठ {माँ}) \ cdot \ frac {f (\ पाठ {माँ साबुन})}} {f (\ पाठ {माँ})}} \ cdot \ frac { f (\ text {साबुन के फ्रेम की माँ))} {f (\ text {माँ की साबुन})} = f (\ text {साबुन के फ्रेम की माँ)) \ _,।$$

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

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

$$

$$P (w_k | w_1w_2 \ ldots w_ {k-1}) \ लगभग P (w_k | w_ {k-L + 1} \ ldots w_ {k-1}) \,।$$

डाल $$$L = 3$ , एक लंबे वाक्यांश के लिए हमें सूत्र मिलता है


$$$P (\ पाठ {कार्ला ने क्लारा से कोरल}) चुरा लिया है) \ लगभग एफ (\ पाठ {कार्ल})} \ cdot \ frac {f (\ पाठ {कार्ल})}} {एफ (\ पाठ {कार्ल})} \ cdot \ frac {f (\ text {carl from clara})}} {f (\ text {carl from})}} \ cdot \ frac {f (\ text {क्लारा से चुराया})}} {f (\ text {clara} से) )} \ cdot \ frac {f (\ text {क्लेयर स्टोल कोरल})} {f (\ text {क्लेयर स्टोल})}},।$


कृपया ध्यान दें: वाक्यांश में पाँच शब्द हैं, लेकिन n- ग्राम अब सूत्र में तीन से अधिक नहीं है। यह वही है जो हमने मांगा था।

एक पतला सा पल बाकी था। क्या होगा यदि उपयोगकर्ता ने हमारे आंकड़ों में बहुत ही अजीब वाक्यांश और संबंधित एन-ग्राम दर्ज किया है और बिल्कुल नहीं? अपरिचित एन-ग्राम को डालना आसान होगा $$$f = 0$ यदि यह इस मूल्य से विभाजित करने के लिए आवश्यक नहीं है। यहाँ चौरसाई (चौरसाई) की सहायता से आता है, जिसे विभिन्न तरीकों से किया जा सकता है; हालाँकि, गंभीर विरोधी अलियासिंग दृष्टिकोणों की एक विस्तृत चर्चा जैसे कि कांसर-नेई स्मूथिंग इस लेख के दायरे से बहुत दूर है।

वाक्यांशों को सही कैसे करें

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

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

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

हमारे अभिभावक के कार्यान्वयन में, हमने इस दृष्टिकोण का उपयोग किया। हर शब्द के लिए चलो $$$s_i$ हमारे वाक्यांश में, त्रुटि मॉडल का उपयोग करके हम शीर्ष-एन शब्दकोश शब्द ढूंढते हैं जो कि हो सकता है, हम उन्हें हर संभव तरीके से और प्रत्येक के लिए वाक्यांशों में संक्षिप्त करते हैं। $$$एन ^ के$ जिसके परिणामस्वरूप वाक्यांश $$$K$ - मूल वाक्यांश में शब्दों की संख्या, ईमानदारी से मूल्य की गणना करें

$$

$$P (s_1 | w_1) \ cdot P (s_K | w_K) \ cdot P (s_K | w_K) \ cdot P (w_1w_2 \ ldots w_K) ^ {\ _dda} \ _।$$

यहां $$$s_i$ - उपयोगकर्ता द्वारा दर्ज शब्द, $$$w_i$ - उनके लिए चयनित सुधार (जो अब हम कर रहे हैं), और $$$\ lambda$ - त्रुटि मॉडल और भाषा मॉडल के तुलनात्मक गुणवत्ता द्वारा निर्धारित गुणांक (बड़े गुणांक - हम भाषा मॉडल पर अधिक भरोसा करते हैं, छोटे गुणांक - हम त्रुटि मॉडल पर अधिक भरोसा करते हैं), [4] में प्रस्तावित है। कुल मिलाकर, प्रत्येक वाक्यांश के लिए, हम संबंधित शब्दकोश वेरिएंट में सही होने के लिए अलग-अलग शब्दों की संभावनाओं को गुणा करते हैं, और हम इसे अपनी भाषा में पूरे वाक्यांश की संभावना से भी गुणा करते हैं। एल्गोरिथ्म का परिणाम शब्दकोश शब्दों से एक वाक्यांश है जो इस मूल्य को अधिकतम करता है।

तो बंद करो क्या? क्रूर बल $$$एन ^ के$ वाक्यांशों?

सौभाग्य से, इस तथ्य के कारण कि हमने एन-ग्राम की लंबाई को सीमित कर दिया है, सभी वाक्यांशों में अधिकतम तेजी से ढूंढना संभव है। याद रखें: ऊपर हमने इसके लिए सूत्र को सरल बनाया $$$P (w_1w_2 \ ldots w_K)$ इतना है कि यह केवल तीन से अधिक नहीं की लंबाई की n- ग्राम की आवृत्तियों पर निर्भर करने के लिए शुरू किया:

$$

$$P (w_1w_2 \ ldots w_K) = P (w_1) \ cdot P (w_2 | w_1) \ cdot P (w_3 | w_1w_2) \ cdot \ ldots \ cdot P (w_K। W_ {के -2) w_ {K-1 }),।$$

यदि हम इस मान को गुणा करें $$$P (s_i | w_i)$ और अधिकतम करने का प्रयास करें $$$w_K$ , हम देखेंगे कि यह सभी प्रकारों को छाँटने के लिए पर्याप्त है $$$w_ {K-2}$ और $$$w_ {K-1}$ और उनके लिए समस्या का समाधान - वह है, वाक्यांशों के लिए $$$w_1w_2 \ ldots w_ {K-2} w_ {K-1}$ । कुल मिलाकर, समस्या को डायनेमिक प्रोग्रामिंग द्वारा हल किया जाता है $$$O (KN ^ 3)$ ।

कार्यान्वयन

मामले को एक साथ रखना और एन-ग्राम की गिनती करना

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

एक शब्दकोश के रूप में, मैंने आवृत्ति में शीर्ष शब्दों को लिया ताकि मुझे लगभग एक लाख शब्द मिलें। बहुत लंबे शब्द (20 से अधिक वर्ण) और बहुत कम (तीन वर्णों से कम, हार्डकॉक्ड प्रसिद्ध रूसी शब्दों को छोड़कर) को बाहर रखा गया था। नियमित रूप से शब्दों पर अलग से बख्शा r"^[a-z0-9]{2}$" - ताकि आईफ़ोन के संस्करण और लंबाई 2 के अन्य रोचक पहचानकर्ता बच गए।

जब वाक्यांशों में बिग्रेड और ट्रिगर्स की गिनती होती है, तो एक गैर-शब्दकोश शब्द हो सकता है। इस मामले में, मैंने इस शब्द को फेंक दिया और पूरे वाक्यांश को दो भागों में (इस शब्द से पहले और बाद में) हराया, जिसके साथ मैंने अलग से काम किया। तो, वाक्यांश के लिए " क्या आप जानते हैं कि" अबीरवाल्ग "क्या है? यह है ... हेडमैन, सहकर्मी "क्या आप जानते हैं" "क्या आप जानते हैं," "आप क्या जानते हैं," "क्या है" और "यह मुख्य मछुआरा सहयोगी है" (जब तक, शब्द "हेडमैन शब्द शब्दकोश में गिर जाता है ...) को ध्यान में रखेगा।"

हम त्रुटि मॉडल को प्रशिक्षित करते हैं

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


संपादन की गणना स्वयं प्राथमिक लगती है, हालांकि इसमें लंबा समय लग सकता है।

त्रुटि मॉडल लागू करें

इस भाग को GRPC के माध्यम से मुख्य बैकएंड से जुड़े, गो पर एक माइक्रो सेवा के रूप में लागू किया गया है। मामूली अनुकूलन के साथ, खुद ब्रिल और मूर द्वारा वर्णित एल्गोरिथ्म को लागू किया गया है। यह मेरे लिए एक परिणाम के रूप में काम करता है, लगभग दो बार धीमा जितना लेखकों ने दावा किया; मैं यह निर्धारित नहीं करता कि यह गो में है या मुझमें। लेकिन प्रोफाइलिंग के दौरान, मैंने गो के बारे में थोड़ा नया सीखा।

• ज्यादा से ज्यादा गिनती करने के लिए math.Max का इस्तेमाल न करें। यह if a > b { b = a } की तुलना में लगभग तीन गुना धीमा है! इस फ़ंक्शन के कार्यान्वयन को देखें :
  

   // Max returns the larger of x or y. // // Special cases are: // Max(x, +Inf) = Max(+Inf, x) = +Inf // Max(x, NaN) = Max(NaN, x) = NaN // Max(+0, ±0) = Max(±0, +0) = +0 // Max(-0, -0) = -0 func Max(x, y float64) float64 func max(x, y float64) float64 { // special cases switch { case IsInf(x, 1) || IsInf(y, 1): return Inf(1) case IsNaN(x) || IsNaN(y): return NaN() case x == 0 && x == y: if Signbit(x) { return y } return x } if x > y { return x } return y } 

  
  जब तक कि आपको SUDDENLY +0 की आवश्यकता न हो, -0 से अधिक होनी चाहिए, math.Max उपयोग न करें।
  
• यदि आप किसी सरणी का उपयोग कर सकते हैं तो हैश तालिका का उपयोग न करें। यह, ज़ाहिर है, बहुत स्पष्ट सलाह है। मुझे प्रोग्राम की शुरुआत में यूनिकोड के पात्रों को संख्याओं में बदलना था, उन्हें ट्राइएड नोड के वंशज सरणी में सूचकांकों के रूप में उपयोग करना था (इस तरह की एक खोज एक बहुत ही सामान्य ऑपरेशन थी)।
  
• गो में कॉलबैक सस्ते नहीं हैं। कोड की समीक्षा के दौरान रिफैक्टिंग के दौरान, डिकॉउलिंग बनाने के मेरे कुछ प्रयासों ने इस तथ्य के बावजूद कार्यक्रम को धीमा कर दिया कि एल्गोरिथ्म औपचारिक रूप से नहीं बदला। तब से, मेरी राय है कि गो ऑप्टिमाइजिंग कंपाइलर के बढ़ने की गुंजाइश है।
  

भाषा मॉडल लागू करें

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

परिणाम

इस काम के परिणामों के आधार पर (जिसमें लगभग एक महीने का समय लगा), हमने अपने उपयोगकर्ताओं पर ए / बी परीक्षण गार्ड का संचालन किया। सभी खोज प्रश्नों के बीच खाली खोज परिणामों के 10% के बजाय जो हमारे पास अभिभावक की शुरूआत से पहले थे, उनमें से 5% थे; मूल रूप से, शेष अनुरोध उन सामानों के लिए हैं जिन्हें हम केवल प्लेटफॉर्म पर नहीं रखते हैं। दूसरी खोज क्वेरी के बिना सत्रों की संख्या भी बढ़ गई है (और UX से संबंधित इस तरह के कई और मैट्रिक्स)। धन से संबंधित मैट्रिक्स, हालांकि, काफी बदलाव नहीं हुआ - यह अप्रत्याशित था और हमें अन्य मैट्रिक्स के गहन विश्लेषण और क्रॉस-चेकिंग की ओर ले गया।

निष्कर्ष

स्टीफन हॉकिंग को एक बार कहा गया था कि वह पुस्तक में शामिल हर सूत्र पाठकों की संख्या को आधा कर देंगे। खैर, इस लेख में उनमें से लगभग पचास हैं - मैं आपको बधाई देता हूं, जिसके बारे में एक$$$10^{-10}$ पाठकों को इस जगह तक पहुँचना!

बोनस

संदर्भ

[१] एमडी केरनिघन, केडब्ल्यू चर्च, डब्ल्यूए गेल। एक शोर सुधार कार्यक्रम एक शोर चैनल मॉडल पर आधारित है । कम्प्यूटेशनल भाषाविज्ञान पर 13 वें सम्मेलन की कार्यवाही - खंड 2, 1990.

[2] ई। ब्रिल, आरसी मूर। शोर चैनल वर्तनी सुधार के लिए एक बेहतर त्रुटि मॉडल । कम्प्यूटेशनल भाषा विज्ञान, 2000 के लिए 38 वीं वार्षिक बैठक की कार्यवाही।

[3] टी। ब्रेंट, एसी पोपट, पी। जू, एफजे ओच, जे। डीन। मशीन अनुवाद में बड़ी भाषा मॉडल । प्राकृतिक भाषा प्रसंस्करण में अनुभवजन्य तरीकों पर 2007 सम्मेलन की कार्यवाही।

[४] सी। व्हिटेलॉ, बी। हचिंसन, जी वाई चुंग, जी एलिस। भाषा के लिए वेब का उपयोग करना स्वतंत्र वर्तनी जाँच और स्वत: सुधार। प्राकृतिक भाषा प्रसंस्करण में अनुभवजन्य विधियों पर 2009 सम्मेलन की कार्यवाही: खंड 2।