PHPでのlevenshtein / similar_textの高速化

Question

現在 similar_text を使用して文字列を比較しています〜50,000のリストは機能しますが、比較の数が非常に遅いためです。 500個までの一意の文字列を比較するのに約11分かかります。

これを実行する前に、データベースが過去に処理されたかどうかを確認するため、最初の実行後は毎回ほぼ瞬時に処理されます。

levenshtein を使用すると、わずかに高速になり、マニュアルに投稿されたLevenshteinDistance関数は面白そうです。これを大幅に高速化できるものがありませんか？

Answer 1

最終的に、 levenshtein と similar_text の両方は、多くのチェックを行って1つだけを使用しても、通過する必要がある文字列の数が両方とも遅すぎました最後の手段としてそれらの。

実験として、コードの一部をC＃に移植して、コードがどの程度高速になるかを確認しました。同じデータセットで約3分で実行されました。

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

最後に、最も簡単なアプローチであるMySQLのフルテキストを選択しました。検出と修正は簡単ですが、ときどき間違いがあります。また、約3〜4秒で非常に高速に実行されます。

Answer 2

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

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

Answer 3

レベンシュタインオートマトン（距離 k の文字列に一致するオートマトン）を使用する場合、 O（n）で一致を確認できます。ここで n は、チェックする文字列の長さです。オートマトンを作成するには、 O（kn）を使用します。 k はベース文字列の最大距離と n の長さです。