Yet Another Fast, Robust and Open Source Sentence Aligner. Time toReconsider Sentence Alignment?

Fethi Lamraoui, Philippe LanglaisMTSummit 2013 · OpenReview

Abstract

Fethi Lamraoui, Philippe Langlais. Proceedings of Machine Translation Summit XIV: Papers.

2013.

Introduction

In the early 1990s, the NLP community largely considered sentence alignment—the task of pairing corresponding sentences in a bilingual corpus—to be a solved issue. Most researchers relied on either simple length-based methods, which are fast but fail on noisy data, or complex lexical-based methods, which are robust but computationally expensive.

However, as datasets have grown to include millions of sentences and "noisier" sources like web-crawled text, legacy tools have hit a wall. Lexical aligners like BMA often require training complex models online, making them prohibitively slow for massive corpora. The authors argue for a middle ground: an aligner that is as fast as length-based methods but as robust as lexical ones.

Methods

YASA (Yet Another Sentence Aligner) employs a pragmatic, two-step pipeline:

  1. Cognate-based Search-Space Reduction: Instead of searching the entire alignment matrix, YASA identifies "cognates" (words with similar orthography across languages). It uses these to create a "dotplot" and applies dynamic programming to find a coarse, token-level alignment. This effectively prunes the search space, focusing subsequent steps on the most promising areas.
  2. Sentence Alignment: Once the search space is narrowed, YASA performs the final alignment using a scoring function that combines length-based features (assuming sentence lengths follow a normal distribution) and cognate-based features (a likelihood ratio estimating translation probability).

The system assumes monotonicity (sentence order is preserved), which allows it to remain extremely fast.

Experimental Setup

The authors evaluated YASA against two popular aligners, BMA and HUNALIGN, using:

  • BAF: A small-scale, multi-genre English-French corpus.
  • EUROPARL: A massive, multi-million sentence multilingual corpus of European Parliament proceedings.
  • HANS: An excerpt from the Canadian Hansards used for downstream translation testing.

Key Results and Insights

Efficiency at Scale

The most striking insight is the efficiency gap. While a lexical aligner like BMA might take over 30 hours to process a million sentence pairs, YASA finishes the same task in under 24 minutes. As shown in Figure 3, YASA maintains a massive speed advantage as the corpus size increases, performing roughly 75x faster than BMA on 1M sentence datasets.

Figure 3: Execution time (seconds) vs. number of sentences for YASA and BMA.

Robustness to Noise

Length-based aligners typically fall apart when text is deleted or added in one language. By using cognates as "anchors," YASA maintains high accuracy even when data is artificially corrupted. As detailed in Figure 4, when 60% noise was added to the institutional sub-corpus, YASA’s F-measure only dropped to 69.5, while BMA’s performance plummeted to 24.7 (indicated by the +44.8 gain for YASA).

Figure 4: Performance (F-measure) of YASA across different noise levels (%) and bitext types. Parentheses indicate gain over BMA.

Impact on Machine Translation

The paper demonstrates that better alignment has tangible benefits for downstream tasks. Using YASA to re-align the Europarl corpus led to measurable gains in BLEU scores for Statistical Machine Translation (SMT) systems, proving that alignment quality remains a critical factor in modern NLP pipelines.

Limitations and Future Work

YASA assumes sentences appear in the same order (monotonicity) and cannot handle "cross-alignments." Furthermore, its current cognate detection is optimized for Indo-European language pairs. Future versions could incorporate more modern phonetic or semantic similarity measures and utilize discriminative models to weight features more intelligently.

Conclusion

YASA’s high performance—despite being based on an algorithm written nearly 20 years prior to the paper—suggests that complex additions to alignment algorithms haven't necessarily translated to better real-world utility. By prioritizing speed and robustness, YASA offers a powerful tool for processing the massive, noisy parallel corpora required for modern research.

Summary updated

BibTeX
@inproceedings{lamraoui2013yet,
  author = {Fethi Lamraoui and Philippe Langlais},
  title = {{Yet Another Fast, Robust and Open Source Sentence Aligner. Time toReconsider Sentence Alignment?}},
  booktitle = {MTSummit},
  year = {2013},
  url = {https://openreview.net/forum?id=hVVz3ubxcqf},
}
Figure