問題タブ [levenshtein-distance]

約20,000通のメールアドレスのリストがあります。そのうちのいくつかは、username1 @ gmail.com、username1a @ gmail.com、username1b @ gmailなど、「メールごとに1つ」の制限を回避しようとする不正な試みであることがわかっています。 comなど。評価のために同様のメールアドレスを見つけたい。現在、私はLevenshteinアルゴリズムを使用して、リスト内の他の電子メールと照合し、編集距離が2未満の電子メールを報告しています。ただし、これは非常に時間がかかります。より効率的なアプローチはありますか？

私が現在使用しているテストコードは次のとおりです。

編集：私がキャッチしようとしているもののいくつかは次のようになります：

01234567890@gmail.com
0123456789@gmail.com
012345678@gmail.com
01234567@gmail.com
0123456@gmail.com
012345@gmail.com
01234@gmail.com
0123@gmail.com
012@gmail.com

私が行っているこのレーベンシュタイン距離の計算を最適化するのに問題があります。次のことを行う必要があります。

1. ソース文字列の最小距離とソース文字列のトリミングされたバージョンを含むレコードを取得します

2. 最小距離のレコードを選択
3. 最小距離が等しい場合 (元の距離とトリミングされた距離)、最短の距離でトリミングされたものを選択します。
4. 上記の 2 つのカテゴリに該当するレコードがまだ複数ある場合は、頻度が最も高いレコードを選択します。

ここに私の作業バージョンがあります:

私がここでしなければならないことは..

1. 結果を一時テーブルに保存しない
2. `MyTable` から 1 つだけ選択してください
3. 最初の選択ステートメントからの選択で結果を正しく設定します。（selectは変数を設定し、1つのselectステートメントで複数の変数を設定できるため）

これには適切な実装が必要であることは知っていますが、理解できません...これは私が得た限りです:

何か案は？

<tl;dr>
<optimizations>ソース バージョン管理の差分パッチの生成において、差分パッチを作成するために diff の私の Ruby 実装で、 この記事の一番下に記載されている最適化 (「参考文献」を参照) を使用する価値はありますか?
</tl;dr>

<introduction>
私は今までにやったことがないことをプログラミングしています。私がプログラミングしていることとまったく同じことを行うためのツールがすでに存在しているかもしれませんが、現時点では気にするのはあまりにも楽しいので、それでも最初からやり直すつもりです。これにはツールがあります。

とにかく、私は Ruby on Rails アプリに取り組んでおり、特定の機能が必要です。基本的に、たとえばビデオゲームのテーブルなど、私のテーブルの各エントリに、そのテーブルエントリのレビューなどを表すテキストのチャンクを保存する必要があります。ただし、このテキストを登録ユーザーが編集できるようにし、バージョン管理システムでさまざまな送信を追跡できるようにしたいと考えています。私が考えることができる最も簡単な解決策は、テキスト本文とテキスト本文のさまざまなバージョンの差分パッチ履歴を Ruby のオブジェクトとして追跡し、できれば人間が読める形式でシリアル化するソリューションを実装することです (したがって、私はほとんどの場合、これには YAML を使用します) ソフトウェアのバグによる破損や、管理者がバージョン編集を行う際のミスにより、必要に応じて編集します。

そのため、最初はこの機能に頭を突っ込んでみましたが、差分パッチを生成する問題は、私が効率的に行うと思っていたよりも難しいことがわかりました。そこで私はいくつかの調査を行い、いくつかのアイデアに出くわしました。すでに実装したものと実装していないものがあります。ただし、diff または diff に似た機能を使用して何かを既に行っているかどうか、およびそれを解決する関数を最適化したことがあるかどうかはすでにわかっているため、すべてが最も長い一般的なサブシーケンスの問題を中心に展開しています。

