Javaのシーケンス比較

Question

2つの整数リスト（古いものと新しいもの）を比較する標準アルゴリズム/コード（Java）を探していて、「古い」リストを「新しい」リストに変換するアクションを提供する3番目の結果リストを提供します'リスト。例えば

：

ここ

1-, 9+, 2, 3, 4-, 6+, 4+ 

、接尾辞：

- = Deleted item from old list. 
    + = New added item to old list. 

、残り（W/Oサフィックス）

old-> 1, 2, 3, 4 
new-> 9, 2, 3, 6, 4 

ので、結果はのようなものでなければなりません、変わらない数字（すなわち、ValueとIndex）です。私はLCS（最も長い共通シーケンス）を使って何かがこの仕事をすると信じています！ しかし、私は本当に何かがあるかどうかは分かりません。

どのポインタも高く評価されます。

Answer 1

アルゴリズムは本質的にあなたが言及したLCSアルゴリズムで動作するようです。選択したアクションを別のテーブルに記録するだけです（最小値を選択した直後に、後でルックアップできるようにするために最小のコストが発生したアクションを記録する必要があります）。

if (seq1[i] == seq2[j] && d[i - 1, j - 1] <= d[i - 1, j] + 1 
         && d[i - 1, j - 1] <= d[i, j - 1] + 1) { 
    d[i, j] = d[i - 1, j - 1]; 
    action[i, j] = MATCHED; 
} else if (d[i - 1, j] < d[i, j - 1]) // If cost of insertion is less: 
{ 
    d[i, j] = d[i - 1, j] + 1; 
    action[i, j] = INSERTION; 
} else { 
    d[i, j] = d[i, j - 1] + 1; 
    action[i, j] = DELETION; 
} 

そして、再帰的プロセスを経て戻って、スタック内の選択したアクションをプッシュするためにaction[i, j]を使用しています。

Answer 2

私はC＃で何かを実装しました。

enum Action { 
    UNCHANGED, ADDED, REMOVED 
} 

static class DiffResult<T> { 
    private T value; 
    public Action type; 

    public DiffResult(T value, Action type) { 
     super(); 
     this.value = value; 
     this.type = type; 
    } 

    public T getValue() { 
     return value; 
    } 

    public Action getType() { 
     return type; 
    } 
} 


public static <T> List<DiffResult<T>> listDiff(List<T> originalList, 
     List<T> newList) { 
    List<DiffResult<T>> result = new ArrayList<DiffResult<T>>(); 

    int maxCount = Math.max(originalList.size(), newList.size()); 
    for (int i = 0; i < maxCount; i++) { 
     if (newList.size() < i + 1) 
      result.add(new DiffResult<T>(originalList.get(i), 
        Action.REMOVED)); 
     else { 
      if (originalList.size() < i + 1) { 
       result.add(new DiffResult<T>(newList.get(i), Action.ADDED)); 
      } else { 
       if (originalList.get(i).equals(newList.get(i))) 
        result.add(new DiffResult<T>(originalList.get(i), 
          Action.UNCHANGED)); 
       else { 
        result.add(new DiffResult<T>(originalList.get(i), 
          Action.REMOVED)); 
        result.add(new DiffResult<T>(newList.get(i), 
          Action.ADDED)); 
       } 
      } 
     } 
    } 
    return result; 
} 

public static void main(String[] args) { 
    List<Integer> oldList = new ArrayList<Integer>(); 
    oldList.add(1); 
    oldList.add(2); 
    oldList.add(3); 
    oldList.add(4); 

    List<Integer> newList = new ArrayList<Integer>(); 
    newList.add(9); 
    newList.add(2); 
    newList.add(3); 
    newList.add(6); 
    newList.add(4); 

    List<DiffResult<Integer>> diff = listDiff(oldList, newList); 

    for (DiffResult<Integer> d : diff) { 
     System.out.println("Item: " + d.getValue() + " -> " + d.getType()); 
    } 
} 

Answer 3

ただ、将来の参照のために：... Javaのそれを移植する

ここで（編集）

は、Javaのバージョンです。 1回目と2回目の両方の回答が良いです。 第1の答えは、私が探していたものの手掛かりです。シーケンスを比較する最適な方法。 および 2番目の答えは、シーケンスを比較するための作業コードです。しかし、これはあるリストを別のリストにカバーする最適な結果をもたらしません。しかし、シンプルなdiffのために良い！

ありがとうございました！

ありがとう、 Abhishek。