php - PHPでのlevenshtein/similar_textの高速化

Question

私は現在、similar_textを使用して、文字列を最大50,000のリストと比較していますが、比較の数が多いため、非常に低速です。約500の一意の文字列を比較するのに約11分かかります。

これを実行する前に、データベースをチェックして、過去に処理されたかどうかを確認します。これにより、最初の実行後は毎回、ほぼ瞬時に処理されます。

レーベンシュタインを使用すると少し速くなり、マニュアルに投稿されたレーベンシュタイン距離関数は面白そうだと思います。これを大幅に高速化できるものがありませんか？

Answer 1

結局、多くのチェックがあり、最後の手段としてそのうちの1つだけを使用したとしても、通過する必要のある文字列の数が両方とも遅すぎましたlevenshtein。similar_text

実験として、コードの一部をC＃に移植して、相互作用するコードよりもどれだけ高速になるかを確認しました。同じデータセットで約3分で実行されました。

次に、テーブルにフィールドを追加し、ダブルメタフォンPECL拡張機能を使用して各行のキーを生成しました。結果は良好でしたが、一部の数値が含まれているため、重複が発生しました。そうすれば、上記の関数をそれぞれ実行できたと思いますが、実行しないことにしました。

結局、私は最も単純なアプローチであるMySQLの全文を選択しました。これは非常にうまく機能しました。検出と修正は簡単ですが、場合によっては間違いがあります。また、約3〜4秒で非常に高速に実行されます。

Answer 2

similar_textおそらく、最初に文字列を完全に一致するかどうかを比較し（そして、長さが同じかどうかを最初に比較することによって）、より高価な呼び出しをスキップすることによって、いくつかのチェックを「短絡」させることができます。

@jasonが指摘したように、O（N ^ 3）アルゴリズムが良い選択になることは決してありません。

Answer 3

levenshteinオートマトン（距離のある文字列に一致するオートマトンk）を使用する場合、で一致するかどうかをチェックできますO(n)。ここnで、はチェックする文字列の長さです。オートマトンの構築にはがかかりますO(kn)。ここで、はベース文字列のk最大距離とn長さです。