アルゴリズム要望：フリーテキストの単語に似た辞書のすべての単語を見つける

Question

約15万語のリストがあり、ユーザがフリーテキストを入力すると、システムは辞書から単語のリストを提示する必要がありますそれはフリーテキストの言葉に非常に近い。

たとえば、ユーザーは次のように入力します。「私はWalmartでlegoeのおもちゃを購入したい」と入力します。辞書に "Lego"、 "Car"、 "Walmart"が含まれている場合、システムは "Lego"と "Walmart"をリストに表示する必要があります。 "Walmart"は文中の単語と同一であるため明らかですが、 "Lego"は "Legoe"と似ています。しかし、 "Car"と似ていないので、その単語は表示されません。

リストがリアルタイムで表示される必要があります。つまり、ユーザーが文章を入力したときに、単語リストが画面に表示されている必要があります。誰もがこのための良いアルゴリズムを知っていますか？

辞書には、実際にはスペースを含む概念が含まれています。例えば、「レゴ宇宙船」。完璧なソリューションは、これらのマルチワードの概念も認識します。

ご迷惑をおかけして申し訳ございません。

Answer 1

簡単なアルゴリズムについてはhttp://norvig.com/spell-correct.htmlをご覧ください。この記事ではPythonを使用していますが、最後に他の言語の実装へのリンクがあります。

Answer 2

Levenshtein distanceのような2つの文字列の差の量を計算できるアルゴリズムを見るのは興味深いかもしれません。

私はどの言語を使用するか考えていませんが、PHPはlevenshteinという機能を持っており、この計算を実行し距離を返します。同様のことをするsimilar_textという関数もあります。可能な単語の辞書と単語をチェックし、最も近い単語を返す関数code example hereがlevenshteinにあります。

これは、ソリューションがどのように機能するかについて少し洞察を与えることを望みます。

Answer 3

Levenshtein distanceを計算するアルゴリズムを使用することをお勧めします。

しかし、あなたのデータセットはかなり大きいので、これに対して多くの単語を比較するので、これを行うtypical algorithmsの直接実装は実用的ではありません。

妥当な時間内に単語を見つけるには、何らかの方法で単語のインデックスを作成して、fuzzy string matchingを容易にする必要があります。

これらのインデックス作成方法の1つは、suffix treeを使用することです。別の方法は、n-gramsを使用することです。

サフィックスツリーを使用する方が、私の頭を包み込む方が簡単だと思っています。問題にもっと適していることがわかります。

Answer 4

固定ディクショナリに対して、かなりの数の検索が行われます。したがって、辞書を準備する必要があります。論理的には、「あまりにも異なる」候補者を迅速に排除することができます。例えば

、言葉carとdissimilarは接尾辞を共有するかもしれないが、彼らはお互いの明らかないスペルミスです。それでなぜ私たちは人間にそれほど明白ですか？まず、長さはまったく違う。それはすぐに失格となります（但し、下記の例外もあります）。だから、あなたの辞書は単語の長さでソートする必要があります。類似した長さの単語と入力単語を一致させます。 +/- 1文字を意味する短い単語については、

類似の長さの候補単語に制限したら、完全に異なる単語を除外したいと思うでしょう。これは、彼らが全く異なる手紙を使用していることを意味します。アルファベット順に並べ替えると、比較が簡単です。例えば。 carは"acr"となります。 rackは"ackr"になります。これは、辞書の前処理と入力単語ごとに行います。その理由は、2つのソートされたセットの差（サイズ）を決定することは安価です。 （説明が必要な場合は、コメントを追加してください）。 carとrackのサイズの差が1の場合、carとhatのサイズに2の差があります。これにより候補セットがさらに絞り込まれます。より長い言葉では、あまりにも多くの違いが見つかったときに早めに脱退することができます。例えば。 dissimilarとbiographyの合計の差は13ですが、長さ（8/9）を考慮すると、5つの差異が見つかった場合はおそらく救済できます。

これにより、ほぼ同じ文字を使用する候補語のセットが残され、ほぼ同じ長さになります。この時点で、より洗練されたアルゴリズムの使用を開始できます。入力単語ごとに150.000の比較を実行する必要はありません。

ここで、前述の長さ例外については、問題はgreencarのような「単語」にあります。それは実際には長さ8の単語とは一致しませんが、人間にとっては何が意味されているかははっきりしています。この場合、入力単語を任意のランダムな境界で壊すことはできず、両方の半分に対して追加のN-1の不正確な一致を実行することはできません。しかし、スペースが足りないことを確認することは可能です。すべての可能な接頭辞を検索するだけです。これは、辞書の同じ部分を何度も繰り返し使用するため効率的です。 ggr、gre、greeなどです。見つかったすべての接頭辞について、残りの接尾辞も辞書に含まれているかどうかを確認します。 reencar,eencar。入力語の両方の半分が辞書内にあるが、単語自体がそうでない場合、スペースがないとみなすことができます。