信号の位置合わせを行うためにレーベンシュタイン距離を実装しました。レーベンシュタインが、最適なソリューションであっても、私が望むソリューションを見つけられない場合があります。たとえば、次の文字列があります。
aaabaa
abaaabaaa
アルゴリズムは、文字列を一致させるために最初の 2 文字と最後の文字を削除する必要があることを認識する必要があります。
abaaabaaa
x xx
代わりに、次のものが見つかります。
abaaabaaa
x x x
したがって、必要以上に文字列を部分文字列に分割します。文字列を最小の部分文字列に分割するレーベンシュタイン距離の延長はありますか?
レーベンシュタイン距離が使用するものよりも複雑な編集コスト関数を導入できます。n 個の連続した削除 (または n 個の連続した挿入) は、n 個の個別の削除 (または挿入) よりも安くすることができます。
これにより、レーベンシュタイン距離で見つかった解よりも安価な解が得られます。
ニーズを満たす編集コスト関数の例:
cost of replace: 2
cost of fist insert: 2
cost of consecutive insert: 1
cost of fist delete: 2
cost of consecutive delete: 1
よりも
abaaabaaa
x xx
編集コスト: 5
と
abaaabaaa
x x x
編集コスト: 6
したがって、見つかったソリューションは、編集距離が 5 の場合に必要なソリューションになります。