類似の文字列を見つけるために使用するデータ構造は何ですか？たとえば、文字列「hapyp brithdya」をGoogleに問い合わせると、以前はスペルミスのある「hapyp brithdya」とよく似た文字列「happy birthday」が表示されます。類似の文字列を見つけるために使用するデータ構造は何ですか？
この種の操作を実行するには、宇宙と時間の両方で最も効率的なデータ構造は何ですか？
助けてください。あなたの時間は非常に高く評価されています。
データ構造を求めるので、Levenshtein automataをお勧めします。
これらは、文字列の最も可能性の高い（コーパス統計に従って）訂正を返す確率的変形に拡張することができます。基本的な考え方については、GoogleのPeter Norvigによるエッセイ"How to Write a Spelling Corrector"を参照してください。これをLevenshtein automataと組み合わせるには、有限状態トランスデューサの知識が必要です。詳細は、Hassan, Noeman and Hassanを参照してください。
Googleが使用する学習メカニズムは検索履歴です。たとえば、私は "hapyp brithdya"を検索し、スペルが間違っていてリンクが選択されていないことに気付きました。私の次の検索は正しい綴りである "幸せな誕生日"です。そして、この一連の検索から、Googleは「hapyp brithdya」が実際に「幸せな誕生日」を意味することを理解することができます。
Googleが妥当な綴り修正をするのに役立つ同じ行に基づく別のスコアリングの仕組みは、「幸せな誕生日」を含むリンク（Google検索で提案されたリンク）でユーザーがクリックする「hapyp brithdya」を検索することです"これは、ユーザーが訪問しなかったリンクに存在していた「おしゃれな誕生日」と比較して、「幸せな誕生日」から「hapyp brithdya」への近接性を向上させます。
例では、彼らの手紙の順列によって。 「似ている」が実際には別の文字（「ハッピー」や「ハッピー」など）を使用している単語も探したいですか？ – huitseeker
はい、そうです。私はまた、 "幸せ"や "幸せ"のような言葉を手に入れたい –