The Algorithm Design Manual Second Edition

8.2

Approximate String Matching

Searching for patterns in text strings is a problem of unquestionable importance.

Section

3.7.2

(page

91

) presented algorithms for exact string matching—finding

where the pattern string P occurs as a substring of the text string T . Life is often

not that simple. Words in either the text or pattern can be mispelled (sic), robbing

us of exact similarity. Evolutionary changes in genomic sequences or language usage

imply that we often search with archaic patterns in mind: “Thou shalt not kill”

morphs over time into “You should not murder.”

How can we search for the substring closest to a given pattern to compensate

for spelling errors? To deal with inexact string matching, we must first define a cost

function telling us how far apart two strings are—i.e., a distance measure between

pairs of strings. A reasonable distance measure reflects the number of changes that

must be made to convert one string to another. There are three natural types of

changes:

• Substitution – Replace a single character from pattern P with a different

character in text T , such as changing “shot” to “spot.”

• Insertion – Insert a single character into pattern P to help it match text T ,

such as changing “ago” to “agog.”

• Deletion – Delete a single character from pattern P to help it match text T ,

such as changing “hour” to “our.”

long binomial_coefficient(n,k)

int n,k;

/* computer n choose k */

{

int i,j;

/* counters */

long bc[MAXN][MAXN];

/* table of binomial coefficients */

for (i=0; i<=n; i++) bc[i][0] = 1;

for (j=0; j<=n; j++) bc[j][j] = 1;

for (i=1; i<=n; i++)

for (j=1; j

bc[i][j] = bc[i-1][j-1] + bc[i-1][j];

return( bc[n][k] );

}

---

8 . 2

A P P R O X I M A T E S T R I N G M A T C H I N G

281

Properly posing the question of string similarity requires us to set the cost of

each of these string transform operations. Assigning each operation an equal cost

of 1 defines the edit distance between two strings. Approximate string matching

arises in many applications, as discussed in Section

18.4

(page

631

).

Approximate string matching seems like a difficult problem, because we must

decide exactly where to delete and insert (potentially) many characters in pattern

and text. But let us think about the problem in reverse. What information would

we like to have to make the final decision? What can happen to the last character

in the matching for each string?