Abstract
This paper introduces a formal method and a modular tool for tree alignment, the process of identifying structural agreement between different linguistic annotation schemes applied to the same text. By prioritizing the "yield" (the span of words) over specific node labels, the approach enables the comparison, merging, and validation of diverse treebanks such as the Susanne Corpus and the Penn Treebank.
Introduction
In computational linguistics, treebanks serve as essential corpora where sentences are annotated with hierarchical syntactic structures. However, different projects often employ distinct markup schemes; some are highly nested and detailed, while others are relatively flat. This lack of standardization makes it difficult to measure agreement between different annotations of the same text. Because naming conventions and structural philosophies vary, a simple node-for-node comparison is insufficient. This research addresses the need for a robust, automated method to find "common ground" between disparate structural analyses, a critical step for increasing confidence in manual annotations and facilitating information transfer between corpora.
Methodology
The proposed algorithm, implemented as a modular tool, abstracts away from specific markup formats to focus on structural boundaries. The process is divided into three primary stages:
- Terminal Alignment: The system identifies the terminal elements (words and punctuation) of both corpora. Using a modified version of the standard
diffutility, it creates a mapping between the two texts. This step is designed to be robust against minor editorial variations or differences in punctuation handling. - Subtree Indexing: The "yield" of a subtree is defined as the specific sequence of terminal elements it encompasses. The algorithm constructs a hash table where keys represent the start and end indices of these yields.
- Alignment Detection: To identify matches, the algorithm checks if a subtree in the "left" corpus shares the same terminal yield (under the established mapping) as a subtree in the "right" corpus. Subtrees with identical boundaries are considered "aligned," regardless of their specific labels.
Experimental Evaluation
The algorithm was evaluated using overlapping portions of the Brown Corpus annotated by two major projects: the Susanne Corpus (developed by Geoffrey Sampson) and the Penn Treebank (Marcus et al., 1993).
Terminal and Structural Results
The comparison revealed both the strengths of the alignment method and the inherent differences between the two schemes:
- Terminal Match: 93% of Susanne's terminal elements were successfully mapped to the Penn Treebank.
- Structural Agreement: Approximately 70% of the trees in the Susanne Corpus aligned with trees in the Penn Treebank.
- Articulation Density: The Penn Treebank proved to be significantly more "articulated" or nested. Only 59% of Penn's trees had a corresponding match in Susanne, confirming that the Penn Treebank generally provides a more granular breakdown of sentence structure.
Key Insights and Discussion
The central insight of this work is that the yield serves as a universal currency for comparison. While labels like "NP" or "Nns" vary wildly, the boundaries of a constituent represent a more objective point of agreement. If two distinct theories agree that a specific span of words forms a single unit, that agreement is statistically and linguistically significant.
Furthermore, the system utilizes a "stand-off" annotation approach. Rather than creating a new merged file, it generates alignment tables. This preserves the integrity of the original data while providing a new layer of cross-corpus information.
Limitations and Future Work
Currently, the algorithm assumes strictly nested trees and cannot handle overlapping or crossing brackets found in some complex markup schemes. Additionally, while the tool identifies boundary agreement, it does not yet analyze the semantic consistency of the labels themselves. Future research should investigate whether specific labels (e.g., Noun Phrases) show higher cross-corpus consistency than others (e.g., Prepositional Phrases). Finally, the success of the process remains dependent on effective normalization to strip away irrelevant markup before the initial diff stage.
Summary updated