1

[ https://cs.stackexchange.com/questions/12986/sliding-window-edit-distanceから転載]

長さ n の長い文字列と長さ m の短い文字列がある場合、短い文字列と長さ m の長い文字列のすべての部分文字列の間のすべての n-m+1レーベンシュタイン距離を計算できるようにする適切な再帰は何ですか?

実際にO（nm）時間で実行できますか？

4

2 に答える 2

4

スライディング ウィンドウのレーベンシュタイン距離を計算すると、次のような非巡回有向平面グラフの頂点のいくつかのペア間の距離を計算することになります (大文字はペアを示します)。

   h a y s t a c k

n  A-B-C-D-E-F-*-*
   |\|\|\|\|\|\|\|
e  *-*-*-*-*-*-*-*
   |\|\|\|\|\|\|\|
e  *-*-A-B-C-D-E-F

水平アークと垂直アークのコストは 1 です。対応する文字が一致する場合、斜めの弧のコストは 0 になり、そうでない場合は 1 になります。

対になった頂点はすべて無限面上にあるため、クラインまたはカベッロ チェンバースの複数ソース最短パス アルゴリズムを使用して、必要な時間 O(mn log (mn)) の距離を計算できます。

最終的なログを削除するには (実際には、ダイクストラのアルゴリズムなどよりもはるかに悪い)、Alexander Tiskin の原稿Semi-local string comparison: Algorithmic technologies and applicationsを参照してください。一つそのもの。（おそらくそれが私の主な答えになるはずですが、私はそれを読んでおらず、複数ソースの最短パス手法をよく知っています。）

また、単方向エッジを処理するための追加ロジックを使用して、Klein を使用した複数ソース最短パス アルゴリズムを作成して O(mn) を達成できる可能性もあります。

于 2013-07-01T22:12:07.053 に答える
0

それはまさにあなたが求めていたものではありませんが、役立つかもしれません。

短い単語から長い単語のいずれかの部分文字列までの最小距離を見つけたい場合は 、Python のレーベンシュタイン距離と一致するレーベンシュタイン距離ファジー部分文字列の簡単なバリエーションが あります。一般に、最後に文字を追加するコストを設定するか、文字列の先頭を 0 に

于 2013-07-01T20:17:58.793 に答える