An O(N) bit-parallel algorithm for the unrestricted Damerau-Levenshtein distance

A bit-parallel algorithm for computing the unrestricted Damerau-Levenshtein edit distance that runs in O(N) time for patterns of length M ≤ 64, where N is the length of the query string. The algorithm improves on the state-of-the-art O(M·N) time complexity by exploiting 64-bit CPU word-level parallelism to process all M pattern positions simultaneously. The paper provides a proof of correctness through four lemmas establishing when transpositions need to be considered, and benchmarks demonstrating speedups of up to 65.7x over the reference O(M·N) implementation on an Intel Core Ultra 7 258V processor.