Structuring Documents Efficiently

Proceedings of the Australasian Language Technology Workshop 2005, pages 120–126, Sydney, Australia, December 2005. Structuring Documents Efficiently Robert Marshall, Steven Bird and Peter J. Stuckey∗ Department of Computer Science and Software Engineering University of Melbourne, Victoria 3010, Australia {robertgm,sb,pjs}@csse.unimelb.edu.au ∗NICTA Victoria Laboratory Abstract Documents are typically marked up to enable ren- dering and to facilitate reuse. However, retargetting a document often requires pervasive changes to the markup. Power et al. have proposed a new level of representation called document structure which captures just those aspects of graphical organisation that are significant for conveying meaning. These document structures can be generated automatically from rhetorical structures, abstract representations of the meaning of a text. The mapping is highly indeterminate, being governed by a large number of interacting constraints. We present a constraint pro- gramming approach to the problem, and report on early experiments with an implementation in Pro- log. 1 Introduction Documents are typically marked up to enable ren- dering and to facilitate reuse. Simple adjustments in layout and style can be implemented without touch- ing the source document. However, retargetting a document often requires pervasive changes to the markup itself — e.g. changing a bulleted list to an inline list — a fact which suggests that the markup is not sufficiently abstract. Recent research by Power et al. (2003) has iden- tified a new level of representation called document structure which captures just those aspects of graph- ical organisation that are significant for conveying meaning. These representations can be generated automatically from rhetorical structures, abstract representations of the meaning of a text. Different document structures corresponding to the same rhetorical structures represent different realizations of the text. We may want to consider different document structures for the same rhetorical structure for a number of reasons. One document structure may be easier to understand than another for the same rhetorical structure. For example a bulleted list usually provides a clearer separation of which items form part of the list than an inline comma separated list. Alternatively, some document structures may have a much more compact representation which may be essential for viewing on a PDA screen with limited size, a constraint that is irrelevant when viewing the same document on a large screen. In this paper we concentrate on finding document structures that minimize the number of “defects”, a somewhat artificial measure of comprehensibility flaws from Power et al. (2003). The mapping from rhetorical structure to docu- ment structure is highly indeterminate, being gov- erned by a large number of interacting constraints. The existing implementation method is to generate all possible document structures corresponding to a given rhetorical structure, evaluate them against the constraints, and find the best solution (minimizing “defects”). However, this method does not scale since the search space is exponential in the size of the document. We present a constraint programming approach to the problem, in which an objective function is stated in advance in order to greatly prune the search space. We report on early experiments with an …

Content truncated to 500 words