A Portable Algorithm for Mapping Bitext Correspondence

I. Dan MelamedACL 1997 · DOI

Abstract

The Smooth Injective Map Recognizer (SIMR) is a high-performance algorithm designed for bitext mapping—the process of aligning a source text with its translation. By framing alignment as a geometric pattern recognition problem at the word level, SIMR achieves significant improvements in accuracy over traditional sentence-based methods while maintaining linear time and memory complexity. This paper details the algorithm's methodology, its robustness to noisy data, and its portability across diverse language pairs.

Introduction

In multilingual Natural Language Processing (NLP), the primary resource is often a bitext: a document available in two languages. Constructing translation models or bilingual dictionaries requires precise knowledge of which segments in the source text correspond to segments in the target text.

Historically, alignment was performed at the sentence level. However, sentence-level heuristics often fail when texts are noisy (e.g., OCR errors), translations are non-literal (merging or splitting sentences), or formatting elements like tables and footnotes disrupt standard markers. I. Dan Melamed proposes a "portable" algorithm that avoids language-specific sentence markers and handles the irregularities of real-world documents by operating on a 2D geometric plane.

Methodology: The SIMR Algorithm

SIMR treats bitext alignment as a search for "True Points of Correspondence" (TPCs) in a geometric space. If the x-axis represents the source text and the y-axis represents the translation, a perfect literal translation would appear as a diagonal line from the origin to the terminus.

The Expanding Rectangle Strategy

SIMR employs a greedy, local search mechanism rather than global optimization:

  1. Point Generation: Candidate matches are identified using "matching predicates," such as cognates or small translation lexicons.
  2. Chain Recognition: The algorithm identifies "chains" of points that are linear, maintain a slope consistent with the document's overall trajectory, and are "injective" (ensuring a one-to-one mapping).
  3. Expansion: When a suitable chain is not immediately found, SIMR proportionally expands its search rectangle. This allows it to bypass "gaps" caused by omissions or significant reorderings.
The SIMR search strategy using an expanding rectangle to find the next chain of True Points of Correspondence (TPCs).

Localized Noise Filtering

A critical innovation in SIMR is its handling of "noise." High-frequency words (e.g., "the", "a") often create numerous false matches. SIMR calculates a "point ambiguity level" based on the density of matches within the current search rectangle. This allows the algorithm to dynamically ignore high-frequency noise while still utilizing those same words as anchors in sections where they appear uniquely.

Evaluation and Datasets

The algorithm's performance was validated across three distinct language pairs and multiple genres:

  • French/English: Utilizing the BAF corpus, including parliamentary debates, technical reports, court transcripts, and UN reports.
  • Spanish/English: Software manuals from Sun MicroSystems Solaris AnswerBooks.
  • Korean/English: Military manuals and messages.

Key Results

SIMR demonstrated exceptional accuracy and efficiency across all test cases. On parliamentary debate data, SIMR achieved a Root Mean Squared (RMS) error of 5.7 characters. In contrast, the previous state-of-the-art char_align algorithm produced an error of 57 characters, making SIMR ten times more precise.

RMS error performance of SIMR across various language pairs and document genres.

Furthermore, the algorithm's running time and memory requirements scale linearly with input size, facilitating the processing of massive bitext corpora. Its portability was proven by the minimal effort required to adapt the system to the Korean/English pair, necessitating only a basic axis generator and matching predicate.

Conclusion

By prioritizing geometric patterns over linguistic heuristics, SIMR provides a robust, scalable, and portable solution for bitext alignment. While the algorithm requires initial parameter tuning and lacks long-range "look-ahead" capabilities, its performance on noisy, real-world data sets a new benchmark for the field. Future work involves integrating SIMR into iterative cycles to refine translation lexicons and further improve mapping accuracy.

Reference: Melamed, I. D. (1997). A Portable Algorithm for Mapping Bitext Correspondence. University of Pennsylvania.

Summary updated

BibTeX
@inproceedings{melamed1997portable,
  author = {I. Dan Melamed},
  title = {{A Portable Algorithm for Mapping Bitext Correspondence}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1997},
  doi = {10.3115/976909.979656},
}
Figure