자바에서 시퀀스 비교

Question

두 정수 목록 (이전 및 신규)을 비교하는 표준 알고리즘/코드 (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. 

및 (접미사 O/w) 나머지 , 변경되지 않은 숫자입니다 (예 : 값 및 색인). 나는 LCS (longest common sequence)를 사용하여 무언가가이 일을 할 것이라고 믿는다. 그러나 나는 그것이 실제로 존재하는지 알아 내지 못합니다.

모든 포인터는 높이 평가됩니다.

Answer 1

Levenshtein distance 알고리즘이 본질적으로 (당신이 언급 한 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

그냥 미래를 참조하십시오. 첫 번째와 두 번째 대답 모두 좋습니다. 첫 번째 대답은 내가 찾고있는 것에 대한 단서입니다. 시퀀스를 비교하는 최적의 방법입니다. 및 두 번째 대답은 시퀀스를 비교하는 작업 코드입니다. 그러나 이것은 한 목록을 다른 목록으로 묶는 최적의 결과를 제공하지 못합니다. 그러나 간단한 diff를 위해 좋다!!

답 해 주셔서 감사합니다.

감사합니다. Abhishek.