초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

XML/HTML 문서와 같이 트리 구조로 표현되는 데이터의 변화 탐지는 NP-hard의 문제로 이에 대한 효율적인 구현은 매우 중요하다. 본 논문에서는 효율적인 변화 탐지를 위해 트리 구조의 데이터를 X-tree로 표현하고 이에 기초한 휴리스틱 알고리즘을 제안한다. X-tree에서는 모든 서브트리의 루트 노드에 서브트리의 구조와 소속 노드들의 데이터들을 128비트의 해시값으로 표현하여 저장함으로 신ㆍ구 버전의 X-tree들에 속한 서브트리들의 비교가 매우 효율적이다. 제시한 변화 탐지 알고리즘에서는 구 버전의 X-tree의 모든 서브트리들에 대해 신 버전의 X-tree에서 동등한 서브트리들을 찾고, 이들에 기초하여 이동 연산이 발생한 서브트리들과 갱신 연산이 발생한 서브트리들을 순차적으로 찾는다. 이때 이동 연산과 갱신 연산으로 대응되는 서브트리는 동등 서브트리로부터 루트 노드로 대응 관계를 확장하는 가운데 발견된다. 이후 깊이 우선으로 검색하면서 나머지 노드들을 대응시킨다. X-tree의 구조적 특징에 기인하여 노드들 간의 비교를 통해 대응 여부를 검사하는 대부분의 기존 연구와는 달리 서브트리의 비교를 통해 대부분의 대응 관계를 결정하므로 효율적인 변화 탐지가 가능하다. 본 알고리즘은 최악의 경우에서도 N을 신ㆍ구 버전 문서의 전체 노드 수라 할 때 O(N)의 시간 복잡도를 갖는다.

XML/HTML 문서와 같이 트리 구조로 표현되는 데이터의 변화 탐지는 NP-hard의 문제로 이에 대한 효율적인 구현은 매우 중요하다. 본 논문에서는 효율적인 변화 탐지를 위해 트리 구조의 데이터를 X-tree로 표현하고 이에 기초한 휴리스틱 알고리즘을 제안한다. X-tree에서는 모든 서브트리의 루트 노드에 서브트리의 구조와 소속 노드들의 데이터들을 128비트의 해시값으로 표현하여 저장함으로 신ㆍ구 버전의 X-tree들에 속한 서브트리들의 비교가 매우 효율적이다. 제시한 변화 탐지 알고리즘에서는 구 버전의 X-tree의 모든 서브트리들에 대해 신 버전의 X-tree에서 동등한 서브트리들을 찾고, 이들에 기초하여 이동 연산이 발생한 서브트리들과 갱신 연산이 발생한 서브트리들을 순차적으로 찾는다. 이때 이동 연산과 갱신 연산으로 대응되는 서브트리는 동등 서브트리로부터 루트 노드로 대응 관계를 확장하는 가운데 발견된다. 이후 깊이 우선으로 검색하면서 나머지 노드들을 대응시킨다. X-tree의 구조적 특징에 기인하여 노드들 간의 비교를 통해 대응 여부를 검사하는 대부분의 기존 연구와는 달리 서브트리의 비교를 통해 대부분의 대응 관계를 결정하므로 효율적인 변화 탐지가 가능하다. 본 알고리즘은 최악의 경우에서도 N을 신ㆍ구 버전 문서의 전체 노드 수라 할 때 O(N)의 시간 복잡도를 갖는다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 따라서, 본 논문에서는 XML 문서의 신.구 버전들 간에 변화가 발생했는지 여부를 확인하고, 변화 발생 시 어느 노드에서 발생했는지룰 빠르게 찾고자 함 올 목적으로 한다.
• XML7HTML 문서로 표현되는 대부분의 웹 문서는 구조화된 문서 (hierarchical structured document) 로 이에 대한 변화의 탐지는 NP-hani에 속하는 문제이다[1, 2]. 따라서 본 논문에서는 순서 트리로 표현된 XML 문서간의 변화롤 효을적으로 탐지할 수 있는 휴리스틱 알고리즘올 제시한다. 단, HTML 문서의 경우 XML 문서로 변환하여 본 알고리즘을 적용한다.
• 본 논문에서는 트리로 표현된 XML 문서간의 변화를 탐지할 수 있는 효율적인 알고리즘과 문서의 변화를 효율적으로 표현할 수 있는 편집 연산과 편집 스크립트를 보였다. 한편, 본 논문에서는 구체적으로 비용을 명시하지 않았으나 적철한 자료구조의 활용으로 신 .
• 본 논문은 계층적 데이터에 대한 변화 탐지 알고리즘으로 최근 발표된 BULD Diff 알고리즘을 개선하였다.
• 우선 X-tree룰 통한 XML 문서의 표현 방법을 살펴보자. X-tree의 노드는 XML 문서의 엘리먼트(Element)나 문자 데이터(PCData)를 나타내며 Type 필드는 X-tree의 노드가 나타내는 데이터가 엘리먼트인지 문자 데이터인지룰 구별한다.

