File EditDistance.h

↰ Parent directory (ADS/string)

The engineered edit distance, longest common subsequence and approximate search, beyond the book: the ones that the benchmark of the distances compares with edlib and rapidfuzz-cpp, while editDistance(), stringMatching() [see File ApproximateMatching.h] and lcs() [see File LongestCommonSubsequence.h] stay the dynamic programming of the textbook, :math:` Theta( m n ) ` time.

Definition (ADS/string/EditDistance.h)

Detailed Description

For a pattern P of m bytes (the column) and a text T of n bytes, the table of the distances is :math:`[
D[ i ][ j ] = min{ D[ i - 1 ][ j - 1 ] + [ P[ i - 1 ] ne T[ j - 1 ] ]

, D[ i - 1 ][ j ] + 1 , D[ i ][ j - 1 ] + 1 } ,

` with :math:` D[ i ][ 0 ] = i ` and :math:` D[ 0 ][ j ] = j ` for the distance (0 for the search), whose adjacent cells differ by -1, 0 or +1. The bit vectors of Myers keep a column as the vertical differences :math:` D[ i ][ j ] - D[ i - 1 ][ j ] , +1 in Pv and -1 in Mv, 64 rows a word (a block), and :math: Eq = Peq[ T[ j - 1 ] ] , the places of P that hold the byte, moves a block to the next column with the horizontal difference :math: h_{in} ` at its top, in the formulation of Hyyro: :math:`[

begin{array}{l}

X_v = Eq vee M_v , quad Eq’ = Eq vee [ h_{in} < 0 ] , quad X_h = ( ( ( Eq’ wedge P_v ) + P_v ) oplus P_v ) vee Eq’ , \ P_h = M_v vee neg( X_h vee P_v ) , quad M_h = P_v wedge X_h , quad h_{out} = P_h[ 63 ] - M_h[ 63 ] , \ P_h leftarrow ( P_h ll 1 ) vee [ h_{in} > 0 ] , quad M_h leftarrow ( M_h ll 1 ) vee [ h_{in} < 0 ] , quad P_v leftarrow M_h vee neg( X_v vee P_h ) , quad M_v leftarrow P_h wedge X_v ,

end{array}

` a dozen operations on words with no branch, so that a column costs :math:` O( lceil m / 64 rceil ) ` of them.

  • levenshtein( a , b ) strips the common prefix and suffix, then puts the shorter string, of m bytes, in the column and scans the longer one, of n bytes: one word if :math:` m le 64 , O( n ). Otherwise, the diagonal transitions of Landau and Vishkin (the furthest reaching paths of Myers, as in the wavefront alignment of Marco-Sola et al.): :math: F_h( k ) `, the furthest row of the diagonal k = j - i reached by h edits, is :math:`[
    F_h( k ) = mathit{slide}_kbigl( max{ F_{h-1}( k ) + 1 ,

    F_{h-1}( k + 1 ) + 1 , F_{h-1}( k - 1 ) } bigr) ,

    ` :math:` mathit{slide}_k( i ) ` the row reached from i along the matches of the diagonal (compared 8 bytes at a time), and the distance is the least d with :math:` F_d( n - m ) = m , :math: O( n + d^2 ) ` expected time on random strings and O( d ) space. They are used for d up to :math:` n / 48 + 128 ` (if m > 128), where they cost about as much as the blocks, and give up once the rows r reached by h = 32, 64, 128, … edits suggest a distance :math:` h m / r ` above twice as much. Then the blocks, restricted to the diagonal band of Ukkonen of the cells that a path of cost at most k can cross, :math:` i - j in [ -k , k - ( n - m ) ] , and in it, as in edlib, to the blocks that may still lead to the end within k: a cell ( i , j ) costs at least :math: D[ i ][ j ] + | ( m - i ) - ( n - j ) | ` to the end, and a cell of a block at least the bottom of the block minus its distance from it, so that the first and the last block are dropped when the least of these bounds exceeds k; the block below the last one enters, all +1, when the bottom of the last is at most k + 1, since the cells at most k grow by at most one row per column. The cells outside the band are taken as larger, which overestimates only cells that no path of cost k crosses. k starts from the guess of the diagonals and a quarter more, and doubles until the distance is at most k, :math:` O( n d / 64 ) ` for distance d in the usual cases. Once the bands have computed a quarter of the :math:` n lceil m / 64 rceil ` blocks of the table, or span half of the column, all the blocks are computed instead, four columns at a time: the block b of the column j + q needs only the block b - 1 of the same column and the block b of the column before, so that the blocks i - q of the columns j

    • q, q < 4, are independent, the four lanes of an AVX2 vector (the bands of 8 blocks or more go the same way). levenshtein( a , b , k ) does the same with k fixed (the diagonals up to k, or the band of k) and gives k + 1 for any larger distance.

  • lcsLength( a , b ) is the bit-parallel LCS of Allison and Dix in the form of Crochemore, Iliopoulos, Pinzon and Reid: with :math:` V = 1^m ` at first and :math:` M = Peq[ b[ j ] ] `, :math:`[

    V leftarrow ( V + ( V wedge M ) ) vee ( V wedge neg M ) ,

    ` the addition carried between the blocks, and the length is the number of 0 among the m bits of V, :math:` O( n lceil m / 64 rceil ) ` after the common prefix and suffix are stripped.

  • approximateMatches( T , P , k ) gives the ends j (1 to n) of the substrings of T at edit distance at most k from P, :math:` D[ m ][ j ] le k ` with the top row 0, with their distances, by the search of Myers: only the blocks up to the last one with a cell at most k + 1 at its bottom are computed (the cut-off of Ukkonen), :math:` O( n k / 64 ) ` expected on random texts.

