問題タブ [levenshtein-distance]

私はあなた自身の質問に答える精神でこれを投稿しています。

私が抱えていた質問は、ここで説明されているように、2 つの文字列間の編集距離を計算するためのレーベンシュタイン アルゴリズムをDelphi でどのように実装できるかということでした。

パフォーマンスに関する注意: これは非常に高速です。私のデスクトップ (2.33 Ghz デュアルコア、2GB RAM、WinXP) では、100K 文字列の配列を 1 秒未満で実行できます。

Web サイトの 404 ページをカスタマイズしています。「もしかして…？」を入れてほしいです。これを行う方法を理解する必要があります。

これまでのところ、私が行っていることは次のとおりです。ユーザーが探している可能性のあるファイルの広範なリストを作成し、levenshtein() を使用して、考えられる各ファイル名をタイプミスされたファイル名と比較します。「もしかして」では、差が最も小さいものが選択されます。

metaphone()の使用も検討しましたが、やり過ぎかと思います。

「もしかして…？」に対して何を提案しますか？脚本？

これらの要件を満たすために、レーベンシュタインアルゴリズムを使用しています。

N文字の単語を見つけるとき、私の辞書データベースで修正として提案する単語は次のとおりです。

見つかった単語と1文字の違いがあるN文字のすべての辞書単語。例：見つかった単語：bearn、辞書の単語：bears

見つかった単語と等しいN文字を持つN+1文字のすべての辞書単語。例：見つかった単語：クマ、辞書の単語：クマ

見つかった単語と等しいN-1文字を持つN-1文字のすべての辞書単語。例：見つかった単語：クマ、辞書の単語：クマ

このC++でのレーベンシュタインアルゴリズムの実装を使用して、単語のレーベンシュタイン数が1（3つの場合すべてのレーベンシュタイン数）であるかどうかを調べていますが、提案する単語を選択するにはどうすればよいですか？Boyer-Moore-HorspoolとKnuth-Morris-Prattについて読みましたが、どちらがどのように役立つかわかりません。

さまざまなソースからの製品名（カメラ、ラップトップ、テレビなど）をデータベース内の正規名に自動的に一致させる必要があります。

たとえば、「Canon PowerShot a20IS」、「NEW powershot A20 IS from Canon」、「Digital Camera Canon PS A20IS」 は、すべて「CanonPowerShotA20IS」と一致する必要があります。私はいくつかのヒューリスティックを追加してレーベンシュタイン距離で作業しました（明白な一般的な単語を削除し、番号の変更により高いコストを割り当てるなど）。これはある程度機能しますが、残念ながら十分ではありません。

主な問題は、関連するキーワードを1文字だけ変更しても大きな違いが生じる可能性があることですが、関連するキーワードを特定するのは簡単ではありません。たとえば、次の3つの製品名を考えてみましょう
。LenovoT400
Lenovo R400
New Lenovo T-400、Core 2 Duo
最初の2つは、どの規格でもばかばかしいほど似た文字列です（この場合、soundexはTとRを区別するのに役立つかもしれませんが、名前は400Tと400Rも同様です）、1番目と3番目はストリングとして互いにかなり離れていますが、同じ製品です。

明らかに、マッチングアルゴリズムを100％正確にすることはできません。私の目標は、名前の約80％を高い信頼性で自動的にマッチングすることです。

任意のアイデアや参考文献は大歓迎です

次のようにスミスのテーブルを検索して、1つの分散内にあるすべてのものを取得できるようにしたいと思います。

データ：

レーベンシュタイン距離の使用を検討しましたが、これを実装する方法を知っている人はいますか？

プロファイリングは、これが私が書いた小さな単語ゲームのコードの最も遅いセグメントであることを示しています:

ノート：

• distance()は 500 万回以上呼び出されており、その大部分は getchildren からのもので、単語リスト内のword1 文字だけ異なるすべての単語を取得することになっています。
• wordlist は、同じ数の文字を含む単語のみを持つように事前にフィルター処理されているため、同じ数の文字を持つwordことが保証されます。word1word2
• 私は Python を初めて使用するので (3 日前に学習を開始しました)、命名規則やその他のスタイルに関するコメントも歓迎します。
• wordlistの場合、「2+2lemma.txt」ファイルを使用して12dict の単語リストを取得します

結果：

みんなありがとう、さまざまな提案を組み合わせて、プログラムを2倍の速度で実行できるようになりました（質問する前に自分で行った最適化に加えて、最初の実装から約4倍の速度が向上しました）

AとBと呼ぶ2セットの入力でテストしました

Optimization1: word1,2 ...のインデックスを反復処理します。

を使用して文字のペアを反復するzip(word1, word2)

入力 A の実行時間は 11.92 から 9.18、入力 B の実行時間は 79.30 から 74.59 になりました

Optimization2: distance-method に加えて、different-by-one の別のメソッドを追加しました (これは、A* ヒューリスティックのために他の場所でまだ必要でした)。

入力 A の実行時間は 9.18 から 8.83、入力 B の実行時間は 74.59 から 70.14 になりました

最適化 3: ここでの大きな勝者は、izip代わりに使用することでしたzip

入力 A の実行時間は 8.83 から 5.02 になり、入力 B の実行時間は 70.14 から 41.69 になりました

低レベル言語で書いたほうがいいかもしれませんが、今のところこれで満足しています。みんな、ありがとう！

もう一度編集: より多くの結果最初の文字が一致しないケースをチェックするマークの方法を使用して、5.02 -> 3.59 および 41.69 -> 29.82 からダウンしました。