가설 설정

• 우선 1단계에서 발견된 동등 서브트리 쌍의 각 루트 노드의 부모 노드들의 대옹 여부를 고려한다. 두 루트 노드풀을 각각 A, B라하고 이들의 부모 노드들을 각각 pA, pB라 할 때, a) 두 부모 노드들(pA, pB)의 nMD 값(Label과 Value 값)이 같으면 그 부모 노드둘(pA, pB)을 NOP로, b) 두 부모 노드돌의 nMD 값은 서로 다르지만 Label 값이 갈은 경우는 그 부모 노드들(pA, pB)을 UFD로 대웅시킨다. 한편, c) 두 부모 노드들(pA, pB)의 nMD 값과 Label 값이 다른 경우에는 A를 루트로 하는 서브트리가 pB로 MOV됨을 의미한다.
• 3333px;">p).i): 트리 T에 속한 노드 N_p의 Value(N_p)을 v₁에서 v₂로 바꾼다.
• 3 단계(배웅 관계의 하향식 확장) : 대옹이 확정된 노드의 자식 노드들의 다옹 여부률 결정하는 단계로 루트로부터 하향식으로 진행된다. r心에서 대옹이 확정된 임의 노드를 A, A의 T_new의 대옹 노드를 B, 그리고 A에는 대웅이 결정되지 않은 차식 노드들(cA[l..s])이 있다고 가정하자. B의 대옹이 결정되지 않은 자식노드들올 cB[l.
• 을 삭제한다. 단, XML 문서의 특성을 고려하여 X-tree의 루트 노드는 삭제할 수 없다고 가정한다.
• 그림 4의 알고리즘은 7泅의 루트 노 드로부터 갚이 우선 탐색하면서 적용된다. 이때 T_old와T_new의 루트 노드는 XML 문서의 특성에 의해 항상 대옹되는 것으로 가정한다. 따라서 본 단계는 끄泅의 루트 노드로부터 점진적으로 대응 관계를 확장해 나간다고 볼 수 있다.

제안 방법

• (1) 깊이 우선 검색을 통해 T_new의 모든 노드롤 방문하면서 INS, MOV, UPD 연산을 생성한다. 이때 대옹이 확정되지 않은 노드로부터 INS 연산을, Op가 MOV와 UPD인 노드로부터 각각 MOV, UPD 연산 올 생성한다.
• 본 절에서는 XML 문서의 데이터를 계층적 구조로 표현하기 위해, 그리고 트리 구조로 표현된 XML 문서의 변화를 탐지하기 위한 알고리즘의 기본 데이터 구조로서 X-tree롤 제안한다. 또한 X-tree에서 변화 탐지에 사용되는 핵심 개념인 노드 MD(message digest)와 트리 MD 에 대해 소개하고, X-tree를 통해 표현된 XML 문서의 변화를 나타내는 편집 연산과 편집 스크립트를 설명한다.
• 제시된 알고리즘에서는 서론에서 밝힌 바와 같이 MD4의 특성으로 서로 다른 서브트리가 서로 같은 서브트리 해시값을 갖올 확율은 극히 적다. 또한, 동일 트리 내에 동일한 서브트리 해시값이 존재할 경우, 대옹이 결정된 부모 노드를 이용하여 대옹 여부를 결정하도록 하여 BULD Diff 알고리즘의 후보 정렬 문제를 없앴다. 이로 인해 제시된 알고리즘은 N을 신 · 구 버전 문서의 전체 노드 수라 할 때의 시간 복잡도를 갖는다.
• 본 절에서는 XML 문서의 데이터를 계층적 구조로 표현하기 위해, 그리고 트리 구조로 표현된 XML 문서의 변화를 탐지하기 위한 알고리즘의 기본 데이터 구조로서 X-tree롤 제안한다. 또한 X-tree에서 변화 탐지에 사용되는 핵심 개념인 노드 MD(message digest)와 트리 MD 에 대해 소개하고, X-tree를 통해 표현된 XML 문서의 변화를 나타내는 편집 연산과 편집 스크립트를 설명한다.
• 2 단계(해웅 관계의 상향식 확장) : 현재까지 NOP나 UPD로 대응이 확장된 노드 쌍으로부터 루트 노드로의 경로 상에 있는 노드들에 대해 점진적으로 대응 여부룔 결정하는 단계이다. 우선 1단계에서 발견된 동등 서브트리 쌍의 각 루트 노드의 부모 노드들의 대옹 여부를 고려한다. 두 루트 노드풀을 각각 A, B라하고 이들의 부모 노드들을 각각 pA, pB라 할 때, a) 두 부모 노드들(pA, pB)의 nMD 값(Label과 Value 값)이 같으면 그 부모 노드둘(pA, pB)을 NOP로, b) 두 부모 노드돌의 nMD 값은 서로 다르지만 Label 값이 갈은 경우는 그 부모 노드들(pA, pB)을 UFD로 대웅시킨다.
• 이때 동등 서브트리의 쌍에 속한 모든 노드들은 대응 확정되었다고 한다. 이 과정에서는 T_new의 모든 노드들의 tMD값을 키로 해시테이블에 등록하고 T_old를 깊이 우선 탐색(Depth first Search)으로 검색하며 해시테이블에 해당 tMD가 존재하는지 여부를 확인한다. 이때 tMD의 정의에 따라 종동 토리의 발견시 그의 서브트리에 대한 탐색은 계속하지 않는다.
• 구 버전 문서의 모든 노드를 방문하면서 방문한 노드를 루트 노드로 하는 서브트리롤 32비트 해시값으로 나타내고 이룰 서브트리의 노드 개수를 나타내는 가중치와 함께 서브트리의 루트 노드에 저장한다. 한편 구 버전 문서에서 계산된 32비트 해시 값을 맵 M에 둥록하고, 신 버전 문서의 노드를, 가중치가 가장 큰 노드부터 방문하면서 방문한 노드의 서브트리 해시값이 맵 M에 등록되어 있는지를 검사한다. 이때, 동일한 서브트리 해시값을 갖는 구 버전 문서의 노드들을 후보(candidates)라 하고 가중치가 큰 순으로 이들 후보룔 정렬한 순서 큐(ordered queue)롤 이용하여 최적의 대웅을 찾는다.
• 한편 동등 서브트리를 찾기 위해 서브트리의 구조와 더불어 서브트리에 속한 노드들의 정보를 나타내는 해시값을 제안한다. 이는 메시지 변조 방지(integrity)에 사용되는 해시 알고리즘인 MD4(message digest alogrithm 4)[8]를 사용하여 계산된 값이다.
• 한편, 본 알고리즘에서는 X-tree 의 각 노드률 구별하기 위해 nID(node identifier)를 제안한다. nID는 X-tree T의 루트 노드 N_p에서 임의 노드 N_k까지의 경로(path) 상의 ILabel의 결합으로, nID(N_k)= .

