問題タブ [edit-distance]

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

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

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

これは、CS 担当者が理論で輝くための演習です。

要素を含む 2 つのコンテナがあるとします。フォルダ、URL、ファイル、文字列、それは本当に問題ではありません。

追加と削除を計算するANアルゴリズムとは何ですか?

注意: この問題を解決する方法が多数ある場合は、回答ごとに 1 つの方法を投稿して、分析して投票できるようにしてください。

編集：すべての回答は、4つのコンテナで問題を解決します。頭の2つだけでも使えますか？

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

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

例えば：

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

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

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

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

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

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

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

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

一致する必要があります

一致するよりも密接に

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

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

データ構造プロジェクトの場合、一度に1文字だけ変更して、 2つの単語（"cat"となど）の間の最短経路を見つける必要があります。"dog"パスを見つけるために使用するスクラブルの単語リストが提供されます。例えば：

幅優先探索を使用して問題を解決しましたが、より良いものを探しています（辞書をトライで表現しました）。

より効率的な方法（速度とメモリの観点から）についていくつかアイデアを教えてください。ばかげているおよび/または挑戦的な何かが好ましい。

私は友人の一人（彼は後輩です）に尋ねました、そして彼はこの問題に対する効率的な解決策はないと言いました。彼は、私がアルゴリズムのコースを受講したときに、その理由を学ぶと言いました。それについて何かコメントはありますか？

私たちは言葉から言葉へと移動しなければなりません。行くことはできませんcat -> dat -> dag -> dog。トラバーサルも印刷する必要があります。

10,000 個の電子メール アドレスのリストがあり、このリスト内の最も近い "隣人" を見つけたいとします。これは、リスト内の他の電子メール アドレスに疑わしいほど近い電子メール アドレスとして定義されます。

2 つの文字列間のレーベンシュタイン距離を計算する方法を認識しています ( this questionのおかげで)。これにより、ある文字列を別の文字列に変換するために必要な操作の数のスコアが得られます。

「別の電子メールアドレスに疑わしいほど近い」を、レーベンシュタインスコアが N 未満の 2 つの文字列として定義するとします。

可能なすべての文字列をリスト内の他のすべての文字列と比較する以外に、スコアがこのしきい値よりも低い文字列のペアを見つけるより効率的な方法はありますか? 言い換えれば、この種の問題は よりも早く解決できるO(n^2)でしょうか?

レーベンシュタイン スコアは、この問題のアルゴリズムとして不適切な選択ですか?

オブジェクトのbase64エンコーディングの変更を検出して、オブジェクトの変更の程度を検出することは可能ですか。

ドキュメントの添付ファイルを複数のユーザーに送信し、それぞれが変更を加えてメールで返信するとします。元のbase64と受信したbase64の間の文字列距離を使用して、最も変更が多いバージョンを検出できますか。それは有効な指標でしょうか？

そうでない場合、デルタを定量化するための他のメトリックはありますか？

レーベンシュタイン距離を使用して、ユーザーが入力したものに最も近い結果を判別するストアドプロシージャがあります。速度に実際に影響するのは、距離が最も短いレコードを選択する前に、すべてのレコードのレーベンシュタイン距離を計算する関数だけです（これは、レーベンシュタイン関数の呼び出しの代わりに0を付けることで確認しました）。テーブルには150万のレコードがあるため、わずかな調整でも数秒短縮される可能性があります。現在、すべてが10分以上実行されています。これが私が使用している方法です：

ここからどこへ行けばいいの？

重複の可能性：
このダメラウ・レーベンシュタインの実装のバグを修正するにはどうすればよいですか？

ダメラウ・レーベネンシュテインの編集距離計算を行う次のCythonコード（bpbioプロジェクトから採用）があります。

コードは正常かつ高速に実行されます（私のPCでは1秒あたり300,000 ... 400,000の比較）。

課題は、このコードをUnicode文字列でも機能させることです。Python 3.1を実行していて、データベースからテキストを取得し、クエリテキストと照合します。

比較のためにCython関数に渡す前に、これらの文字列をエンコードするbytesことはお勧めできません。パフォーマンスが大幅に低下し（テスト済み）、7ビットのUSASCII以外の文字を含むテキストの結果が正しくない可能性があるためです。

（非常に簡潔な）Cythonマニュアルにはユニコード文字列が記載されていますが、目前の問題にはほとんど役立ちません。

