問題タブ [edit-distance]

私は別の長い質問で戻ってきました。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リストに投稿しました。

同じテーブル内に非常によく似た行を持つデータベースがあります。これらの行は、列の値がほぼ等しいため、類似しています。これらの対応する行を1つの行に統合する必要があります。

たとえば、これら2つのユーザー（u1とu2）を統合する必要があります。

私はいくつかの編集距離とステミングテクニックを使用することを考えています。他のアルゴリズムとテクニックの提案？使用するのに役立つライブラリはありますか（できればPythonまたはJavaで）？

2 つの文の間の単語レベルの編集距離を見つけることができるアルゴリズムはありますか? たとえば、「A Big Fat Dog」と「The Big House with the Fat Dog」には、1 つの代替、3 つの挿入があります。

私はこの編集距離の問題のバリエーションに出くわしました：

ある単語から別の単語への最短経路を見つけます。たとえば、storm-> powerのように、isValidWord()関数を使用して各中間単語を検証します。単語の辞書への他のアクセスがないため、グラフを作成できません。

私はこれを理解しようとしていますが、それ自体は距離に関連する問題ではないようです。多分単純な再帰を使用しますか？しかし、それでは、自分が正しい方向に進んでいることをどうやって知るのでしょうか。

他の誰かがこれを面白いと思いますか？助けてくれるのを楽しみにしています、ありがとう！

2 つの異なる単語間の距離の計算について、レーベンシュタイン距離について読みました。

ソース文字列が 1 つあり、それを 10,000 のターゲット ワードすべてと一致させる必要があります。最も近い単語が返されます。

問題は、10,000 のターゲット ワードのリストを指定したことと、入力ソース ワードも巨大であることです。ここで適用する最短かつ効率的なアルゴリズムは何でしょうか。n ごとの組み合わせごとのレーベンシュタイン距離の計算 (ブルート フォース ロジック) は、非常に時間がかかります。

ヒントやアイデアは大歓迎です。

私の会社の猫飼いアプリケーションは、猫の車列を追跡しています。定期的に(それぞれが) と比較previousOrderし、変化を cat-wrangler に通知する必要があります。currentOrderArrayList<Cat>

各猫は一意で、各リストに 1 回しか表示されません (またはまったく表示されません)。ほとんどの場合、previousOrderとcurrentOrderリストは同じ内容を同じ順序で持っていますが、次のいずれかが発生する可能性があります (頻度の高いものから低いものへ)。

1. 猫の順番が完全に入れ替わる
2. 猫は個別にリスト内を上下に移動します
3. 車列の特定の時点で、新しい猫が加わります
4. 猫は車列を離れます

これは、私には編集距離の問題のように見えます。previousOrder理想的には、一致させるために必要な手順を決定するアルゴリズムを探していますcurrentOrder。

• 位置Fluffyに移動12
• Snuggles位置に挿入37
• 消去Mr. Chubbs
• 等

アルゴリズムは、シナリオ #1 も認識する必要があります。この場合、新しい順序が完全に伝達されます。

これに対する最善のアプローチは何ですか？

(この投稿とその投稿は同様の質問を提起しますが、どちらもソートされたリストを扱っています。私のものは順序付けられていますが、ソートされていません。)

編集

レーベンシュタイン アルゴリズムは素晴らしい提案ですが、マトリックスを作成するための時間/空間の要件が気になります。私の主な目標は、できるだけ早く変更を決定して伝達することです。追加を見つけて、「これが新しい猫で、これが現在の注文です」という行に沿ってメッセージを送信するよりも高速です。

私は企業の大規模なデータベースを使用しています。

2つの商号の類似性を比較して、重複している可能性があるかどうかを確認できるようにしたいと思います。

以下は、重複する可能性が高いとテストする必要がある会社名のリストですが、これを行うための良い方法は何ですか？

長さnとmの2つのシーケンスがあります。それぞれが（x、y）の形式の点のシーケンスであり、画像内の曲線を表します。これらのシーケンスがどのように異なる（または類似している）かを見つける必要があります

1. 一方のシーケンスはもう一方のシーケンスよりも長い可能性があります（つまり、一方のシーケンスの長さはもう一方のシーケンスの半分または4分の1になりますが、ほぼ同じ曲線をトレースする場合は同じです）

2. これらのシーケンスは反対方向である可能性があります（つまり、シーケンス1は左から右に進み、シーケンス2は右から左に進みます）

   レーベンシュタインのようないくつかの違いの推定値や、タンパク質フォールディングの構造的類似性マッチングの編集距離を調べましたが、どれもうまくいかないようです。独自のブルートフォースメソッドを作成することもできますが、もっと良い方法があるかどうか知りたいです。

ありがとう。

問題: 2 つの文字列間の LCS の長さが必要です。文字列のサイズは最大 100 文字です。アルファベットはいつものDNAのもので、4文字の「ACGT」。動的なアプローチは十分に迅速ではありません。

私の問題は、たくさんのペア (私が見る限り数億のランク) を扱っていることです。LCS_length 関数の呼び出しを可能な限り最小限に減らしたと思うので、プログラムの実行を高速化する他の唯一の方法は、より効率的な LCS_Length 関数を使用することです。

通常の動的プログラミングのアプローチで実装することから始めました。それは正しい答えを与え、うまくいけば適切に実装されます。

それは O(mn) である必要があります (うまくいけば)。

次に、速度を求めて 、Myers によるO(ND) 論文 を提供するこの投稿Longest Common Subsequenceを見つけました。LCSを最短の編集スクリプト（SES）に関連付けるこれを試しました。彼らが与える関係は D = M + N - 2L で、D は SES の長さ、M と N は 2 つのストリングの長さ、L は LCS の長さです。しかし、これは私の実装では常に正しいとは限りません。私は私の実装を与えます（私は正しいと思います）：

主に例があります。例えば。"tomato" と "potato" (コメントしないでください) の LCS の長さは 4 です。実装では、SES (コード内の D) が 4 ではなく 2 として出力されるのは 5 サイスであることがわかります ( 「t」を削除、「p」を挿入、「m」を削除、「t」を挿入）。おそらく O(ND) アルゴリズムも置換をカウントするのではないかと思う傾向がありますが、これについてはよくわかりません。

実装可能なアプローチ (私は膨大なプログラミング スキルを持っていません) であれば、どんなアプローチでも大歓迎です。（たとえば、小さなアルファベットを利用する方法を誰かが知っている場合）。

編集: いつでも任意の 2 つの文字列間で LCS 関数を使用することを何よりも強調すると便利だと思います。したがって、数百万の他の文字列と比較して、s1 などの文字列だけではありません。s1000 で s200、s10000 で s0、s100000 で 250 の可能性があります。ほとんどの使用文字列も追跡できない可能性があります。近似アルゴリズムを実装しており、余分なエラーを追加したくないため、LCSの長さは近似ではないことが必要です。

編集: callgrind を実行しました。10000 個の文字列の入力の場合、文字列のさまざまなペアに対して、lcs 関数を約 50,000,000 回呼び出すようです。(10000 文字列は実行したい最小値であり、最大値は 100 万です (実行可能な場合))。