問題タブ [levenshtein-distance]

私はレーベンシュタインの距離に精通しているので、UVA の Edit Steps Ladder 問題を解決するためにそれを使用することにしました。

私の解決策は次のとおりです。

この入力で：

このサンプルの正しい出力が生成されます。

裁判官は私の回答を却下しています。これは、オンライン ジャッジの問題を解決するための私の最初の試みであり、おそらくここで正しい答えを強制していると思います。

レーベンシュタインで単純に計算すると、maxEdit の値は 4 になるためです。それは何が起こっているのですか？

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

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

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

私はそのようなアルゴリズムを探していますが、文字間ではなく単語間で置換を行うアルゴリズムです。そのようなアルゴリズムはありますか？

SQL Server での実装を探していますが、アルゴリズムの名前で十分です。

2 つの文字列間の文字列の類似性を見つけたい。このページには、それらのいくつかの例があります。Python にはレーベンシュタイン アルゴリズムが実装されています。これらの制約の下で、より優れたアルゴリズム (およびできれば Python ライブラリ) はありますか。

1. 文字列間のあいまい一致を実行したい。たとえば、matches('Hello, All you people', 'hello, all you people') は True を返す必要があります
2. 偽陰性は許容されますが、非常にまれなケースを除いて、偽陽性は許容されません。
3. これは非リアルタイム設定で行われるため、速度は (あまり) 重要ではありません。
4. [編集] 複数の単語の文字列を比較しています。

私の場合、レーベンシュタイン距離(またはレーベンシュタイン比)以外の何かがより良いアルゴリズムでしょうか?

ドキュメントの剽窃を検出するために、damerau leveshtein 距離アルゴリズムをシミュレートするにはどうすればよいですか? ありがとう！

「n」個の単語の辞書があり、応答する「m」個のクエリがあります。編集距離が 1 または 2 である辞書内の単語数を出力したい。n と m がおよそ 3000 であることを考慮して、結果セットを最適化したい。

以下の回答から追加された編集：

私はそれを別の言葉で表現しようとします。

最初に、一連の Dictionary 単語として指定された 'n' 個の単語があります。次の 'm' 個の単語がクエリ単語として与えられ、クエリ単語ごとに、その単語が辞書に既に存在するか (編集距離 '0')、または編集距離 1 にある辞書内の単語の総数を見つける必要があります。 2 辞書の言葉から。

質問が明確になったことを願っています。

そうですね、時間計算量が (m*n)n の場合はタイムアウトになります。単純に DP Edit Distance Algorithm を使用するとタイムアウトになります。2k+1 の対角要素を計算しても、上記の場合は k=3 のしきい値である場合にタイムアウトになります。

LD = レーベンシュタイン距離

紙の上でいくつかの例を実行するだけで、これは機能しているように見えますが、これが常に正しいかどうかは誰にもわかりませんか?

3つの文字列があるとしましょう

ボット

ボブ

部品表

LD(ボット、ボブ) = 1

と

LD(BOB,BOM)=1

それから

LD(BOT,BOM)=max(LD(BOT,BOB),LD(BOB,DOM))=1

また

バアブ

BBAB

BCCD

LD(BBAB、BAAB) = 1

と

LD(BBAB,BCCD)=3

それから

LD(BAAB、BCCD)=max(LD(BBAB、BAAB)、LD(BBAB、BCCD))=3

これが常に当てはまるかどうか知りたいです。

あれは、

LD(B,C) = 最大 (LD(A,C),LD(A,B))

編集 -- 2009 年 10 月 22 日午後 7:08 PST に追加

これは同じ長さの単語にも当てはまると思い始めています。それ以外の場合は引き続き実行できますが、単語の長さの差の絶対値を追加する必要があります。

本質的に LD(B,C) = max(LD(A,C),LD(A,B)) + abs(長さ(B)-長さ(C))

Apache の Solr 検索エンジンは、たとえばレーベンシュタイン アルゴリズムを介して、おおよその文字列一致を提供しますか?

姓で顧客を検索する方法を探しています。ただし、名前の正確性は保証できません。「Levenstein」を検索しても「Levenshtein」という人物が見つかるように Solr を構成するにはどうすればよいですか?