Earticle

To extract structural features from tree-structured documents among nodes in which characteristic words appear, we described a text-mining algorithm for enumerating all frequent consecutive path patterns (CPP) on a list W of words in Uchida et al., PAKDD 2004 [14]. In this paper, we first extend a CPP to a tree pattern, which is called a tree association pattern (TAP), over a set W of words. A TAP is an ordered rooted tree t such that the root of t has no child or at least two children, all leaves of t are labeled with non-empty subsets of W and all internal nodes, if they exist, are labeled with strings. By modifying text-mining algorithms to find all frequent CPPs, next, we present text-mining algorithms for enumerating all maximal frequent TAPs in tree-structured documents, where a TAP t is maximal if there exists no frequent TAP, which has t as a proper subpattern. Then, we tested our algorithms using Reuters news wires. Finally, as one application of CPPs, we present an algorithm for a wrapper based on CPP using XSLT transformation language and demonstrate simply the use of the wrapper to translate one of the Reuters news wires into other XML document.

웹, XML, 오피스 어플리케이션에 사용되는 대부분의 문서들은 트리 구조로 구성되어 있으며 특히 다중 사용자 환경에서의 트리 구조의 문서의 차이 발견, 합병, 버전 제어 등의 연구가 활발하다. 그러나 이들의 기초가 되는 편집스크립트에 대한 연구는 초보적인 상태에 있다. 본 논문에서는 편집연산들의 실행 시 트리구조의 문서의 변화를 이해하기 위한 문서 모델을 제시하고 편집연산들의 실행 효과의 분석을 통해 트리 구조 문서에 대한 인접한 편집연산들의 순서 교환 방법을 제안한다. 트리 구조 문서에 대한 변화탐지의 결과로 생성되는 편집스크립트들은 대부분 기본연산들(갱신, 삽입, 삭제)만으로 구성된다. 그러나 이동, 복사연산을 포함하는 경우, 이들의 복합연산의 특성으로 인해 주로 2단계 패스의 실행을 전제로 하는 편집스크립트를 생성한다. 본 논문에서는 제안한 편집 연산들의 순서 교환 방법을 통해 2단계 패스의 실행을 전제로 하는 X-treeESgen의 편집스크립트를 단일 패스로 변환하는 알고리즘을 제시한다.

Since most documents used in web, XML, office applications are tree-structured, diff, merge, and version control for tree-structured documents in multi-user environments are crucial tasks. However research on edit scripts which is a basis for them is in primitive stage. In this paper, we present a document model for understanding the change of tree-structured documents as edit scripts are executed, and propose a method of switching adjacent edit operations on tree-structured documents based on the analysis of the effects of edit operations. Mostly, edit scripts which are produced as the results of diff on tree-structured documents only consist of basic operations such as update, insert, delete. However, when move and copy are included in edit scripts, because of the characteristics of their complex operation, it is often that edit scripts are generated to execute in two passes. In this paper, using the proposed method of switching edit operations, we present an algorithm of transforming the edit scripts of X-treeESgen, which are designed to execute in two passes, into the ones that can be executed in one pass.