A Fast and Simple Online Synchronous Context Free Grammar Extractor

Paul Baltescu, Phil BlunsomPrague Bull. Math. Linguistics 2014 · OpenReview

Introduction

In hierarchical phrase-based machine translation, systems learn complex translation rules that include "gaps" or non-terminals (e.g., mapping the French ne [X] pas to the English not [X]). Because the number of possible rules grows exponentially with phrase length, pre-calculating and storing every possible rule is infeasible for large datasets.

To address this, researchers utilize online grammar extraction, where relevant rules are retrieved from a word-aligned corpus "on the fly" during translation. However, these lookups frequently become the primary bottleneck in the translation pipeline. This paper introduces a high-performance, open-source grammar extractor that optimizes rule search and utilizes a multithreaded C++ architecture to achieve significant speedups and memory efficiency.

Methodology

The authors' approach builds upon suffix arrays, a memory-efficient data structure for fast pattern matching. The core innovations include:

  1. Optimized Intersection Algorithm: Searching for phrases with gaps requires finding where two words appear within a specific proximity. While previous methods had a time complexity based on the sum of word occurrences, the authors introduced a technique reducing this to the minimum of the two occurrence lists, $O(\min(|M_{aeta}|, |M_{eta c}|))$, making the search asymptotically faster.
  2. Shared-Memory Multithreading: Unlike previous extractors (such as the one in the cdec toolkit) that used a multi-process approach—requiring each CPU core to maintain its own copy of massive data structures—this implementation uses a single shared-memory space across multiple threads.
  3. Precomputed Indexing: The search for frequent discontiguous phrases is further optimized using a Longest Common Prefix (LCP) array.

Experimental Setup

The system was evaluated using the Europarl-v7 French-English corpus, consisting of approximately 2 million sentence pairs (104 million tokens). The corpus was word-aligned using fast_align. Performance was tested against the existing Cython-based extractor in the cdec toolkit using the newstest2012 evaluation set.

Key Results

The proposed C++ implementation demonstrated substantial improvements across all performance metrics:

  • Extraction Speed: The new algorithm achieved a 4x speedup in extraction time compared to the original Cython-based extractor.
  • Preprocessing Efficiency: Preprocessing time was reduced from approximately 28 minutes to under 3 minutes, representing a 10-fold reduction.
  • Memory Footprint: By utilizing a shared-memory architecture, the system scales efficiently. In a parallel setup with 8 threads, the new system required only 6.1 GB of RAM, compared to 35.2 GB for the original multi-process version—a nearly 6x reduction.
Table 1: Comparison of extraction time and memory usage across different implementations.
Table 2: Comparison of preprocessing time and memory usage across different implementations.

Conclusion

This work demonstrates that algorithmic refinements and modern engineering practices can significantly alleviate the computational burdens of online grammar extraction. By shifting from $O(N+M)$ to $O(\min(N,M))$ complexity and adopting a shared-memory C++ architecture, the authors provide a tool that is both faster and more accessible for researchers working on commodity hardware. While the field has largely moved toward Neural Machine Translation, these string-matching optimizations remain highly relevant for any large-scale pattern matching tasks in natural language processing.

Summary updated

BibTeX
@inproceedings{baltescu2014fast,
  author = {Paul Baltescu and Phil Blunsom},
  title = {{A Fast and Simple Online Synchronous Context Free Grammar Extractor}},
  booktitle = {Prague Bull. Math. Linguistics},
  year = {2014},
  url = {https://openreview.net/forum?id=CR3Yuu31OF5},
}
Figure