識別子の2つのシーケンスを比較する

Question

識別子の2つのシーケンスが与えられた場合、識別子の第1のシーケンスを第2のシーケンスに変換する最小の動作シーケンスをどのように見つけるか。

動作することができる：

• が所定位置
• 所定の位置から
• 移動別の

注する位置から識別子を識別子を削除するに識別子を挿入します。識別子はユニークでシーケンス内に2回出現することはできません

例：

Sequence1 [1, 2, 3, 4, 5] 
Sequence2 [5, 1, 2, 9, 3, 7] 

Result (index are 0 based) : 
- Remove at 3 
- Move from 3 to 0 
- Insert '9' at 3 
- Insert '7' at 5 

ありがとうございます！

Answer 1

まず、longest common subsequenceを見つけてください。これにより、移動しない要素が識別されます。LCSの要素はカッコで囲まれています。

インデックス0の両方のシーケンスを調べ、シーケンスを同一にするために必要な操作を記録します。最初のシーケンスの現在の項目がLCSの一部でない場合は、後でそれを挿入する必要がある場合に備えて、それを削除し、以前の場所にマークを付けます。現在の要素がLCSの一部である場合、その要素の前に2番目の要素を挿入します。これは簡単な挿入または移動のいずれかになります。挿入しているアイテムが元のリストにある場合は、移動します。それ以外の場合は、挿入します。

ここにあなたの例を使ったデモがあります。中括弧は、現在の要素

[{(1)}, (2), (3), 4, 5] vs [{5}, 1, 2, 9, 3, 7] 

1は、LCSのメンバーであるので、我々は5を挿入する必要があります示しています。 5は、元のシーケンスであるので、我々は動きを記録：MOVE 4 to 0

[5, {(1)}, (2), (3), 4] vs [5, {1}, 2, 9, 3, 7] 

項目は同じですので、我々は次のものに移動：

[5, (1), {(2)}, (3), 4] vs [5, 1, {2}, 9, 3, 7] 

再び番号が同じである - 移動次のいずれかに：

[5, (1), (2), {(3)}, 4] vs [5, 1, 2, {9}, 3, 7] 

3は、LCSのメンバーであるので、我々は9を挿入する必要があります。

[5, (1), (2), 9, (3), {4}] vs [5, 1, 2, 9, 3, {7}] 

「4」メンバーではありません： - 次の1への移行はINSERT 9 at 3

[5, (1), (2), 9, {(3)}, 4] vs [5, 1, 2, 9, {3}, 7] 

またしても番号が同じである：それは、単純な挿入ですので、元の要素は、9を持っていませんそれが削除されるLCSの、よう：DEL at 5

[5, (1), (2), 9, (3)] vs [5, 1, 2, 9, 3, {7}] 

我々は最初のシーケンスの終わりに達した - 私たちは、単に目に第二の配列の残りの項目を追加します最初の1つ、前の削除のリストに注意を払う。たとえば、7が以前に削除されていた場合、この時点でその削除を移動に変換します。しかし元のリストには7が含まれていなかったので、最終的な操作はINS 7 at 5です。

Answer 2

このメトリックはLevenshtein distance以上、正確にはDamerau–Levenshtein distanceと呼ばれます。

ほとんどすべての可能なプログラミング言語の実装がありますので、ここで説明した問題を解決できます。