XML 버전 관리 알고리즘

Question

두 XML 기반 구문 분석 트리를 비교하고 차이를 만드는 효율적인 방법을 찾고 있습니다.

이러한 차이점을 저장하는 가장 좋은 방법은 무엇이라고 생각하십니까? 나는이 작업을 수행 한 것 :

XML의 A :

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> 
    </w:r> 
</w:p> 

XML의 B :

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

알고리즘은 "세계"가 "자위대"로 변경 한 후 저장했다고 판단 :

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

발생 가능한 모든 문제를 해결하기에 충분합니까?

누구나 그 좋은 방법을 알고 있습니까? 어떤 도움이 정말로 감사하겠습니다!

Answer 1

힘들어 질 수 있습니다. 이 예를 살펴 보겠습니다 :

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> <-- Case 1: this changes to <w:t>ASDF</w:t> 
    <w:t>World</w:t> <-- Case 2: this changes to <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

두 경우 모두 인식 할 수 있도록, 당신은 저장해야 하나

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

및

div: <w:p><w:r><w:t>World</w:t><w:t>World</w:t> -> <w:p><w:r><w:t>World</w:t><w:t>ASDF</w:t> 

또는 비슷한 (같은 다른

로 유효한 XML 하위 트리가되도록 "w : p"닫는 태그를 두 태그에 추가 할 수도 있습니다.

일반적으로 이러한 프로그램은 매우 복잡 할 수 있으므로 완전히 새로운 것을 만들지 만 기존의 diff 알고리즘을 사용하거나 (대부분 XML 구조를 구문 분석하지 않아도 충분합니다) 수정하거나 그 중 하나는 귀하의 필요에 부합합니다.

Answer 2

XMLDiff :

는 XML DIFF 그 독자가 을을 수 일반적인 시나리오를 활용하여, 의 XML 출력의 차이를 두 XML 파일을 비교하고 생산 패치 도구를 사용하는 방법을 설명합니다 자신의 응용 프로그램에 적용하십시오.

Answer 3

공통 부분에 대한 간단한 깊이 우선 검색은 어떻습니까? 즉, 깊이 우선 탐색을 수행하고 차이를 발견하면 즉시 저장하고 백 트랙킹을 시작하십시오. 출력의 컨텍스트 부분을 구성하는 데 필요한 추가 정보는 "백 트랙 스택"에 쉽게 저장 될 수 있습니다.

Answer 4

두 나무 사이의 차이를 비교하고 그 차이를 "차이"를 만들어 내고 싶다면 변형의 변형을보고 있습니다. 문제입니다. 시동기의 경우 this paper을 확인하십시오.

더 일반적인 "편집 거리"문제는 문자열의 거리를 편집하는 문제입니다. 변경 내용을 저장하기 위해 "델타 코딩"을 사용하는 CVS 또는 SVN과 같은 버전 제어 소프트웨어은 델타를 계산하기 위해 문자열 편집 거리 알고리즘의 변형을 사용합니다.나무의 경우는 흔하지는 않지만 확실히 흥미 롭습니다.