The bits Peq take :math:` 256 lceil m / 64 rceil ` words (in the object up to 4 blocks, with only the bytes of the two strings cleared beyond). The contracts [see File Contract.h]: the results equal those of the dynamic programming, editDistance(), lcs() and the last row of matchingTable() (audits, :math:` O( m n ) ` time). The functions are defined in EditDistance.tpp.

    1. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Doklady 10(8), 707-710, 1966

  1. Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM 46(3), 395-415, 1999, doi:10.1145/316542.316550

  2. Hyyro, A bit-vector algorithm for computing Levenshtein and Damerau edit distances, Nordic Journal of Computing 10(1), 29-39, 2003, https://cs.helsinki.fi/njc/Contents_of_Vol10.html

    1. Landau, U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms 10(2), 157-169, 1989, doi:10.1016/0196-6774(89)90010-2

    1. Myers, An O(ND) difference algorithm and its variations, Algorithmica 1(1-4), 251-266, 1986, doi:10.1007/BF01840446

  1. Marco-Sola, J. C. Moure, M. Moreto, A. Espinosa, Fast gap-affine pairwise alignment using the wavefront algorithm, Bioinformatics 37(4), 456-463, 2021, doi:10.1093/bioinformatics/btaa777

  1. Ukkonen, Algorithms for approximate string matching, Information and Control 64(1-3), 100-118, 1985, doi:10.1016/S0019-9958(85)80046-2

  1. Sosic, M. Sikic, Edlib: a C/C++ library for fast, exact sequence alignment using edit distance, Bioinformatics 33(9), 1394-1395, 2017, doi:10.1093/bioinformatics/btw753

  1. Allison, T. I. Dix, A bit-string longest-common-subsequence algorithm, Information Processing Letters 23(5), 305-310, 1986, doi:10.1016/0020-0190(86)90091-8

  2. Crochemore, C. S. Iliopoulos, Y. J. Pinzon, J. F. Reid, A fast and practical bit-vector algorithm for the longest common subsequence problem, Information Processing Letters 80(6), 279-285, 2001, doi:10.1016/S0020-0190(01)00182-X

  1. Ukkonen, Finding approximate patterns in strings, Journal of Algorithms 6(1), 132-137, 1985, doi:10.1016/0196-6774(85)90023-9

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/string/impl/EditDistance.tpp

  • cstddef

  • cstdint

  • string_view

  • utility

  • vector

Namespaces

Functions