2

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

例えば：

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

結果は次のようになります。

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

ここで、接尾辞:

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

残り (サフィックスなし) は変更されない数値です (つまり、値とインデックス)。LCS (最長共通シーケンス) を使用すると、この仕事ができると思います! しかし、実際にあるかどうかはわかりません。

どんな指針も高く評価されます。

4

3 に答える 3

3

レーベンシュタイン距離アルゴリズムはあなたのために働くようです（本質的にあなたが言及した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]、プロセスを再帰的に戻り、選択したアクションをスタックにプッシュするために使用します。

于 2009-05-09T11:27:46.653 に答える
2

C#で何かを実装しました。それをJavaに移植しています...

（編集）

Java のバージョンは次のとおりです。

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());
    }
}
于 2009-05-09T11:58:01.107 に答える
0

今後の参考のために。1番目と2番目の答えはどちらも良いです。最初の答えは、私が探していたものの手がかりです。シーケンスを比較する最適な方法。そして、2番目の答えは、シーケンスを比較するための作業コードです。しかし、これは、あるリストを別のリストに変換するための最適な結果をもたらしません。しかし、単純な差分には適しています!!

答えてくれてありがとう！

ありがとう、アビシェーク。

于 2009-05-28T15:08:10.737 に答える