編集距離

「kitten」と「sitting」のレーベンシュタイン距離は3です。前者を後者に変換する最小限の編集スクリプトは次のとおりです。

1. k itten → s itten（「k」を「s」に置き換えてください）
2. sitt e n → sitt i n (「e」を「i」に置き換えてください)
3. sittin → sittin g（最後に「g」を挿入）

LCS距離（挿入と削除のみ）は、異なる距離と最小限の編集スクリプトを提供します。

1. k itten → itten (0の「k」を削除)
2. itten → s itten（0の位置に「s」を挿入）
3. sitt e n → sittn (4の「e」を削除)
4. sittn → sitt i n (4に「i」を挿入)
5. sittin → sittin g（6の位置に「g」を挿入）

合計費用／距離は5回の操作に相当します。

非負のコストを持つ編集距離は、以下の条件が満たされる場合に、距離の公理を満たし、文字列の距離空間を生み出す。 ^{[ 1 ] : 37}

• すべての編集操作には正のコストがかかる。
• すべての操作には、同等のコストを持つ逆操作が存在する。

これらの性質により、計量公理は以下のように満たされる。

d ( a , b ) = 0 は a=b の場合に限り成り立つ。なぜなら、各文字列は正確にゼロ回の操作で自明にそれ自身に変換できるからである。

a ≠ bの場合、 d ( a , b ) > 0 となります。これは、少なくとも 1 つの非ゼロのコストの操作が必要になるためです。

d ( a , b ) = d ( b , a ) は、各演算のコストとその逆演算の等式によって成り立つ。

三角不等式: d ( a , c ) ≤ d ( a , b ) + d ( b , c ) 。^{[ 5 ]}

レーベンシュタイン距離と単位コストのLCS距離は上記の条件を満たし、したがってメトリックの公理を満たします。適切なメトリックではない編集距離の変種も文献で検討されています。^{[ 1 ]}

単位コスト編集距離のその他の有用な特性には、以下のようなものがあります。

• LCS距離は、一対の弦の長さの合計によって上限が定められる。^{[ 1 ]： 37}
• LCS距離はレーベンシュタイン距離の上限値である。
• 同じ長さの文字列の場合、ハミング距離はレーベンシュタイン距離の上限です。^{[ 1 ]}

コストや重みに関係なく、すべての編集距離において以下の性質が成り立つ。

• aとb が共通の接頭辞を持つ場合、この接頭辞は距離に影響を与えません。正式には、a = uvかつb = uwの場合、d ( a , b ) = d ( v , w ) となります。^{[ 4 ]}これにより、共通の接頭辞と接尾辞を線形時間でスキップできるため、編集距離と編集スクリプトを含む多くの計算を高速化できます。

レーベンシュタインの元の操作を使用すると、(非対称)編集距離は${\displaystyle a=a_{1}\ldots a_{m}}$に${\displaystyle b=b_{1}\ldots b_{n}}$は$d_mn$再帰式^{[ 2 ]}によって定義される

${\displaystyle {\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}}$

このアルゴリズムは、再帰節の最小化に別の項を追加することで、転置を処理するように一般化できます。^{[ 3 ]}

この漸化式を評価する単純な再帰的方法は指数関数的な時間を要します。そのため、通常は動的計画法アルゴリズムを使用して計算されます。このアルゴリズムは一般的にワグナーとフィッシャーに帰せられていますが^{[ 7 ]}、複数の発明の歴史があります^{[ 2 ] [ 3 ]} 。ワグナー・フィッシャーアルゴリズムの完了後、最小限の編集操作のシーケンスは、動的計画法アルゴリズムで使用された操作のバックトレースとして読み取ることができます。${\displaystyle d_{mn}}$。

このアルゴリズムの時間計算量はΘ( m n ) で、mとn は文字列の長さです。完全な動的計画法テーブルが構築されると、その空間計算量もΘ( m n )になります。任意の時点でアルゴリズムがメモリに 2 行 (または 2 列) しか必要としないことに着目すると、これはΘ(min( m , n ))に改善できます。ただし、この最適化により、最小限の編集操作の系列を読み取ることが不可能になります。^{[ 3 ]}この問題に対する線形空間の解法は、ヒルシュベルクのアルゴリズムによって提供されています。^{[ 8 ] : 634}このような再帰を解決し、入力のサイズに線形な空間でキャッシュ効率よく最適な操作のシーケンスを抽出するための一般的な再帰的分割統治フレームワークは、Chowdhury、Le、および Ramachandran によって提供されています。^{[ 9 ]}

上記のワグナー・フィッシャーアルゴリズムを改良し、ウッコネンはいくつかのバリアントを記述している^{[ 10 ]。}そのうちの1つは、2つの文字列と最大編集距離sを受け取り、min( s , d )を返す。これは、動的計画法テーブルの対角線付近の一部のみを計算して保存することで実現される。このアルゴリズムの実行時間はO( s ×min( m , n ))であり、mとnは文字列の長さである。空間計算量は、編集シーケンス^を読み取る必要があるかどうかに応じて、O( s2 )またはO( s )となる^{[ 3 ] 。}

ランダウ、マイヤーズ、シュミットによるさらなる改良O( s2 + max( m , n )) の^時間アルゴリズムを与える。^{[ 11 ]}

有限のアルファベットと互いに倍数である編集コストの場合、最速の既知の正確なアルゴリズムはMasekとPaterson ^{[ 12 ]}のもので、最悪の場合の実行時間はO(nm/logn)です。