성능/효과

• 두 루트 노드풀을 각각 A, B라하고 이들의 부모 노드들을 각각 pA, pB라 할 때, a) 두 부모 노드들(pA, pB)의 nMD 값(Label과 Value 값)이 같으면 그 부모 노드둘(pA, pB)을 NOP로, b) 두 부모 노드돌의 nMD 값은 서로 다르지만 Label 값이 갈은 경우는 그 부모 노드들(pA, pB)을 UFD로 대웅시킨다. 한편, c) 두 부모 노드들(pA, pB)의 nMD 값과 Label 값이 다른 경우에는 A를 루트로 하는 서브트리가 pB로 MOV됨을 의미한다. 이때 노드 A와 B를 MOV로 대응시킨다.
• 제시된 알고리즘에서는 서론에서 밝힌 바와 같이 MD4의 특성으로 서로 다른 서브트리가 서로 같은 서브트리 해시값을 갖올 확율은 극히 적다. 또한, 동일 트리 내에 동일한 서브트리 해시값이 존재할 경우, 대옹이 결정된 부모 노드를 이용하여 대옹 여부를 결정하도록 하여 BULD Diff 알고리즘의 후보 정렬 문제를 없앴다.

후속연구

• 현재 WIDS에서 사이트 별로 변화에 대한 패턴을 모으고 있으며 향후 변화에 대한 패턴을 이용하여 변화 탐지에 적용할 수 있는 방안올 연구할 계획이다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기