Improve Sentence Alignment by Divide-and-conquer
This work addresses efficiency issues in sentence alignment for natural language processing applications, presenting an incremental improvement with specific computational gains.
The paper tackles the problem of slow sentence alignment by introducing a divide-and-conquer algorithm that reduces average time complexity from quadratic to O(NlogN), improving the Bleualign baseline by 3 F1 points on an OCR dataset and offering practical speed advantages over Vecalign under resource constraints.
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.