問題タブ [edit-distance]

問題:それぞれサイズ n と m の 2 つの文字列について、O(mn) での自明な編集距離 DP の定式化と計算を知っています。しかし、編集距離 f の最小値のみを計算する必要があり、それが |f|<=s に制限されている場合、O(min(m,n) + s^2) で計算できることを最近知りました。または O(s*min(m,n)) [ウィキペディア] 時間。

これが DP ベースの場合、またはアルゴリズムを説明する場合は、その背後にある dp の定式化を説明してください。

リンクimproved algorithmのセクションを 見てください: http://en.wikipedia.org/wiki/Edit_distance .

改善された UKKONEN のアルゴリズムに関するもう 1 つのリンクhttp://www.berghel.net/publications/asm/asm.php

前もって感謝します。

編集距離の問題を解決しようとしています。私が使用しているコードは以下のとおりです。

DPアプローチです。2D配列を使用しているため、大きな文字列に対して上記の方法を使用してこの問題を解決することはできません。例: 文字列の長さ > 100000。

それで、その困難を克服するためにこのアルゴリズムを変更する方法はありますか?

注: 上記のコードは、小さな文字列の編集距離の問題を正確に解決します。(長さが 1000 未満またはそれに近い)

コードでわかるように、Java 2D Array "dp[][]" を使用しています。したがって、大きな行と列の 2D 配列を初期化することはできません。

例：長さが100000を超える2つの文字列をチェックする必要がある場合

上記は

そのため、stackOverflow エラーが発生します。

したがって、上記のプログラムは、長さが短い文字列にのみ適しています。私が求めているのは、Javaで大きな文字列（長さ> 100000）のこの問題を効率的に解決する方法はありますか.

PS 追加、置換、および削除の重み付けが異なる場合。私を助けることができるアルゴリズムはありますか。

あるいは、追加・削除と置換の重みが異なる場合、編集距離を最小化するには、ワーグナー・フィッシャーのアルゴリズムにどのような修正が必要でしょうか?

データベースに多数の名前と住所を含むプロジェクトに取り組んでいます。「ジョン K スミス」や「ジョー スミス」などの名前と、「20 Theroad avenue」や「1345 Myplace st.」などの住所。

このプロジェクトでは、ユーザー X が Web サイトにアクセスすると、名前と住所、およびその他の詳細を入力します。入力された名前と住所は、データベースに既に存在するものと照合されます。入力された名前とアドレスが、ユーザー X のデータベースに存在するものと十分に類似している場合、アクセスが許可されます。

ログインをより便利にするために、正確な文字列一致の代わりに、おおよその文字列一致を実行する必要があります。（これはセキュリティコンサートであることは知っていますが、完全に一致するユーザー名/パスもあります）。

名前と住所に適した文字列一致アルゴリズムを探しています。さらに、頭字語、短縮形、および「ave」と「avenue」または「mr」と「mr」などの類似のフレーズを考慮に入れています。または「通り」対「大通り」。

これまで、編集距離、jarowinkler、ngram(qgram)、コサイン類似度、および音声学的アプローチを見てきました。

カスタム正規化関数 (短縮形/類似用語の文字列置換を行う) を使用したハイブリッド アプローチが最適な方法であると考えましたが、まだ確信が持てません。

このプロジェクトは最終的に他の言語 (スペイン語とフランス語) で動作するはずです。これは、より多くのカスタム テキスト置換を意味する可能性があります。

名前と住所を高い精度で (最小数の誤検知で) 一致させるための最適なアルゴリズムを見つけるための助けをいただければ幸いです。

したがって、レーベンシュタイン距離アルゴリズムでは、文字列 A を文字列 B に変更するために必要な削除、挿入、および置換の最小数が考慮されることは承知しています。変更を行うために必要です。私はこのアルゴリズムの実装を見ていましたが、

したがって、削除を追跡するために、次のことを試しました。

次にカウントを増やします。しかし、これはうまくいかないようです。また、2 つの文字列のサイズの違いを取得しようとしましたが、次の場合は失敗します

ここには明らかに 1 つの削除がありますが、サイズの違いを取得するだけでは検出されません。

文字列 A を文字列 B に変更するための合計編集に含まれる削除の数を追跡する方法を誰かが知っているかどうか疑問に思っていました.

置換と挿入のみをカウントする編集距離アルゴリズムを知っている人はいますか? したがって、基本的には、削除のないレーベンシュタイン距離アルゴリズムになります。

2 つの異なる文字列の部分文字列を探しています。問題は次のとおりです。

2 つの文字列 x = X1...Xn および y = Y1...Ym が与えられた場合、最も長い共通部分文字列の長さと、インデックス i および j が XiXi+1...Xi+k の最大の k を見つけます。 -1 = YjYj+1...Yj+k-1. 時間 O(m*n) でこれを行う方法を示します。

誰かが私があまりにも長い間見てきたこの問題を手伝ってくれますか? 私はすでにこの問題のために部分空間をやろうとしましたが、結局間違っていました。どんな支援も喜んでいただければ幸いです！前もって感謝します！