Optimizing the weighted sequence alignment algorithm for large-scale text similarity computation (2022)

Abstract: We present an optimized implementation of the weighted sequence alignment algorithm (a.k.a. weighted edit distance) in a scenario where the items to align are numeric vectors and the substitution weights are determined by their cosine similarity. The optimization relies on using vector and matrix operations provided by numeric computation libraries (including GPU acceleration) instead of loops. The resulting algorithm provides an efficient way of aligning large sets of texts represented as sequences of continuous-space numeric vectors (embeddings). The optimization made it possible to compute alignment-based similarity for all pairs of texts in a large corpus of Finnic oral folk poetry for the purpose of studying intertextuality in the oral tradition.

## introduction sequence alignment algorithms have a long history of usage in both bioinformatics and natural language processing (nlp). the concept of 'edit distance' dates back to @xcite , while a dynamic algorithm for its performant computation was presented independently at least by @xcite and @xcite . with the popularization of the concept of embeddings in nlp, units of text (typically words) are often represented as vectors in a high-dimensional continuous space, with some similarity measure on such vectors (typically cosine similarity) capturing abstract similarity between those units (e.g. similarity of words in meaning). 1 this opens up the possibility of non-exact sequential comparison of texts using weighted alignment with cosine similarities of embedding vectors as weights. a concrete example of such computation was recently presented by @xcite , who apply alignment to study intertextuality in old poems of the finnish people (suomen kansan vanhat runot, skvr) -a large collection of finnic folk poetry recorded from oral tradition. in janicki et al.'s article, texts are represented as sequences of lines and the similarity measure for lines is defined based on bag-of-bigrams vector representation. although this is a very simple kind of embedding, it was proven useful in tackling the high linguistic variation that characterizes this corpus. however, due to the size of the corpus (around 90,000 texts), the authors were only able to compute the alignment-based similarity between pairs of poems pre-selected based on certain criteria, which might miss some interesting cases. 2 in this paper, we are going to present an optimization of the alignment computation which allows one to deal with large amounts of texts. it can be used to compute an alignment between every single pair of poems in skvr using janicki et al.'s embedding method. more generally, it can be applied to find similar passages in any large collection of texts using an embedding representation of smaller text units (e.g. words or lines) as basis for similarity. as the present short paper is incremental work focused on optimizing a particular well-known, general-purpose algorithm, we limit the discussion on its application in the study of finnic folk poetry to a short example in section 4 showing the benefit of the current improvements. for a broader digital humanities context and a more thorough discussion of using text similarity in the study of oral tradition, the reader may be referred to @xcite . existing approaches. most available python packages for sequence alignment are either de-signed specifically for biological sequences (like e.g. bio.align foot_2 ) or very simple pure-python implementations of the base algorithm (like e.g. alignment foot_3 , edit-distance foot_4 ). a notable example of a library allowing for alignment of sequences of numeric vectors using a custom similarity measure, as well as providing a fast c++ implementation, is pyalign foot_5 . however, as we will see in sec. 3, it does not provide sufficient performance to solve the problems addressed here. optimizations to the base algorithm are typically based on restricting the allowed edit distance to a small number and pre-selecting or filtering candidate pairs (e.g. @xcite . for handling large numbers of strings, also finite state automata have been used @xcite . however, these methods are only applicable to sequences of symbols from a finite alphabet. ## benchmarks in order to test the optimizations, we compute pairwise maximum-weight alignment matrices for poems from the skvr collection, using the vectorization of verses as bags of character bigrams (following @xcite . we conduct the experiments on subsets of the collection with different sizes, comparing the following algorithm variants: 0 no optimizations -the alignment matrix is computed for each pair of documents separately using the standard dynamic programming algorithm implemented as a python loop. s is precomputed as a single dot product per target document.) in all the variants, we applied a threshold of 0.5 on the similarity of individual items and then rescaled the values to the interval [0, 1]. this was done to avoid false positives, but it should not influence the runtime of the algorithm. the benchmarks were run on a mid-range desktop pc with an 8threaded intel core i7-6700 3.4 ghz cpu and a geforce gtx 1060 gpu. the results are shown in ## application using the optimized algorithm, we are able to compute alignment-based similarity between every single poem pair in the skvr collection, and thus get rid of the pre-selection criteria employed by @xcite the algorithm is scalable enough to be practically usable even if the skvr collection is combined with further corpora of similar size. in our current research, we combine skvr with the estonian runosongs database foot_8 (eesti regilaulude andmebaas, erab), which contains around 100,000 documents. this allows us to search for cross-dataset and cross-lingual similarities. an example for this is given in the threshold used by the current method is 0.5, which allows us to align the verse pairs with similarity scores marked in bold. because there are quite many alignable pairs, the poems will be easily recognized as similar. on the other hand, the method described by @xcite required the poems to share verse pairs with similarity of at least 0.8 in order to be considered for alignment. such pairs do not occur here, and thus this poem pair would go unrecognized. furthermore, the runtime of the current method does not depend on the threshold (unlike the former), so it could be adjusted to any lower value if needed. the only limitation for that is that values below 0.5 are increasingly common for completely unrelated lines, so lowering the threshold increases the number of false positives. ## conclusion we have presented an optimized version of the maximum-weight sequence alignment algorithm (a variant of the weighted edit distance algorithm, a.k.a. needleman-wunsch or wagner-fisher algorithm). the optimization utilizes matrix operations for efficient computation on a large number of sequences. the weighted alignment can be used for non-exact comparison of texts, in which individual text units (like words or poetry lines) are represented with embeddings. the presented optimization made it possible to compute alignment-based similarity scores for all pairs of poems within a large collection of finnic oral folk poetry, opening possibilities for a large-scale quantitative study of intertextuality in the finnic oral tradition.