performance - レーベンシュタイン転置距離

Question

動的計画法を使用して、転置/スワップ/ひねり/交換距離のみを実装するにはどうすればよいですか。他の操作（つまり、コピー、削除、挿入、強制終了など）を転置/スワップするだけでチェックしたくないことを強調する必要があります。

スワップ距離だけにレーベンシュタインのアルゴリズムを適用したいと思います。コードはどのようになりますか？

Answer 1

動的計画法を効率的に適用するには、通常、入力を短くするためにタスクを同じタスクの複数のインスタンスに分解する必要があります。レーベンスタイン距離の場合、これは 2 つの文字列の接頭辞と、一方から他方に取得するために必要な編集の数に要約されます。あなたの場合、そのような分解がどのように達成できるかわかりません。少なくとも、多項式時間アルゴリズムになるものは見当たりません。

また、あなたが話している操作が明確ではありません。文脈に応じて、スワップまたは交換は、転置と同じことを意味する場合もあれば、文字を任意の他の文字に置き換えることを意味する場合もありtest->textます。"transpose/swap/twiddle/exchange" で単に "transpose" と言おうとする場合は、Counting the neighbor swaps required to convert one permutation into another を参照する必要があります。そうでない場合は、質問を明確にしてください。

Answer 2

この場合、Levenstein のアルゴリズムを使用できるかどうかはわかりません。挿入または削除操作を行わない場合、距離は同じ長さおよび同じ文字の文字列間でのみ適切に定義されます。転置だけでは同じ文字列に変換できない文字列の例:

AB, ABC
AAB, ABB

これにより、アルゴリズムは、両方の文字列の同じ場所にない文字の位置のすべての可能な順列を見つけ、最小数の転置または交換で表現できるものを探すことができます。