現在、私はそれを持っているので、一致しない行が見つかるまで、テキスト本文の比較されたバージョンを最初と最後から切り捨てます。次に、比較行列を使用して問題を解決しますが、例を見た最も長い一般的なサブシーケンスアルゴリズムのように一致する行が見つかったときにセルに格納されている値をインクリメントする代わりに、一致しない行があるときにインクリメントするので、最長共通部分列の代わりに編集距離を計算するように。私が知る限り、この 2 つのアプローチは同じコインの裏表であるため、どちらを使用しても答えを導き出すことができます。次に、比較マトリックスをバックトレースし、インクリメントが発生した時期と隣接セル (西、北西、または北) を記録して、その行の diff エントリを決定し、他のすべての行が変更されていないと想定します。

通常はそのままにしておきますが、これはスタンドアロンの Ruby スクリプトだけでなく、Rails 環境にも適用されるため、少なくとも十分に最適化する必要があるのではないかと心配し始めました。システムを制御し、私の最悪のシナリオのエントリがサーバーにそれほどヒットできないことを知っていました. インターネットを介して研究論文や記事を検索して読んだ後、まともなように見えるがすべてに長所と短所があるように見えるいくつかに出くわしました。アウト。ここにリストされているものはそれだけの価値がありますか？それらを既知の長所と短所とともにリストしました。
</introduction>

<optimizations>

1. 行が変更されていない場所で分割し、各セクションの最初と最後で変更されていない行の各セクションを切り捨てることにより、比較されたシーケンスを複数のサブシーケンスにチョップします。次に、各サブシーケンスの編集距離を解決します。

   • 長所: 変更された領域が大きくなるにつれて、時間の増加を 2 次増加から線形増加に近いものに変更します。

   • 短所：分割する場所を特定することは、編集距離を解決する必要があるように思えますが、今ではそれがどのように変更されたかは気にしません。これがハミング距離の解決に近いプロセスで解決できる場合は問題ありませんが、1 回の挿入ではこれが失敗します。

2. 暗号化ハッシュ関数を使用して、すべてのシーケンス要素を整数に変換し、一意性を確保します。次に、シーケンス要素自体ではなく、ハッシュ整数を比較して編集距離を解決します。

   • 長所: 2 つの整数を比較する操作は、2 つの文字列を比較する操作よりも高速であるため、比較のたびにパフォーマンスがわずかに向上します。

   • 短所: 暗号化ハッシュ関数を使用すると、すべてのシーケンス要素を変換するのに時間がかかり、整数比較から得られる変換を行うためにより多くの時間がかかる可能性があります。文字列に組み込みのハッシュ関数を使用できますが、一意性は保証されません。

3. 遅延評価を使用して、比較行列の中心にある 3 つの対角線のみを計算し、必要に応じて追加の対角線のみを計算します。また、このアプローチを使用して、ここで説明したように、隣接する 3 つのセルすべてを比較する必要がなくなる可能性があります。

   • 長所: 常に O(n * m) 時間かかるアルゴリズムを変更して、最悪のシナリオのみがその時間であり、最良のケースは実質的に線形になり、平均的なケースは 2 つの間のどこかにあるようにすることができます。

   • 短所：関数型プログラミング言語でしか実装されていないアルゴリズムであり、上記のリンク先のサイトで説明されている方法に基づいて、これをRubyに変換する方法を理解するのに苦労しています。

4. C モジュールを作成し、C のネイティブ レベルで大変な作業を行い、そのための Ruby ラッパーを作成するだけで、Ruby は必要なすべての呼び出しを行うことができます。

   • Pro : このようなものを評価すると、はるかに高速になる可能性があると想像する必要があります。

   • 短所: Rails が C 拡張を持つ Ruby コードを使用したアプリをどのように処理するのかわかりません。また、アプリの移植性が損なわれます。

5. これは、編集距離の解決後の最適化ですが、アイデアは、各バージョンによって生成された差分を組み合わせて追加の差分を保存し、最近作成された差分をツリーのルート ノードとしてデルタ ツリー データ構造を作成することです。どのバージョンでも、O(n) ではなく O(log n) の最悪のケースの時間がかかります。

   • 長所: 古いバージョンに戻るのがずっと速くなります。

   • 短所：新しいコミットのたびに、デルタツリーが新しいルートノードを取得することを意味します。これは、言うまでもなく、バージョンを戻すよりもはるかに頻繁に実行される操作のためにデルタツリーを再編成するのに時間がかかります古いバージョンである可能性は低いです。