それに基づいての代わりに組み込むiziprangeと、次のようになりました。

これにより、タイムが 3.59 -> 3.38 および 29.82 -> 27.88 に短縮されました。

さらに成果が！

「単語」から1文字離れたすべての文字列のリストを生成し、 is_neighbor 関数の代わりに wordlist にあるものを確認するというSumuduの提案を試してみると、次のようになりました。

最終的には遅くなりましたが (3.38 -> 3.74 および 27.88 -> 34.40)、有望に思えました。最初は、最適化する必要がある部分は「one_letter_off_strings」だと思っていましたが、プロファイリングではそうではなく、遅い部分は実際には

「oneoff」と「wordlist」を切り替えて、逆に比較すると、2 つのリストの共通点を探していることに気が付いたときに、何か違いがあるのではないかと考えました。それを文字の set-intersectionに置き換えます:

バム！3.74 -> 0.23 および 34.40 -> 2.25

これは本当に驚くべきことであり、元の素朴な実装との合計速度の差: 23.79 -> 0.23 および 180.07 -> 2.25 であり、元の実装よりも約 80 倍から 100 倍高速です。

誰かが興味を持っている場合は、プログラムを説明し、ここで言及されていないものを含めて行われた最適化について説明するブログ投稿を作成しました (コードの別のセクションにあるため)。

大論争：

わかりました、私と Unknown は大きな議論をしています。彼の回答のコメントで読むことができます。彼は、C に移植した場合、元の方法 (セットを使用する代わりに is_neighbor を使用) を使用した方が高速になると主張しています。thisとthisの例に従ってください。Windows ではプロセスが少し異なるように見えますか? わかりませんが、私はそれをあきらめました。とにかく、ここにプログラムの完全なコードがあり、テキストファイルは12dict 単語リストから来ています「2+2lemma.txt」ファイルを使用します。コードが少し乱雑で申し訳ありませんが、これは私が一緒にハッキングしたものです。また、単語リストからコンマを削除するのを忘れていたので、実際には同じ比較のためにそのままにしておくか、cleanentries の文字のリストにコンマを追加して修正できるバグです。

is_neighbors メソッドは使用されていませんが、残しました。これは、C への移植が提案されているメソッドです。これを使用するには、getchildren を次のように置き換えます。

Cモジュールとして動作させることに関しては、私はそこまで行きませんでしたが、これは私が思いついたものです:

私はこれを使用してプロファイリングしました：

python -m cProfile "Wordgame.py"

記録された時間は、AStar メソッド呼び出しの合計時間です。高速入力セットは「詩の詩人」であり、長い入力セットは「詩人の詩」でした。タイミングは明らかに異なるマシン間で異なるため、誰かがこれを試した場合は、プログラムそのままの結果と C モジュールの結果を比較してください。

PHP levenshtein関数を使用して文字列を比較することに成功しました。

ただし、位置が入れ替わった部分文字列を含む 2 つの文字列の場合、アルゴリズムはそれらをまったく新しい部分文字列としてカウントします。

例えば：

以下よりも共通点が少ないものとして扱われます。

私は、最初の 2つがより似ていることを確認したアルゴリズムを好みます。

位置が切り替わった部分文字列を編集とは異なるものとして識別できる比較関数を考え出すにはどうすればよいでしょうか?

私が考えた 1 つの可能なアプローチは、比較の前に、文字列内のすべての単語をアルファベット順に並べることです。これにより、単語の元の順序が比較から完全に除外されます。ただし、これの欠点は、単語の最初の文字だけを変更すると、1 文字を変更する場合よりもはるかに大きな混乱が生じる可能性があることです。

私が達成しようとしているのは、人に関する 2 つの事実 (フリー テキスト文字列) を比較し、これらの事実が同じ事実を示している可能性を判断することです。事実とは、たとえば、その人が通った学校、雇用主または発行者の名前などです。2 つのレコードは、同じ学校の綴りが異なっていたり、単語の順序が異なっていたり、余分な単語があったりする可能性があるため、それらが同じ学校を指していると推測するには、マッチングが多少あいまいである必要があります。これまでのところ、スペルミスに対しては非常にうまく機能していますが (私はこれに加えて metaphone に似た表音アルゴリズムを使用しています)、学校でよく見られる単語の順序を入れ替えると非常にうまく機能しません: "xxx college" vs 「○○大学」。

1) なぜこれらの行に 1 を追加するのですか?

この線

削除された/より短い単語の長さを考慮に入れる必要がありますか、それとも何か不足していますか?

2) また、コメントには削除と挿入が記載されています。低い値は削除された文字を表すため、両方の単語 (単語の長さを表す整数 j/i) で削除された文字をチェックしていると考えるのは正しいですか。

使用されているコードは次のとおりです (疑似コードであり、言語固有の問題がないため、このスレッドはどの言語カテゴリにもありません)。

http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq

「チャンク転置」を引用符で囲んだのは、専門用語がどうあるべきか、またはどのような用語であるべきかがわからないためです。プロセスの専門用語があるかどうかを知っているだけでも非常に役立ちます。

編集距離に関するウィキペディアの記事は、この概念に関する良い背景を示しています。

「チャンク転置」を考慮すると、

一致する必要があります

一致するよりも密接に

つまり、距離計算は、テキストの部分文字列がテキスト内で単に移動されたときに検出する必要があります。これは、一般的なレーベンシュタイン距離の公式には当てはまりません。

文字列の長さはせいぜい数百文字です。さまざまな形式の著者名または著者名のリストです。私は DNA シーケンシングを行っていません (ただし、行っている人はこのテーマについて少し知っていると思います)。