| 한글제목(Korean Title) |
경로 매칭 알고리즘을 이용한 구조화된 문서의 변화 탐지 |
| 영문제목(English Title) |
Change Detection of Structured Documents using Path-Matching Algorithm |
| 저자(Author) |
이경호
변창원
최윤철
고견
|
| 원문수록처(Citation) |
VOL 28 NO. 04 PP. 0606 ~ 0619 (2001. 12) |
한글내용
(Korean Abstract) |
본 논문에서는 SGML/XML 문서의 구 버전과 신 버전간의 차이를 계산할 수 있는 효율적인 알고리즘을 제안한다. 차이는 구 버전의 문서를 신 버전으로 변환하는데 소요되는 편집 스크립트로 간주할 수 있다. 제안된 알고리즘은 상향식과 하향식의 복합적인 접근 방식을 적용한다. 먼저 두 버전을 구성하는 노드간의 대응관계를 상향식으로 생성하며 하향식 너비 우선 탐색을 적용하여 편집 스크립트를 계산한다. 제안된 알고리즘은 모든 노드간의 대응 여부를 모두 조사할 필요가 없기 때문에 대응관계를 보다 빠르게 생성할 수 있다. 또한 삽입, 삭제, 그리고 갱신의 단순한 변화는 물론이고 부트리 이동과 복사의 구조적으로 보다 의미 있는 변화를 탐지할 수 있다. |
영문내용
(English Abstract) |
This paper presents an efficient algorithm to compute differences between old and new versions of an SGML/XML document. The difference between the two versions can be considered to be an edit script that transforms one document tree into another. The proposed algorithm is based on hybridization of bottom-up and top-down methods: matching relationships between nodes in the two versions are produced in a bottom-up manner and top-down breadth-first search computes an edit script. Because the algorithm does not need to investigate possible existence of matchings for all nodes, faster matching can be achieved. Furthermore, it can detect more structurally meaningful changes such as subtree move and copy as well as simple changes to the node itself like insert, delete, and update. |
| 키워드(Keyword) |
SGML
XML
노드
|
| 파일첨부 |
PDF 다운로드
|
