Forming Grammars for Structured Documents

Discovery in Textual Documents

We consider the problem of finding a small regular grammar that correctly describes the structure of a large text with named components. Examples of such texts are dictionaries, user manuals, business letters, and so on. A structural description in the form of the regular grammar can be used, e.g., to help in retrieving information from the document. We start by constructing for each named component of the document a weighted finite-state automaton that accepts all the structures for that component that are present in the original document. The weight of a transition shows how many times the transition is used in the original document. This automaton is generalized by merging states and updating the weights until the automaton satisfies a certain context condition. The automata corresponding to different components in the document are also generalized with respect to each other. The generalized weighted automata are transformed into a series of regular expressions corresponding to the heavy paths in the automata.