Clever Geek Handbook

リクエストの処理と分類。 パート3：タイプミスの修正

タイプミスは、読者を楽しませるのに役立つ場合があります。 検索エンジンはまだユーモアを評価することができず、エラーを入力した単語は混乱を招き、ユーザーを混乱させます。 これらの現象を防ぐために、タイプミスの自動「コレクター」があり、スペルチェッカーでもあります。



タイプミスを修正するためのさまざまなアプローチについてはすでに十分に書かれているので、この記事では既に知られていることを繰り返しませんが、スペルチェッカーをゼロから書く方法を示します-シンプルですが、非常に有能です。 必要なのは、正しい単語のリストと少しのC ++だけです。











ここで単語のリストを取りましたが、他の辞書でもかまいません。 プレフィックスツリー（別名Trie）に保存します。 これはややエキゾチックで 、完全に最適ではなく、むしろ危険ですが、おそらく最も簡潔な実装です： 



struct trie_t: map<char, trie_t> { }


trie_t



構造は、すべてのmap



メソッドを継承しmap



。 単語の文字はこのmap



のキーに書き込まれ、値は再び...を継承する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(); }


この関数では、正しく機能しますが、簡潔にするためにエラーが発生しています。 このような「明確な」検索は、とにかく役に立たなくなるため、修正しません。



ファジー検索



木を一種の複数の分岐した道路と考える場合、単語検索機能はこの道路を歩いている旅行者です。 旅行者にはルート（検索ワード）が与えられ、それに応じて、ノードからノードに移動し、渡されたルートの文字を消します。 文字が終わった場合、「一時停止標識」が表示されているかどうかを確認するために残ります。



旅行者は、いわば、一度にすべての方向に同時に送られると想像してください。 各フォークの各クローンは、誰かが最終的なストップ（つまり、ツリーの葉）に到達するまで、まったく同じように動作します。 旅行者の総数は、ツリーに書かれた単語の数と等しくなり、それぞれが独自の個別の軌跡をたどります。



それらのすべてが最初に同じ単語ルートを与えられたと仮定します。 各トランジションで、各旅行者は、以前と同様に、ルートのコピーで1文字を消します。 しかし、移行の実際の方向が取り消し線の文字と一致しない場合、旅行者は罰金を受け取ります。 その結果、旅の終わりに、誰もがいくらかの負債を抱えることになります。 この値を増やして並べ替え、すべてを一列に並べます。



検索語が辞書に存在する場合、1人の旅行者が罰なしに最後まで進みます-彼はソートされたリストの最初になります。 単語が辞書にない場合、リーダーは最小数の違反で道を進んだ人になります。



実際、これはほぼアルゴリズム全体です。 秘Theは、リーダーが移動したパスが特定の単語（またはタイプミスがない場合は単語自体）の最も近い修正であり、違反（指定されたルートからの逸脱）の数がタイプミスの数になることです。



始めるには



もちろん、道路をツリー、分岐点をノード、旅行者を仮説、ルートからの逸脱を編集操作と呼ぶ方が正しいでしょう。 しかし、彼らは何とか生きているので、そのままにしておきましょう。 旅行者に関するすべての情報を保存する構造を導入します。 



 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 ) {} };


以下がフィールドに保存されます。



したがって、旅行者は出発点にあります。 



 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 ];


運賃支払いでは、2つのオプションが可能です。 選択した方向が「一般線」と一致する場合、遷移は自由です。それ以外の場合は+1： 



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


さて、最初の一歩が踏み出されました。 一度に多くの最初のステップがあると言う方が正しいです-孤独な放浪者の代わりに、チーム全体が現れました： 



 typedef vector<rambler_t> team_t;


目的のために全員がポイントに達するまで、それまでチームを増やし、段階的に繰り返すだけです。 微妙な違いがあります。



単語の文字を別の文字に置き換えることに対応する上記の「間違った順番」は、タイプミスの種類の1つにすぎません。 削除と挿入の少なくとも2つがあります。



削除する



この状況は「支払われましたが、行きませんでした」： todo



から最初の文字を削除し、ペナルティを科しますが、移行を行わず、何も追加しません。 



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


その結果、 todo



