S ent A lign: Accurate and Scalable Sentence Alignment (2023)

Abstract: We present SentAlign, an accurate sentence alignment tool designed to handle very large parallel document pairs. Given user-defined parameters, the alignment algorithm evaluates all possible alignment paths in fairly large documents of thousands of sentences and uses a divide-and-conquer approach to align documents containing tens of thousands of sentences. The scoring function is based on LaBSE bilingual sentence representations. SentAlign outperforms five other sentence alignment tools when evaluated on two different evaluation sets, German-French and English-Icelandic, and on a downstream machine translation task.

## introduction sentence alignment is the task of finding matching sentences in two parallel documents, as illustrated in figure 1 . it can be seen as a path-finding problem, with a list of source sentences on one axis in a two-dimensional graph and the target sentences on the other, as demonstrated in figure 2 . each potential sentence pair is represented by a node in the graph, or nodes when multiple sentences are grouped together. the nodes are assigned values figure 1 : an automatic sentence alignment system aims to align source sentences s 1 , ..., s n with target sentences t 1 , ..., t n while using as few sentences as possible for each alignment. the figure shows examples of six alignment functions being applied while aligning eight sentences in icelandic with eight sentences in english: contraction (n-1), expansion (1-n), deletion (1-0), insertion (0-1), substitution (1-1) and merging (n-m). sentence alignment is a necessary processing step for parallel corpora to be useful for machine translation (mt). neural machine translation (nmt) has been shown to be sensitive to misaligned training data (e.g. @xcite ) so an accurate sentence aligner is highly important for nmt to unleash the full potential of the parallel corpora it is trained on. in this paper, we present sentalign, 1 a sentence aligner with a user-friendly command line interface, able to align very large documents. as shown in section 4 it outperforms other available sentence aligners when evaluated on a common evaluation set, as well as on a downstream mt task. sentalign evaluates all possible alignment paths in fairly large documents, with up to a few thousand sentences in each language, and activates a divide-and-conquer (dac) approach to reduce running time when the number of sentences exceed a user-defined threshold. to identify matching sentences in two languages, sentalign applies a scoring mechanism based on labse @xcite , a model trained and optimized to produce similar representations for bilingual sentence pairs. the model, which employs both a masked language model @xcite and a translation language model @xcite , is pretrained on monolingual and bilingual data in 109 languages. gargantua @xcite uses a twostep clustering approach to sentence alignment. it aims to find 1-n and n-1 alignments, but does not search for many-to-many alignments. it uses sentence length-based statistics considering relative lengths in comparison to the mean length of source and target sentences, and translation likelihoods of each target word with all source words, according to ibm model-1 @xcite . it starts by looking for optimal alignments through the alignment matrix consisting only of 0-1, 1-0 and 1-1 correspondences. in a second step, the previously acquired alignments are merged into clusters containing up to r sentences (4 by default) on either the source or target size, and if the merge produces a better score it is accepted. the final alignments are found when an optimal score has been obtained for the whole graph. bleualign @xcite uses mt and bleu @xcite to align sentences. even though bleu has been criticised as a measure of translation quality and is not considered reliable on a sentence level @xcite , the authors of bleualign point out that judging the quality of a translation is harder than deciding whether two sentences are possible translations of each other. furthermore, they find that bleu is very sensitive to misalignments, indicating that it should be capable of discriminating between aligned and unaligned sentence pairs. bleu is usually measured on up to 4-grams. too often, for the purposes of sentence alignment, this yields a score of 0 so bleualign uses 2-grams. furthermore, when comparing two sentences, the bleu scores are different depending on which of the sentences is the hypothesis, due to the brevity penalty in bleu. therefore, bleualign translates both directions when possible and uses the mean as the final score. in the first pass of the alignment algorithm, a set of 1-1 beads are identified. in the second pass, all unaligned sentences that fall between the beads, are extracted and a list generated of all possible 1-, 2-or 3-sentence sequences composed of the unaligned sentences and the beads. bleu scores are then calculated for the cartesian product of the two lists. if any 1-n alignment scores higher than the bead, it is replaced in the graph and the step is repeated. in vecalign, @xcite use the similarity between sentence embeddings as the scoring function, employing laser (artetxe and schwenk, 2019) for scoring alignment candidates. in the alignment algorithm, recursive approximation is used to reduce the search space. ## the sentalign system in this section, we present sentalign, a highly accurate sentence aligner capable of evaluating all possible alignment paths through fairly large documents, using a labse-based scoring mechanism. our alignment approach is of quadratic complexity, o(n 2 ), and in order to handle very large files, we apply a dac approach. when the total nodes in the alignment graph exceed a user-defined maximum, by default set to 4, 000, 000, the dac-mechanism is activated in order to reduce the time complexity when aligning the documents. the main components of the sentalign system illustrated in figure 3 are the scoring mechanism, the alignment or pathfinding algorithm, a dac-module to deal with very large files, and a readjustment module to compensate for shortcomings in the scoring mechanism. ## evaluation we evaluated sentalign by comparing the system to other sentence aligners, both using sentence alignment evaluation sets and by testing the impact on downstream mt task. ## conclusion sentalign is an accurate, scalable and easy-to-use sentence alignment system. it uses the labse model, which has been trained to generate sentence embeddings in 109 languages, to score alignment candidates. the alignment algorithm considers all possible paths through the alignment graph where the number of merges for adjoining sentences in each language is under a user-set threshold, and the maximum number of nodes in the search space is less than the dac-threshold. evaluation on two sentence alignment evaluation sets, as well as on a downstream mt task, show that the aligner is highly competitive, outperforming other alignment systems in most regards. sentalign is distributed under an apache 2.0 licence.