Fine-grained Change Detection in Structured Text Documents

Beitrag bei einer Tagung

Details zur Publikation

Autor(en): Dohrn H, Riehle D
Titel Sammelwerk: DocEng 2014 - Proceedings of the 2014 ACM Symposium on Document Engineering
Verlag: Association for Computing Machinery, Inc
Jahr der Veröffentlichung: 2014
Tagungsband: Proceedings of the 2014 Symposium on Document Engineering
Seitenbereich: 87-96


Detecting and understanding changes between document revisions is an important task. The acquired knowledge can be used to classify the nature of a new document revision or to support a human editor in the review process. While purely textual change detection algorithms offer fine-grained results, they do not understand the syntactic meaning of a change. By representing structured text documents as XML documents we can apply tree-to-tree correction algorithms to identify the syntactic nature of a change. Many algorithms for change detection in XML documents have been propsed but most of them focus on the intricacies of generic XML data and emphasize speed over the quality of the result. Structured text requires a change detection algorithm to pay close attention to the content in text nodes, however, recent algorithms treat text nodes as black boxes. We present an algorithm that combines the advantages of the purely textual approach with the advantages of tree-to-tree change detection by redistributing text from non-overlapping common substrings to the nodes of the trees. This allows us to not only spot changes in the structure but also in the text itself, thus achieving higher quality and a fine-grained result in linear time on average. The algorithm is evaluated by applying it to the corpus of structured text documents that can be found in the English Wikipedia.

FAU-Autoren / FAU-Herausgeber

Dohrn, Hannes
Professur für Open Source Software
Riehle, Dirk Prof. Dr.
Professur für Open Source Software


Dohrn, H., & Riehle, D. (2014). Fine-grained Change Detection in Structured Text Documents. In Proceedings of the 2014 Symposium on Document Engineering (pp. 87-96). Denver, Colorado, USA: Association for Computing Machinery, Inc.

Dohrn, Hannes, and Dirk Riehle. "Fine-grained Change Detection in Structured Text Documents." Proceedings of the The 14th Symposium on Document Engineering, Denver, Colorado, USA Association for Computing Machinery, Inc, 2014. 87-96.


Zuletzt aktualisiert 2018-09-08 um 23:23