からの手紙は途中で失われます。これは削除するのと同じです。



挿入



ここでは、逆に「所定の場所で実行」します。ツリーの奥深くに移動し、 done



に文字を追加しますが、 todo



からは何も削除しません。 



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


完了したレターは、計画の外に、どこからともなく現れます。これは、それを挿入することに相当します。



父と子



各ステップでは、世界の並列化、オブジェクトの数の増加があるため、旅行者のパラメーターを変更せずに、彼のイメージと肖像に新しいパラメーターを作成します。 次の関数はすべてを結合します。入力で旅行者を受け取り、指定されたルート、ツリーノードのキー、および上記の規則に従って旅行者の2つのベクトルを入力します。

team



ベクトルには、移動を続ける人と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 )); }




自然選択



そして、2番目のニュアンス：雪崩のようなプロセスの新規および新規参加者の各ステップでの生成は、非合理的に行動します。 木の上でぼんやりと群がっている群れは、うまく制御されていません。ほとんどの部分は役に立たず、リソースをむさぼり食います。 私たちは制限を導入し、彼らのために競争を手配します。



最初に、罰金の最大許容量を割り当て、それを超えたすべての人を捨て、所定のパスから離れすぎます。



第二に、遅れているすべての人々を遠くから落とします。 確かに、追放された部外者の間で、誰かがレースの最後にリーダーを追い越すかもしれないというリスクがありますが、最適化のために彼らはそれに耐えなければなりません。



遅れている人を識別するために、すべての人が成功する可能性、つまり、上限を超えても失格なく残りの道がカバーされる可能性を推定します。 チャンスは次のように推定されます。 



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


対数があるのはなぜですか？ どんなビットシフト？ なぜこのような機能があるのですか？ 説明しようとすることができます。 明らかに、すでに受け取った罰金の量が多ければ多いほど、終わりに達する可能性は低くなります。 また、サブツリー内の単語が多いほど、それらの中から少なくとも1つの適切な単語を見つける可能性が高くなります。 そして、すでに移動した経路の長さは、いわば「持久力」を証明しています。



私は認めざるを得ません、後者は非常に残酷なものです。 しかし、どのヒューリスティックでも、主なことは働くことです。 これは動作します。 そして、いずれにせよ、私たちは完成に近づいています。 罰金の最大額をmax_cost



、最大チームサイズをteam_size



としてteam_size



ます。



パイオニアをすべての道路の先頭に置きます： 



 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 );


パスを完了したnext_g



はleads



記録され、まだ到達していない人はnext_g



に分類されnext_g



。 私たちは彼らに到達する可能性がありますが、下降することはありません： 



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


そして、まだ先に進む人がいるまでこれを繰り返します。 ペナルティがmax_cost



超えたmax_cost



、および最高のteam_size



入力しなかった人は無視し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個の候補の制限と、指定された単語の長さの半分の最大偏差は、手動で選択しました。 このようなパラメーターを使用すると、アルゴリズムのパフォーマンスは1秒あたり約10ワードに



、



、







、



、



という言葉に対応しますが、



を



変えることはありません。



これですべてです。 始めましょう。 次に、タイプミスを修正するためのシンプルだが効果的なメカニズムの動作の例を示します。 



   2    3   3   3   2  2  2




彼のすべての結果が完璧というわけではありませんが、これは修正可能です。



旅の結果



多くの人が、インフォームドサーチの種類の1つであるA *アルゴリズム 、またはそのバリエーション-反復的な深化とメモリ制限を備えたA *アルゴリズムの説明で学んだと確信しています。 もちろん、説明されているアルゴリズムは、実際に戦闘で使用されるものに対する最初の大まかな近似にすぎません。



本物の戦闘スペルチェッカーは他に何ができるはずですか？

















副作用



最終的には、説明したアプローチの可能性について言及するのは間違いであり、タスクの範囲を超えてしまいます。















プログラムの全文はここにあります 。 このプログラムは、有名なナノスペルチェッカーのピーター・ノーヴィグよりもわずかに長いですが、性能においては劣らず、その能力で大幅に上回っています。



ご清聴ありがとうございました！



役に立たないリンク







ミハイル・ドリニン、

検索クエリチームリーダー


More articles:


All Articles