私が見ているように、ユニコード文字列は、それぞれが単一のコードポイントを表す整数の配列として考えることができ、上記のコードは基本的にcharすでにsの配列で動作しているので、 （1）それを拡張する必要があると思います整数のC配列を処理するため。（2） Pythonユニコード文字列をC配列に変換するコードを追加します。（3）利益！

（ 注： このアプローチには2つの潜在的な問題があります：1つはユニコード代理文字の処理ですが、私はそれらをどうするか知っていると思います。もう1つの問題は、ユニコードコードポイントが実際には文字の概念に1：1でマッピングされないことです'。私はそれをよく知っていますが、この質問の範囲外だと思います。1つのUnicodeコードポイントが1つの比較単位であると想定してください。）

だから私はどのように提案を求めています

• unsigned intPythonユニコード文字列を受け入れてCythonのC配列（4バイト）を返す高速Cython関数を記述します。

• これらの配列を処理し、正しいメモリ割り当て/割り当て解除を行うように示されているコードを変更します（これは私にとってかなり異質なことです）。

編集：ジョン・マチンchar *m1は、奇妙なタイプキャストなどはおそらく速度やメモリの最適化のために行われていると指摘しています。これらの変数は、引き続き数値の配列として扱われます。私は、コードが長い文字列で起こりうるオーバーフローを防ぐために何もしていないことに気づきました。1つの配列要素が127または255を超えると、誤った結果が発生する可能性があります（使用するCコンパイラによって異なります）。バイオインフォマティクスプロジェクトからのコードには、ある種驚くべきものがあります。

とは言うものの、私が興味を持っているのは、ほぼ100文字未満のほぼ同一の文字列の正確な結果だけです。60％未満の同一性の結果は、私の目的では「完全に異なる」（長いテキストの長さを返すことによって）として安全に報告される可能性があるため、char *m1キャストをそのままにしておくのが最善だと思いますが、オーバーフローをチェックするためのコードを追加します横行する非類似性の場合の早期中絶。

私は別の長い質問で戻ってきました。PythonベースのDamerau-Levenshtein編集距離の実装をいくつか試した結果、最終的に以下にリストされているものが見つかりましたeditdistance_reference()。正しい結果が得られ、効率的に実装されているようです。

そこで、コードをCythonに変換することにしました。私のテストデータでは、参照メソッドは11,000回の比較（12文字の長さの単語のペアの場合）の結果を提供しますが、Cythonizedメソッドは1秒あたり200,000回を超える比較を実行します。残念ながら、結果は正しくありません。デバッグ用に出力した変数を見ると、thisrow どのデータをスローしても、私のバージョンでは変数がいっぱいになっていますが、参照出力には別の画像が表示されます。たとえば、'helo'に対してテストすると'world' 、次の出力が生成されます（ED私の関数をマークEDRし、正しく機能する参照です）。

差出人editdistance()：

からeditdistance_reference()：

エラーはおそらくそれらの非常に明白なものの1つであるため、私は非常に愚かである必要があります。しかし、私はそれを見つけることができないようです。

2番目の問題がありmallocます。3つの配列、、、およびのスペースtwoagoがoneagoあれthisrowば、それらは循環的に入れ替わります。などを実行しようとするfree( twoago )と、glibcが文句を言う行が表示されdouble free or corruptionます。私はそれをグーグルで検索しました。ポインタ交換ビジネスによってglibcが少しめまいを起こし、メモリを正しく解放できなくなる可能性がありますか？

以下に、最初にsetup.pyコンパイル（）を実行するために必要なものをリストし/path/to/python3.1 ./setup.py build_ext --inplace、次に適切な距離コードを編集するので、興味のある人は複製が簡単であることがわかります。

もう1つ：これはPython3.1で実行されます。面白いことに、*.pyxファイル内には裸のUnicode文字列がprintありますが、それでも関数ではなくステートメントです。

はい、これはここに貼り付けるコードがたくさんあることは知っていますが、切り詰めすぎるとコードを実行できなくなります。私はeditdistance()正しく機能することを除いてすべての方法を信じていますが、あなたが感じる問題を自由に指摘してください。

setup.py：

cython_dameraulevenshtein.pyx（最後までスクロールして、興味深いものを確認してください）：

編集私もこのテキストをpastebinとCythonリストに投稿しました。