# Improve Sentence Alignment by Divide-and-conquer

arXiv: https://arxiv.org/abs/2201.06907 · HTML: https://mlsanity.com/paper/2201.06907/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 24 references that are in the map.
- First posted on arXiv 18 Jan 2022.

## Builds on (most cited first, 5 of 5)

- [Achieving Human Parity on Automatic Chinese to English News Translation](https://mlsanity.com/paper/1803.05567/) (2018)
- [Margin-based Parallel Corpus Mining with Multilingual Sentence Embeddings](https://mlsanity.com/paper/1811.01136/) (2018)
- [Effective Parallel Corpus Mining using Bilingual Sentence Embeddings](https://mlsanity.com/paper/1807.11906/) (2018)
- [Low-Resource Corpus Filtering using Multilingual Sentence Embeddings](https://mlsanity.com/paper/1906.08885/) (2019)
- [Building a Balanced k-d Tree in O(kn log n) Time](https://mlsanity.com/paper/1410.5420/) (2014)

## Abstract (arXiv)

In this paper, we introduce a divide-and-conquer algorithm to improve sentence alignment speed. We utilize external bilingual sentence embeddings to find accurate hard delimiters for the parallel texts to be aligned. We use Monte Carlo simulation to show experimentally that using this divide-and-conquer algorithm, we can turn any quadratic time complexity sentence alignment algorithm into an algorithm with average time complexity of O(NlogN). On a standard OCR-generated dataset, our method improves the Bleualign baseline by 3 F1 points. Besides, when computational resources are restricted, our algorithm is faster than Vecalign in practice.