On aligning trees

On aligning trees Jo Calder University of Edinburgh Language Technology Group, Human Communication Research Centre and Centre for Cognitive Science 2 Buccleuch Place Edinburgh, Scotland EH8 9LW J. Ca].derCed. ac. uk Abstract The increasing availability of corpora anno- tated for linguistic structure prompts the question: if we have the same texts, anno- tated for phrase structure under two dif- ferent schemes, to what extent do the an- notations agree on structuring within the text? We suggest the term tree alignment to indicate the situation where two markup schemes choose to bracket off the same text elements. We propose a general method for determining agreement between two anal- yses. We then describe an efficient im- plementation, which is also modular in that the core of the implementation can be reused regardless of the format of markup used in the corpora. The output of the implementation on the Susanne and Penn treebank corpora is discussed. 1 Introduction We present here a general design for, and mod- ular implementation of, an algorithm for comput- ing areas of agreement between structurally anno- tated corpora. Roughly speaking, if two corpora bracket off the same stretches of words in their struc- tural analysis of a text, the corpora agree that that stretch of text should be considered a single unit at some level of structure. We will (borrowing a usage from (Church and Gale, 1993) term this agreement (sub)tree alignment. We make the following assumptions, which appear reasonable for markup schemes with which we are familiar: • the "content" of each text consists of a sequence of "terminal" elements. That is, the content is a collection of elements generally correspond- ing to words and punctuation and this will be roughly constant across the two corpora. It may also contain additional elements to represent, for example, the positing of orthographically null categories. • the two corpora whose trees are to be aligned contain identifiable structural markup. That is, structural "delimiters" are distinct from other forms of markup and content. • two corpora agree on an analysis when they bracket off the same content. • The corpora may contain additional markup provided this is distinct from content and struc- tural markup. Our goal, then, is to determine those stretches of a text's content which two corpora agree on. Why might we want to do this? There are several reasons: • increase confidence in markup and determine areas of disagreement If two or more corpora agree on parts of an anal- ysis, one may "trust" that choice of grouping more than those groupings on which the cor- pora differ. Alignment can be used to detect disagreements between manual annotators. • verify preservation of analyses across multiple versions of a corpus If all the subtrees of a corpus are aligned with those of another, then the second is consistent with the first, and represents analyses at least as detailed as those in the first. Such automatic checking will be useful both in the case of man- ual edits to a …

Content truncated to 500 words