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:
- 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.
- Shared-Memory Multithreading: Unlike previous extractors (such as the one in the
cdectoolkit) 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. - 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.
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