अनुरोधों का प्रसंस्करण और वर्गीकरण। भाग तीन: टाइपिंग को सही करना

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

टाइपिंग को सही करने के विभिन्न तरीकों के बारे में पहले से ही बहुत कुछ लिखा जा चुका है, इसलिए इस लेख में मैं वह नहीं दोहराऊंगा जो पहले से ही ज्ञात है, लेकिन मैं दिखाऊंगा कि स्क्रैच करने वाले को खरोंच से कैसे लिखा जाए - सरल, लेकिन काफी सक्षम। जरूरत है कि सही शब्दों की एक सूची और सी ++ का एक सा है।





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

struct trie_t: map<char, trie_t> { } 

trie_t संरचना सभी map विधियों को विरासत में मिली है। इस map की कुंजियों में शब्दों के अक्षर लिखे गए हैं, और मान फिर से trie_t संरचनाएं हैं जो विरासत में trie_t ... और इसी तरह। थोड़ा ध्यान से, लेकिन एक प्रोटोटाइप के लिए यह करेगा।

संरचना में नोड का वजन जोड़ें, यह बाद में काम में आएगा:

 struct trie_t: map< char, trie_t > { size_t w; trie_t() : w(0) {} } 

हम इस फंक्शन का उपयोग करके पेड़ों में शब्द लिखेंगे:

 trie_t & add( trie_t & t, const string & s ) { t.w++; return !s.empty() ? add( t[ s[0] ], s.substr(1) ) : t['$']; } 

यह इस तरह से काम करता है: हम शब्द के पहले चरित्र को लेते हैं, इसे मानचित्र कुंजी में लिखते हैं, हमें संबंधित सबट्री के लिए एक लिंक मिलता है (यदि आवश्यक हो, तो इसे तुरंत बनाया जाता है)। इस रेखा में शेष रेखा को पुन: लिखें। जब लाइन समाप्त हो जाती है, तो अंतिम नोड में एक "स्टॉप साइन" - एक खाली सबट्री के साथ कुंजी ' $ ' जोड़ें।

दिए गए फ़ाइल से शब्दों को पढ़ने के बाद, हम उन सभी को शब्दकोश में दर्ज करेंगे:

 trie_t glossary; ifstream fi( argv[1] ); string word; while( getline( fi, word ) ) add( glossary, word ); 

परिणामस्वरूप, पेड़ के प्रत्येक नोड के w क्षेत्र में, इस नोड से गुजरने वाले शब्दों की संख्या दर्ज की जाएगी।

इस सब के साथ क्या किया जा सकता है? आप पेड़ की सामग्री को इनहेरिट किए गए पुनरावृत्त के साथ प्रत्येक नोड की कुंजियों और उपप्रकारों के माध्यम से छाँट सकते हैं:

 void print( const trie_t & t, const string & prefix = "" ) { for( map<char, trie_t>::const_iterator it = t.begin(); it != t.end(); ++it ) if ( it->first == '$' ) cout << prefix << endl; else print( it->second, prefix + it->first ); } 

आप पेड़ में दिए गए शब्द की उपस्थिति या अनुपस्थिति को निर्धारित कर सकते हैं:

 bool is_known( trie_t & t, const string & s ) { return !s.empty() ? is_known( t[ s[0] ], s.substr(1) ) : t.find('$') != t.end(); } 

इस फ़ंक्शन में, हालांकि यह सही ढंग से काम करता है, संक्षिप्तता के लिए एक त्रुटि बनाई गई है। मैं इसे सही नहीं करूंगा, क्योंकि इस तरह की "स्पष्ट" खोज अब हमारे लिए उपयोगी नहीं होगी।

फजी खोज

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

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

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

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

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

शुरू करने के लिए

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

 struct rambler_t { string todo; string done; size_t cost; const trie_t * road; rambler_t( const string & t, const string & d, const size_t c, const trie_t * r ) : todo( t ), done( d ), cost( c ), road( r ) {} }; 

निम्नलिखित क्षेत्रों में संग्रहीत किया जाता है:

