Supervised learning for the legacy document conversion

ABSTRACT

We consider the problem of document conversion from the rendering-oriented HTML markup into a semantic-oriented XML annotation defined by user-specific DTDs or XML Schema descriptions. We represent both source and target documents as rooted ordered trees so the conversion can be achieved by applying a set of tree transformations. We apply the supervised learning framework to the conversion task according to which the tree transformations are learned from a set of training examples. %Because of the complexity of tree-to-tree transformations, We develop a two-step approach to the conversion problem, that first labels leaves in the source trees and then recomposes target trees from the leaf labels. We present two solutions based of the leaf classification with the target terminals and paths. Moreover, we develop three methods for the leaf classification. All methods and solutions have been tested on two real collections.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Oronzo Altamura, Floriana Esposito, and Donato Malerba. Transforming paper documents into XML format with WISDOM++. IJDAR, 4(1):2--17, 2001.
• 4: N. Ashish and C. Knoblock. Wrapper generation for semi-structured internet sources. In Proc. ACM SIGMOD Workshop on Management of Semistructured Data, 1997.
• 5: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 6: Peter F. Brown , Peter V. deSouza , Robert L. Mercer , Vincent J. Della Pietra , Jenifer C. Lai, Class-based n-gram models of natural language, Computational Linguistics, v.18 n.4, p.467-479, December 1992
• 7: Reverse Engineering for Web Data: From Visual to Semantic Structures, Proceedings of the 18th International Conference on Data Engineering, p.53, February 26-March 01, 2002
• 8: Thomas G. Dietterich, Machine Learning for Sequential Data: A Review, Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, p.15-30, August 06-09, 2002
• 9: Eila Kuikka , Paula Leinonen , Martti Penttonen, Towards automating of document structure transformations, Proceedings of the 2002 ACM symposium on Document engineering, November 08-09, 2002, McLean, Virginia, USA [doi>10.1145/585058.585078]
• 10: Dayne Freitag, Information extraction from HTML: application of a general machine learning approach, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.517-523, July 1998, Madison, Wisconsin, United States
• 11: I4I - The WORD is XML. www.i4i.com/life sciences.htm.
• 12: Thorsten Joachims, A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.143-151, July 08-12, 1997
• 13: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 14: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.11-22, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335171]
• 15: Frank Neven, Automata theory for XML researchers, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601869]
• 16: OmniPage Pro 14 Office. http://www.scansoft.com/omnipage/.
• 17: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 18: W2X Convertor. www.turnkey.com.au/site/xice/xice/convert.html.
• 19: Y. Wang, I. T. Phillips, and R. Haralick. From image to SGML/XML representation: One method. In International Workshop on Document Layout Interpretation and Its Applications (DLIAP'99), Bangalore, India, September 1999.
• 20: D. Wood. Standard Generalized Markup Language: Mathematical and philosophical issues. Lecture Notes in Computer Science, 1000:344--365, 1995.
• 21: Word and YAWC: A Poor Mans' XML Publishing Environment. www.idealliance.org/papers/xmle02/dx_xmle02/html/abstract/02-06-04.html.
• 22: Yasubumi Sakakibara, Recent advances of grammatical inference, Theoretical Computer Science, v.185 n.1, p.15-45, Oct. 10, 1997 [doi>10.1016/S0304-3975(97)00014-5]
• 23: Jeonghee Yi , Neel Sundaresan, A classifier for semi-structured documents, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.340-344, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347164]
• 24: Mohammed J. Zaki , Charu C. Aggarwal, XRules: an effective structural classifier for XML data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956787]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Markup languages

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Documentation, Languages, Performance

Keywords:
XML markup, legacy document conversion, machine learning