File ApproximateMatching.h

↰ Parent directory (ADS/string)

The approximate string matching of section 13.1: an occurrence of the pattern P = p_0 … p_{m-1} in the text T = t_0 … t_{n-1} with k errors, a substitution, an insertion (a character of P not in T) or a deletion (a character of T not in P) each.

Definition (ADS/string/ApproximateMatching.h)

Detailed Description

DP[ i ][ j ], the least k of an occurrence of P( i ) ending at T( j ), is :math:`[
DP[ i ][ j ] = left{ begin{array}{ll}

0 & i = 0 \ i & j = 0 \ min{ DP[ i - 1 ][ j - 1 ] + delta , DP[ i - 1 ][ j ] + 1 ,

DP[ i ][ j - 1 ] + 1 } & mbox{otherwise}

end{array} right.

` with :math:` delta = 0 ` if p_{i-1} = t_{j-1} and 1 otherwise, Theta( m n ) time; the best occurrences end where the last row is smallest. occurrence() walks back from DP[ m ][ j ] to where the occurrence starts (exercise 13.1); stringMatchingSingleRow() keeps two rows only, O( n ) space (section 13.4). editDistance(), the distance of Levenshtein, has DP[ 0 ][ j ] = j, since T( j ) has j characters more than the empty P, and its result in DP[ m ][ n ].

The contracts [see File Contract.h]: occurrence() needs the table of P and T and a column of it; the best cost of stringMatching() is between 0 and m, the edit distance between | m - n | and max( m , n ). The operations are defined in ApproximateMatching.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 13.1 and 13.4, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

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

    1. Sellers, The theory and computation of evolutionary distances: pattern recognition, Journal of Algorithms 1(4), 359-373, 1980, doi:10.1016/0196-6774(80)90016-4

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Typedefs