두 XML 문서를 비교하기위한 데이터 구조 설계

Question

두 개의 XML 문서가 주어졌습니다. 두 개의 문서를 비교하고 문서 간의 차이점을 인쇄하는 데이터 구조 및 코드를 제안합니다. (태그가 존재하지 않거나 태그가 동일하지만 데이터가 다를 수 있습니다.)

My approach : N- 트리를 사용하십시오. N 뭔가처럼 될 것이다 XML file.Now 기능의 속성의 수에 따라 달라집니다

Bool IsIdentical(tree1,tree2) 
{ 
    if(tree1 == NULL && tree2 == NULL)return true; 
    if(tree1 || tree2) return false; 
    if(tree1->data == tree2->data)return true; 
    else return (Isindentical(tree1->firstchild,tree2->firstchild) && Isindentical(tree1->secondchild,tree2->secondchild) && ........ Isindentical(tree1->nthchild,tree2->nthchild)) 

} 

당신이 알려주세요 수 있습니다 나의 접근 방식은 권리 또는 비교 다른 데이터 구조가 무엇입니까? 내 접근 방식이 맞다면 차이점을 생성하는 방법을 알려주십시오.

미리 감사드립니다.

Answer 1

귀하의 접근 방식은 소리입니다. 두 xml 문서를 동시에 메모리에 보관할 필요가없는 대체 방법은 각 문서에 대해 Merkle tree을 작성하여 비교하는 것입니다.

차이점을 비교하는 것이 더 열린 문제이며 문서간에 '차이'를 정의하는 방법에 따라 다릅니다. 예 : <tag 1><tag 2><tag 3>... 대 <tag 1><tag 3> 인 경우 <tag 1>이 유일한 공통 요소이거나 <tag 1> & <tag 3>이 둘 다 공통이라고 주장 할 수 있습니다.

노드의 하위 노드가 다를 때마다 가장 보수적 인 (따라서 단순한) 방법으로 차이를 선언하고이 시점에서 재귀를 중지합니다. 즉 2 개의 트리 교차를 생성합니다. 이 솔루션은 당신의 목표에 따라 지나치게 보수적 수

class Tree: 
    def __init__(self, value, children): 
     self.value = value 
     self.children = children 

def intersect(a, b): 
    if a.value != b.value: 
     return None 
    children = [x for x in itertools.imap(intersect, a.children, b.children) if x is not None] 
    return Tree(a.value, children) 

참고 : 구현은 다음과 같이 보일 수 있습니다.