</optimizations>

では、これらのことは努力する価値があるのでしょうか?

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

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

壁の特定の投稿を見つけるためのフリーテキスト検索アルゴリズムを作成しようとしています（Facebookが使用するのと同様の種類の壁）。ユーザーは、検索フィールドにいくつかの単語を書き込んで、その単語を含む投稿にヒットすることができると想定されています。一番上に最もよく一致し、次に他の投稿が一致スコアに従って降順で表示されます。

編集距離（Levenshtein） "e（x、y）= e"を使用して、クエリワード「x」および投稿ワード「y」と比較した場合の各投稿のスコアを次のように計算しています：score（x、y ）= 2 ^（2-e）（1-min（e、| x |）/ | x |）、ここで "| x |" クエリワードの文字数です。

投稿内の各単語は、その特定の投稿の合計スコアに影響します。このアプローチは、投稿のサイズがほぼ同じである場合にうまく機能するように見えますが、実際にはクエリに関連していないのに、特定の大きな投稿が多くの単語を含むだけでスコアを上げることができる場合があります。

私はこの問題に間違った方法でアプローチしていますか、それとも私が考えていなかったスコアを正規化する方法がありますか？

ユーザーが記事をアップロードするデータベースがあります。ユーザーが読んだものに応じて、Web アプリが同様のテキストを提案するアルゴリズムを作成したいと思います。

レーベンシュタイン距離のような例を見ました。しかし、これらのアルゴリズムは、記事全体ではなく文字列の距離を測定します。テキストから最も重要なキーワードを抽出する方法はありますか? 確かに、「最も重要」という言葉があいまいな言葉であることは理解しています。

他のサイトはこれをどのように管理していますか?

どうもありがとう

PHP 用のDamerau-Levenshteinアルゴリズムの実装を探していますが、友人の Google では何も見つからないようです。これまでのところ、PHP で実装されたレーベンシュタイン (Damerau 転置なし、これは非常に重要です) を使用するか、元のソース コード (C、C++、C#、Perl) を入手して、それを PHP に書き込む (翻訳する) 必要があります。

PHP の実装に関する知識を持っている人はいますか?

私は社内イントラネットの "もしかして:" 拡張機能に soundex と double metaphone を使用しており、Damerau-Levenshtein アルゴリズムを実装して、結果をより適切に分類できるようにしたいと考えています。このアイデアに似たもの: http://www.briandrought.com/blog/?p=66、私の実装は最初の 5 つのステップに似ています。

CまたはFortranコードとして実装されているレーベンシュタイン距離カウント機能を含むパッケージはありますか？比較する文字列がたくさんありますが、これstringMatchにMiscPsychoは遅すぎます。

辞書内の文字列に最も近い一致を見つけるために、最適一致ファイル検索アルゴリズムを実装しました。コードのプロファイリングを行った後、クエリと可能な結果との間の距離の計算に圧倒的に多くの時間が費やされていることがわかりました。現在、2 次元配列を使用してレーベンシュタイン距離を計算するアルゴリズムを実装しています。これにより、実装は O(n^2) 演算になります。誰かが同じことをするより速い方法を提案できることを望んでいました。

これが私の実装です：

最近、レーベンシュタイン距離を計算するためのアルゴリズムの最適化に関する質問を投稿しました。その回答から、レーベンシュタイン距離に関するWikipediaの記事が表示されます。

この記事では、最大距離に限界kがある場合、与えられたクエリから可能な結果が得られる可能性があると述べています。実行時間はO（mn）からO（kn）に短縮できます。mとnはの長さです。文字列。アルゴリズムを調べましたが、実装方法がわかりませんでした。私はここでそれについていくつかのリードを得ることを望んでいました。

最適化は「可能な改善」の＃4です。

私を混乱させたのは、主対角線を中心とした幅2k + 1の対角線ストライプを計算するだけでよいと言った部分です（主対角線は座標（i、i）として定義されます）。

誰かが助け/洞察を提供することができれば、私は本当にそれをいただければ幸いです。必要に応じて、アルゴリズムの完全な説明を本の回答としてここに投稿できます。