Sequenzvergleich in Java

Question

Ich suche nach einem Standardalgorithmus/-code (Java), der zwei Integer-Listen (alt und neu) vergleicht und eine dritte Ergebnisliste gibt, die Aktionen zur Umwandlung der 'alten' Liste in die 'neue' bietet ' Liste.

Zum Beispiel:

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

so sollte das Ergebnis so etwas wie:

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

hier das Suffix:

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

und den Rest (w/o Suffix) , sind Zahlen, die unverändert sind (dh Wert sowie Index). Ich glaube, etwas mit der LCS (längste gemeinsame Sequenz) würde diesen Job erledigen! Aber ich kann nicht wirklich herausfinden, ob es welche gibt.

Alle Hinweise werden sehr geschätzt.

Answer 1

Levenshtein distance Algorithmus scheint für Sie zu arbeiten (im Wesentlichen der LCS-Algorithmus, den Sie erwähnten). Zeichnen Sie einfach die Aktion auf, die Sie in einer anderen Tabelle ausgewählt haben (gleich nachdem Sie das Minimum ausgewählt haben, müssen Sie aufzeichnen, welche Aktion die Mindestkosten ergeben hat, um sie danach abfragen zu können).

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; 
} 

Dann action[i, j] verwenden rekursiv zurück durch den Prozess zu gehen und in einem Stapel die gewählte Aktion drücken.

Answer 2

Ich habe etwas in C# implementiert. Portieren es zu Java ...

(edit)

Hier ist die Java-Version:

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

Gerade für zukünftige Referenzen. Sowohl die erste als auch die zweite Antwort sind gut. Die erste Antwort ist der Schlüssel zu dem, was ich suchte. Der optimale Weg, um Sequenzen zu vergleichen. und Die zweite Antwort ist ein Arbeitscode zum Vergleichen von Sequenzen. Dies ergibt jedoch kein optimales Ergebnis für die Umwandlung einer Liste in eine andere. Aber gut für einen einfachen Unterschied !!

Vielen Dank für die Antworten !!

Danke, Abhishek.