• todo जाने का रास्ता है। प्रारंभ में, यह वही यात्रा मार्ग है, जो कि सही शब्द है। आखिर में एक खाली लाइन है।
• done - पथ का पारित भाग। शुरुआत में - एक खाली रेखा, अंत में - पास की गई नोड्स की एक सूची, जो कि, एक सही शब्द है।
• cost - जुर्माना की राशि। शुरू में - शून्य, अंत में - यह कैसे जाता है।
• road - यात्री का स्थान। शुरुआत में - पेड़ की जड़, अंत में - पत्तियों में से एक।

तो, यात्री शुरुआती बिंदु पर है, आप जा सकते हैं:

 rambler_t R( word, "", 0, &glossary ); 

पहला कदम

शब्दकोश प्रिंट करते समय पहले से उपयोगी उपयोगी सभी निर्देशों को छाँटा जा सकता है:

 for( map<char, trie_t>::const_iterator it = R.road->begin(); it != R.road->end(); ++it ) { char dest = it->first; //   const trie_t * road = it->second; //   //     } 

चरण पूरा करने के बाद, संरचना क्षेत्रों के मूल्य निम्नानुसार बदल जाएंगे:

 R.done = R.done + dest; R.todo = R.todo.substr(1); R.road = R.road[ dest ]; 

किराया भुगतान के साथ, दो विकल्प संभव हैं। यदि चयनित दिशा "सामान्य रेखा" से मेल खाती है, तो संक्रमण मुक्त है, अन्यथा +1:

 R.cost = R.cost + ( dest == todo[0] ? 0 : 1 ); 

ठीक है, पहला कदम उठाया गया है। यह कहना अधिक सही है कि एक ही बार में कई पहले चरण होते हैं - एक अकेला पथिक के बजाय, एक पूरी टीम दिखाई दी:

 typedef vector<rambler_t> team_t; 

यह केवल कदम से कदम को दोहराने के लिए बनी हुई है, टीम को तब तक बढ़ाती है, जब तक कि हर कोई उद्देश्य के लिए अपनी बात पर नहीं पहुंचता है ... स्टॉप। एक अतिशयता है, और एक नहीं।

ऊपर वर्णित "गलत मोड़", दूसरे अक्षर के साथ एक शब्द के एक अक्षर को बदलने के लिए इसी प्रकार, टाइपो की किस्मों में से एक है। कम से कम दो और हैं: हटाएं और डालें।

निष्कासन

यह स्थिति "भुगतान की गई है, लेकिन चली नहीं गई": हम पहले पत्र को todo से हटाते हैं, हम अपने आप को ठीक करते हैं, लेकिन हम परिवर्तन नहीं करते हैं और कुछ भी नहीं करते हैं।

 R.done = R.done; R.todo = R.todo.substr(1); R.road = R.road; R.cost = R.cost + 1; 

नतीजतन, todo से पत्र बस रास्ते से खो जाता है, जो इसे हटाने के बराबर है।

डालने

यहां, इसके विपरीत, "जगह में चल रहा है": हम पेड़ में गहराई से चलते हैं, किए गए पत्र को जोड़ते हैं, लेकिन todo से कुछ भी नहीं हटाते हैं।

 R.done = R.done + dest; R.todo = R.todo; R.road = R.road[ dest ]; R.cost = R.cost + 1; 

पूर्ण किया गया पत्र योजना से बाहर कहीं नहीं दिखाई देता है, जो इसे सम्मिलित करने के बराबर है।

पिता और बच्चे

चूंकि प्रत्येक चरण में दुनिया के कुछ समानांतरकरण होते हैं, वस्तुओं की संख्या में वृद्धि होती है, हम यात्री के मापदंडों को संशोधित नहीं करेंगे, लेकिन उनकी छवि और समानता में नए लोगों का निर्माण करेंगे। निम्नलिखित फ़ंक्शन सब कुछ एकजुट करता है: यह इनपुट पर एक यात्री को प्राप्त करता है, दिए गए मार्ग के अनुसार यात्रियों के आउटपुट दो वैक्टर में भरता है, ट्री नोड की कुंजी और ऊपर वर्णित नियम।
team वेक्टर में वे लोग शामिल हैं जो आगे बढ़ना जारी रखेंगे, और जो finished गए हैं वे वेक्टर में finished , अर्थात, जिनके todo खाली हैं और वर्तमान ट्री नोड में शब्द के अंत में अंकन हैं।

 void step_forward( const rambler_t & R, team_t & team, team_t & finished ) { char next = R.todo[0]; //  const string & todo = next ? R.todo.substr(1) : ""; for( map<char, trie_t>::const_iterator it = R.road->begin(); it != R.road->end(); ++it ) { const trie_t * road = &it->second; //  char dest = it->first; //  if ( next == dest ) team.push_back( rambler_t( todo, //    R.done + dest, R.cost, road )); else { team.push_back( rambler_t( todo, //  R.done + dest, R.cost + 1, road )); team.push_back( rambler_t( R.todo, //  R.done + dest, R.cost + 1, road )); if ( !next && dest == '$' ) finished.push_back( R ); // ! } } if ( next ) team.push_back( rambler_t( todo, //  R.done, R.cost + 1, R.road )); } 

प्राकृतिक चयन

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

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

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

जो लोग पिछड़ रहे हैं, उनकी पहचान करने के लिए, हम सभी के सफल होने की संभावनाओं का अनुमान लगाएंगे, अर्थात, शेष राशि अधिकतम राशि से अधिक के लिए अयोग्यता के बिना कवर की जाएगी। मौका का अनुमान इस प्रकार होगा:

 double ramb_chances( const rambler_t & a ) { return log( ( a.road->w + 1 ) * ( a.done.size() + 1 ) ) / ( 1 << a.cost ); } 

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

मुझे स्वीकार करना चाहिए, बाद वाला बहुत क्रूर है। लेकिन किसी भी अनुमान में, मुख्य बात काम करना है। यह काम करता है। और, एक रास्ता या कोई अन्य, हम पूरा होने जा रहे हैं। अधिकतम राशि जुर्माना को max_cost रूप में max_cost , टीम के रूप में अधिकतम टीम का आकार।

सभी सड़कों की शुरुआत में अग्रणी रखें:

 team_t walkers, leads; walkers.push_back( rambler_t( word, "", 0, &glossary ) ); 

हम एक कदम उठाते हैं, अगली "पीढ़ी" उत्पन्न करते हैं:

 team_t next_g; for( size_t i = 0; i < walkers.size(); ++i ) step_forward( walkers[i], next_g, leads ); 

leads लोगों ने अपना रास्ता पूरा कर लिया leads , next_g leads में दर्ज किए जाते हैं, जो अभी तक नहीं पहुंचे हैं, next_g में next_g । हम उनके अभी तक नहीं उतरने की संभावना की तरह है:

 sort( next_g.begin(), next_g.end(), ramb_chance_cmp ); 

और हम यह सब तब तक दोहराते हैं जब तक कि कोई आगे बढ़ना बाकी है। हम उन लोगों को नज़रअंदाज़ करते हैं जिनकी पेनल्टी max_cost अधिक max_cost , और जिन्होंने सर्वश्रेष्ठ team_size प्रवेश नहीं किया:

 while ( !walkers.empty() ) { team_t next_g; for( size_t i = 0; i < min( walkers.size(), team_size ); ++i ) if ( walkers[i].cost < max_cost ) step_forward( walkers[i], next_g, leads ); walkers.swap( next_g ); sort( walkers.begin(), walkers.end(), ramb_chance_cmp ); } 

वैसे, leads में एक ही done लाइनों के साथ कई संरचनाएं हो सकती हैं। लगता है कि वे कहाँ से आते हैं?
हम केवल अनन्य तत्व छोड़ेंगे:

 sort( leads.begin(), leads.end(), ramb_done_cmp ); //   done leads.resize( distance( leads.begin(), unique( leads.begin(), leads.end(), ramb_uniq ) ) ); //   sort( leads.begin(), leads.end(), ramb_chance_cmp ); //   

यह लगभग सभी है।

उपरोक्त सभी को spellcheck फ़ंक्शन में जोड़ें, हमारे शब्द को इसमें पास करें, अधिकतम जुर्माना और उम्मीदवारों की संख्या। आप उपयोग कर सकते हैं:

 while( getline( cin, word ) ) { team_t fixed = spellcheck( word, word.size()/2, 512 ); cout << word << endl; for( size_t i = 0; i < fixed.size(); ++i ) cout << '\t' << fixed[i].done << ' ' << fixed[i].cost << endl; cout << endl; } 

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

अब बस इतना ही। चलिए शुरू करते हैं। और यहाँ टाइपो को सही करने के लिए हमारे सरल लेकिन प्रभावी तंत्र के काम का एक उदाहरण है:

   2    3   3   3   2  2  2 

यह देखा जा सकता है कि उसके सभी परिणाम सही नहीं हैं, लेकिन यह निश्चित है।

यात्रा के परिणाम

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

एक असली मुकाबला करने वाले को क्या करना चाहिए?

• हमारे संदर्भ शब्दकोश में, केवल शब्दों के प्रारंभिक रूप मौजूद हैं, जिससे वह को को सही करता है, जो गलत है। किसी को आकृति विज्ञान की समझ होनी चाहिए, या शब्दकोश में शब्दों के सभी रूपों को शामिल करना चाहिए। पहला बेहतर है, लेकिन कठिन है।

• सभी शब्द समान हैं। यह सर्वश्रेष्ठ परिकल्पना को चुनने में अशुद्धियाँ पैदा करता है:
  

     1  1 

  यदि हम शब्दों के उपयोग की आवृत्ति के बारे में जानकारी जोड़ते हैं तो समस्या हल हो जाएगी।

• सभी त्रुटियां समान हैं। यहाँ से ऐसे अनिश्चित परिणाम आए:
  

     1  1 

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

• "पुंटो स्विचिंग।" यहां सब कुछ सरल है। हम प्रपत्र q- , w- , a- और एक अन्य प्रकार के टाइपो के एक पत्राचार तालिका को जोड़ते हैं - एक लेआउट परिवर्तन। हो गया।

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

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

साइड इफेक्ट

अंत में, वर्णित दृष्टिकोण की संभावनाओं का उल्लेख नहीं करना गलत होगा जो हमारे कार्य के दायरे से परे हैं।

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

• यदि हम वर्णों के ध्वन्यात्मक पत्राचार के कार्यक्रम तालिकाओं में डालते हैं, तो हमें अस्पष्टता की किसी भी डिग्री की लिप्यंतरण मान्यता प्रणाली मिलती है। एल्गोरिथ्म में सबसे अधिक संभावना वाला शब्द मिलेगा।
  

    → j, zh, g, dj j → , , ,  ... 

• संख्याओं और पत्रों के पत्राचार द्वारा निर्दिष्ट नियमों के अनुसार पेड़ पर संक्रमण एक टी 9 सेट सिस्टम में वर्तनी जांचक को बदल देगा:
  

    2 →  ... 9 →  

• त्रुटि की लागत, टाइपो की संभावनाओं पर गणना नहीं की गई, लेकिन विशेष रूप से कुंजी (या बल्कि, टच स्क्रीन पर उनकी छवियां) के बीच की दूरी पर "चलती" शब्द इनपुट - स्वाइप की प्रणाली के आधार के रूप में कार्य करता है।

• फ़ज़ी सर्च का कार्य भाषण मान्यता प्रणालियों, हस्तलिखित ग्रंथों का हिस्सा है ... हालाँकि, पर्याप्त है। इस बारे में पहले ही बहुत कुछ लिखा जा चुका है।

कार्यक्रम का पूरा पाठ यहां पाया जा सकता है । कार्यक्रम प्रसिद्ध नेनोस्पेलचर पीटर नॉरविग की तुलना में थोड़ा लंबा है, लेकिन यह प्रदर्शन में हीन नहीं, बल्कि अपनी क्षमताओं में इसे पार करता है।

आपका ध्यान के लिए धन्यवाद!

बेकार के लिंक

• प्रेरणा का स्रोत: क्वेरी पूर्णता के लिए ऑनलाइन वर्तनी सुधार
• पीटर नॉरविग से दुनिया का सबसे छोटा जादूई
• शब्द "सहपाठियों" को लिखने के 1200 तरीके - का उपयोग त्रुटि मॉडल की गणना करने के लिए किया जा सकता है
• वैकल्पिक दृष्टिकोण: एक , दो , तीन

मिखाइल डोलिनिन,
खोज क्वेरी टीम लीडर