Edit Distance

The edit distance measure, also known as Levenshtein distance, d (x,y ), computes the minimal cost of transforming string x to string y. Transforming a string is carried out using a sequence of the following operators: delete a character, insert a character, and substitute one character for another. For example, the cost of transforming the string x = David Smiths to the string y = Davidd Simth is 4. The required operations are: inserting a d (after David), substituting m by i, substituting i by m, and deleting the last character of x, which is s.

It is not hard to see that the minimal cost of transforming x to y is the same as the minimal cost of transforming y to x (using in effect the same transformation). Thus, d (x,y ) is well-defined and symmetric with respect to both x and y.

Intuitively, edit distance tries to capture the various ways people make editing mistakes, such as inserting an extra character (e.g., Davidd instead of David) or swapping two characters (e.g., Simth instead of Smith). Hence, the smaller the edit distance, the more similar the two strings are.

The edit distance function d (x,y ) is converted into a similarity function s (x,y ) as follows:

For example, the similarity score between David Smiths and Davidd Smith is

The value of d (x,y ) can be computed using dynamic programming. Let and , where the x_i and y_j are characters. Let d (i,j ) denote the edit distance between and (which are the i th and j th prefixes of x and y ).

The key to designing a dynamic-programming algorithm is to establish a recurrence equation that enables computing d (i,j ) from previously computed values of d. Figure 4.2(a) shows the recurrence equation in our case. To understand the equation, observe that we can transform string into string in one of four ways: (a) transforming into , then copying x_i into y_j if , (b) transforming into , then substituting x_i with y_j if , (c) deleting x_i, then transforming into , and (d) transforming into , then inserting y_j. The value d (i,j ) is the minimum of the costs of the above transformations. Figure 4.2(b) simplifies the equation in Figure 4.2(a) by merging the first two lines.

Figure 4.2 (a) The recurrence equation for computing edit distance between strings x and y using dynamic programming and (b) a simplified form of the equation.

Figure 4.3 shows an example computation using the simplified equation. The figure illustrates computing the distance between the strings x = dva and y = dave. We start with the matrix in Figure 4.3(a), where the x_i are listed on the left and the y_j at the top. Note that we have added x₀ and y₀, two null characters at the start of x and y, to simplify the implementation. Specifically, this allows us to quickly fill in the first row and column, by setting d (i, 0) = i and .

Figure 4.3 Computing the edit distance between dva and dave using the dynamic programming equation in Figure 4.2(b). (a) The dynamic programming matrix after filling in several cells, (b) the filled-in matrix, and (c) the sequence of edit operations that transforms dva into dave, found by following the bold arrows in part (b).

Now we can use the equation in Figure 4.2(b) to fill in the rest of the matrix. For example, we have . Since this value is obtained by adding 0 to , we add an arrow pointing from cell (1,1) to cell (0,0). Similarly, d (1,2) = 1 (see Figure 4.3(a)). Figure 4.3(b) shows the entire filled-in matrix. The edit distance between x and y can then be found to be 2, in (3,4), the bottom rightmost cell.

In addition to computing the edit distance, the algorithm also shows the sequence of edit operations, by following the arrows. In our example, since the arrow goes “diagonal,” from (3,4) to (2,3), we know that x₃(character a ) has been copied into or substituted with y₄(character e). The arrow then goes “diagonal” again, from (2,3) to (1,2). So again x₂ (character v) has been copied into or substituted with y₃(character v). Next, the arrow goes “horizontal,” from (1,2) to (1,1). This means a gap - has been inserted into x and aligned with a in y (which denotes an insertion operation). This process stops when we have reached cell (0,0). The transformation is depicted in Figure 4.3(c).

The cost of computing the edit distance is . In practice, the lengths of x and y often are roughly the same, and hence we often refer to the above cost as quadratic.

The Needleman-Wunch Measure

The Needleman-Wunch measure generalizes the Levenshtein distance. Specifically, it is computed by assigning a score to each alignment between the two input strings and choosing the score of the best alignment, that is, the maximal score. An alignment between two strings x and y is a set of correspondences between the characters of x and y, allowing for gaps. For example, Figure 4.4(a) shows an alignment between the strings x = dva and y = deeve, where d corresponds to d, v to v, and a to e. Note that a gap of length 2 has been inserted into x, and so the two characters ee of y do not have any corresponding characters in x.

Figure 4.4 An example for the Needleman-Wunch function: (a) an alignment between two strings x = dva and y = deeve, with a gap in x, and (b) a score matrix that assigns to each pair of characters a score and a gap penalty c_g.

The score of an alignment is computed using a score matrix and a gap penalty. The matrix assigns a score for a correspondence between every pair of characters and therefore allows for penalizing transformations on a case-by-case basis. Figure 4.4(b) shows a sample score matrix where a correspondence between two identical characters scores 2, and -1 otherwise. A gap of length 1 has a penalty c_g (set to 1 in Figure 4.4). A gap of length k has a linear penalty of kc_g.

The score of an alignment is then the sum of the scores of all correspondences in the alignment, minus the penalties for the gaps. For example, the score of the alignment in Figure 4.4(a) is 2 (for correspondence d-d) + 2 (for v-v) − 1 (for a-e) − 2 (penalty for the gap of length 2) = 1. This is the best alignment between x and y (that is, the one with the highest score) and therefore is the Needleman-Wunch score between the two.

As described, the Needleman-Wunch measure generalizes the Levenshtein distance in three ways. First, it computes similarity scores instead of distance values. Second, it generalizes edit costs into a score matrix, thus allowing for more fine-grained score modeling. For example, the letter o and the number 0 are often confused in practice (e.g., by OCR systems). Hence, a correspondence between these two should have a higher score than one between a and 0, say. As another example, when matching bioinformatic sequences, different pairs of amino acids may have different semantic distances. Finally, the Needleman-Wunch measure generalizes insertion and deletion into gaps and generalizes the cost of such operations from 1 to an arbitrary penalty c_g.

The Needleman-Wunch score s (x,y ) is computed with dynamic programming, using the recurrence equation shown in Figure 4.5(a). We note three differences between the algorithm used here and the one used for computing the edit distance (Figure 4.2(b)). First, here we compute the max instead of min. Second, we use the score matrix in the recurrence equation instead of the unit costs of edit operations. Third, we use the gap cost c_g instead of the unit gap cost. Note that when initializing this matrix, we must set and (instead of i and j as in the edit distance case).

Figure 4.5 An example for the Needleman-Wunch function: (a) the recurrence equation for computing the similarity score using dynamic programming, (b) the dynamic-programming matrix between dva and deeve using the equation in part (a), and (c) the optimal alignment between the above two strings, found by following the arrows in part (b).

Figure 4.5(b) shows the fully filled-in matrix for x = dva and y = deeve, using the score matrix and gap penalty in Figure 4.4(b). Figure 4.5(c) shows the best alignment, found by following the arrows in the matrix of Figure 4.5(b).

The Affine Gap Measure

The affine gap measure is an extension of the Needleman-Wunch measure that handles longer gaps more gracefully. Consider matching x = David Smith with y = David R. Smith. The Needleman-Wunch measure can do this match very well, by opening a gap of length 2 in x, right after David, then aligning the gap with R. However, consider matching the same x = David Smith with y′ = David Richardson Smith, as shown in Figure 4.6(a). Here the gap between the two strings is 10 characters long. Needleman-Wunch does not match very well because the cost of the gap is too high. For example, assume that each character correspondence has a score of 2 and that c_g is 1; then the score of the above alignment under Needleman-Wunch is 6 ⋅ 2 - 10 = 2.

Figure 4.6 (a) An example of two strings where there is a long gap, (b) the recurrence equations for the affine gap measure.

In practice, gaps tend to be longer than one character. Hence, assigning a uniform penalty to each character in the gap in a sense will unfairly punish long gaps. The affine gap measure addresses this problem by distinguishing between the cost of opening a gap and the cost of continuing the gap. Formally, the measure assigns to each gap of length k a cost , where c_o is the cost of opening the gap (i.e., the cost of the very first character of the gap), and c_r is the cost of continuing the gap (i.e., the cost of the remaining characters of the gap). Cost c_r is less than c_o, thereby lessening the penalty of a long gap. Continuing with the example in Figure 4.6(a), if and , the score of the alignment is 6 ⋅ 2 - 1 - 9 ⋅ 0.5 = 6.5, much higher than the score 2 obtained under Needleman-Wunch.

Figure 4.6(b) shows the recurrence equations for the affine gap measure. Deriving these equations is rather involved. Since we now penalize opening a gap and continuing a gap differently, in every stage, for each cell (i,j ) of the dynamic-programming matrix we keep track of three values:

The best score for the cell, s (i,j ), is then the maximum of these three scores.

In deriving the above recurrence equations, we make the following assumption about the cost function. We assume that in an optimal alignment, we will never have an insertion followed directly by a deletion, or vice versa. This means we will never have the situation depicted in Figure 4.7(a) or Figure 4.7(b). We can guarantee this property by setting the cost to be lower than the lowest mismatch score in the score matrix. Under such conditions, the alignment in Figure 4.7(c) will have a higher score than those to its left.

Figure 4.7 By setting the gap penalties and the score matrix appropriately, the alignment in (c) will always score higher than those in (a) and (b).

We now explain how to derive the equations for M (i,j ), , and in Figure 4.6(b). Figure 4.8 explains how to derive the equation for M (i,j). This equation considers the case where x_i is aligned with y_j(Figure 4.8(a)). Thus, is aligned with . This can only happen in one of three ways, as shown in Figures 4.8(b)–(d): is aligned with , is aligned into a gap, or is aligned into a gap. These three ways give rise to the three cases in the equation for M (i,j ) in Figure 4.6(b).

Figure 4.8 The derivation of the equation for M(i, j) in Figure 4.6(b).

Figure 4.9 shows how to derive the equation for in Figure 4.6(b). This equation considers the case where x_i is aligned into a gap (Figure 4.9(a)). This can only happen in one of three ways, as shown in Figure 4.9(b)–(d): is aligned with y_j, is aligned into a gap, or y_j is aligned into a gap. The first two ways give rise to the two cases shown in Figure 4.6(b). The third case cannot happen, because it means an insertion followed directly by a deletion. This violates the assumption we described earlier. The equation for in Figure 4.6(b) is derived in a similar fashion. The complexity of computing the affine gap measure remains .

Figure 4.9 The derivation of the equation for I_x(i, j) in Figure 4.6(b).

The Smith-Waterman Measure

The previous measures consider global alignments between the input strings. That is, they attempt to match all characters of x with all characters of y.

Global alignments may not be well suited for some cases. For example, consider the two strings Prof. John R. Smith, Univ of Wisconsin and John R. Smith, Professor. The similarity score based on global alignments will be relatively low. In such a case, what we really want is to find two substrings of x and y that are most similar, and then return the score between the substrings as the score for x and y. For example, here we would want to identify John R. Smith to be the most similar substrings of the above two strings. This means matching the above two strings by ignoring certain prefixes (e.g., Prof.) and suffixes (e.g., Univ of Wisconsin in x and Professor in y ). We call this local alignment.

The Smith-Waterman measure is designed to find matching substrings by introducing two key changes to the Needleman-Wunch measure. First, the measure allows the match to restart at any position in the strings (no longer limited to just the first position). The restart is captured by the first line of the recurrence equation in Figure 4.10(a). Intuitively, if the global match dips below zero, then this line has the effect of ignoring the prefixand restarting the match. Similarly, note that all values in the first row and column of the dynamic-programming matrix are zeros, instead of and as in the Needleman-Wunsch case. Applying this recurrence equation to the strings avd and dave produces the matrix in Figure 4.10(b).

Figure 4.10 An example for the Smith-Waterman measure: (a) the recurrence equation for computing the similarity score using dynamic programming and (b) the dynamic-programming matrix between avd and dave using the equation in part (a).

The second key change is that after computing the matrix using the recurrence equation, the algorithm starts retracing the arrows from the largest value in the matrix (4 in our example) rather than starting from the lower-right corner (3 in the matrix). This change effectively ignores suffixes if the match they produce is not optimal. Retracing ends when we meet a cell with value 0, which corresponds to the start of the alignment. In our example we can read out the best local alignment between avd and dave, which is av.

The Jaro Measure

The Jaro measure was developed mainly to compare short strings, such as first and last names. Given two strings x and y, we compute their Jaro score as follows.

As an example, consider x = jon and y = john. We have c = 3. The common character sequence in x is jon, and so is the sequence in y. Hence, there is no transposition, and t = 0. Thus, . In contrast, the similarity score according to edit distance would be 0.75.

Now suppose x = jon and y = ojhn. Here the common character sequence in x is jon and the common character sequence in y is ojn. Thus t = 2, and .

The cost of computing the Jaro distance is , due to the cost of finding common characters.

The Jaro-Winkler Measure

The Jaro-Winkler measure is designed to capture cases where two strings have a low Jaro score, but share a prefix and thus are still likely to match. Specifically, the measure introduces two parameters: PL, which is the length of the longest common prefix between the two strengths, and PW, which is the weight to give the prefix. The measure is computed using the following formula:

The Overlap Measure

Let B_x and B_y be the sets of tokens generated for strings x and y, respectively. The overlap measure returns the number of common tokens .

Consider x = dave and y = dav; then the set of all 2-grams of x is B_x = {#d, da, av, ve, e#} and the set of all 2-grams of y is B_y = {#d, da, av, v#}. So O (x,y ) = 3.

The Jaccard Measure

Continuing with the above notation, the Jaccard similarity score between two strings x and y is .

Again, consider x = dave with B_x = {#d, da, av, ve, e#}, and y = dav with B_y = {#d, da, av, v#}. Then J (x,y ) = 3/6.

The TF/IDF Measure

This measure employs the notion of TF/IDF score commonly used in information retrieval (IR) to find documents that are relevant to keyword queries. The intuition underlying the TF/IDF measure is that two strings are similar if they share distinguishing terms. For example, consider the three strings x = Apple Corporation, CA, y = IBM Corporation, CA, and z = Apple Corp. The edit distance and Jaccard measure would match x with y as s (x,y ) is higher than s (x,z ). However, the TF/IDF measure is able to recognize that Apple is a distinguishing term, whereas Corporation and CA are far more common, and thus would correctly match x with z.

When discussing the TF/IDF measure, we assume that the pair of strings being matched is taken from a collection of strings. Figure 4.11(a) shows a tiny such collection of three strings, x = aab, y = ac, and z = a. We convert each string into a bag of terms. Using IR terminology, we refer to such a bag of terms as a document. For example, we convert string x = aab into document B_x= {a, a, b}.

Figure 4.11 In the TF/IDF measure (a) strings are converted into bags of terms, (b) TF and IDF scores of the terms are computed, then (c) these scores are used to compute feature vectors.

We now compute term frequency (TF) scores and inverse document frequency (IDF) scores as follows:

Figure 4.11(b) shows the TF/IDF scores for the tiny example in Figure 4.11(a).

Next, we convert each document d into a feature vector v_d. The intuition is that two documents will be similar if their corresponding vectors are close to each other. The vector of d has a feature for each term t, and the value of is a function of the TF and IDF scores. Vector v_d thus has as many features as the number of terms in the collection. Figure 4.11(c) shows the three vectors , and v_z for the three documents , and B_z, respectively. In the figure, we use a relatively simple score: . Thus, the score for feature a of v_x is , and so on.

Now we are ready to compute the TF/IDF similarity score between any two strings p and q. Let T be the set of all terms in the collection. Then conceptually the vectors v_p and v_q(of the strings p and q ) can be viewed as vectors in the -dimensional space where each dimension corresponds to a term. The TF/IDF score between p and q can be computed as the cosine of the angle between these two vectors:

(4.1)

For example, the TF/IDF score between the two strings x and y in Figure 4.11(a) is , using the vectors v_x and v_y in Figure 4.11(c).

It is not difficult to see from Equation 4.1 that the TF/IDF similarity score between two strings p and q is high if they share many frequent terms (that is, terms with high TF scores), unless these terms also commonly appear in other strings in the collection (in which case the terms have low IDF scores). Using the IDF component, the TF/IDF similarity score can effectively discount the importance of such common terms.

In the above example, we assumed . This means that if we “double” the number of occurrences of t in document d, then will also double. In practice this is found to be excessive: doubling the number of occurrences of t should increase but not double it. One way of addressing this is to “dampen” the TF and IDF components by a logarithmic factor. Specifically, we can take

(In fact, log(idf(t)) itself is also commonly referred to as the inverse document frequency.) In addition, the vector v_d is often normalized to length 1, by setting

This way, computing the TF/IDF similarity score s (p,q ) as in Equation 4.1 reduces to computing the dot product between the two normalized vectors v_p and v_q.

The Generalized Jaccard Measure

Recall that the Jaccard measure considers the number of overlapping tokens in the input strings x and y. However, a token from x and a token from y have to be identical in order to be considered in the overlap set, which may be restrictive in some cases.

For example, consider matching the names of the nodes of two taxonomies describing divisions of companies. Each node is described by a string, such as Energy and Transportation and Transportation, Energy, and Gas. The Jaccard measure is a promising candidate for matching such strings because intuitively two nodes are similar if their names share many tokens (e.g., energy and transportation). However, in practice tokens are often misspelled, such as energy vs. eneryg. The generalized Jaccard measure will enable matching in such cases.

As with the Jaccard measure, we begin by converting the string x into a set of tokens and string y into a set of tokens . Figure 4.12(a) shows two such strings x and y, with and .

Figure 4.12 An example of computing the generalized Jaccard measure.

The next three steps will determine the set of pairs of tokens that are considered in the “softened” overlap set. First, let s be a similarity measure that returns values in the range [0,1]. We apply s to compute a similarity score for each pair . Continuing with the above example, Figure 4.12(a) shows all six such scores.

Second, we keep only those scores that equal or exceed a given threshold α. Figure 4.12(b) shows the remaining scores in our example, given . The sets B_x and B_y, together with the edges that denote the remaining scores, form a bipartite graph G. In the third step we find the maximum-weight matching M in the bipartite graph G. Figure 4.12(c) shows this matching in our example. The total weight of this matching is 0.7 + 0.9 = 1.6.

Finally, we return the normalized weight of M as the generalized Jaccard score between x and y. To normalize, we divide the weight by the sum of the number of edges in M and the number of “unmatched” elements in B_x and B_y. This sum is . Formally,

Continuing with the above example, the generalized Jaccard score is .

The measure GJ (x,y ) is guaranteed to be between 0 and 1. It is a natural generalization of the Jaccard measure J (x,y ): if we constrain the elements of B_x and B_y to match only if they are identical, GJ (x,y ) reduces to J (x,y ). We discuss how to compute GJ (x,y ) efficiently later in Section 4.3.

The Soft TF/IDF Similarity Measure

This measure is similar in spirit to the generalized Jaccard measure, except that it uses the TF/IDF measure instead of the Jaccard measure as the “higher-level” similarity measure.

Consider an example with three strings x = Apple Corporation, CA, y = IBM Corporation, CA, and z = Aple Corp. To match these strings, we would like to use the TF/IDF measure so that we can discount common terms such as Corporation and CA. Unfortunately, in this case the TF/IDF measure does not help us match x with z, because the term Apple in x does not match the misspelled term Aple in z. Thus, x and z do not share any term. As with the generalized Jaccard measure, we would like to “soften” the requirement that Apple and Aple match exactly, and instead require that they be similar to each other.

We compute the soft TF/IDF measure as follows. As with the TF/IDF measure, given two strings x and y, we create the two documents B_x and B_y. Figure 4.13(b) shows the documents created for the strings in Figure 4.13(a).

Figure 4.13 An example of computing soft TF/IDF similarity score for two strings x and y.

Next, we compute close (x,y,k) to be the set of all terms in B_x that have at least one close term in B_y. Specifically, close (x,y,k ) is the set of terms such that there exists a term that satisfies , where s′ is a basic similarity measure (e.g., Jaro-Winkler) and k is a prespecified threshold. Continuing with our example in Figure 4.13(b), suppose , as shown in the figure. Then . Note that is excluded because the closest term to d in B_y is d′, but d′ is still too far from d (at a similarity score of 0.6).

In the final step, we compute s (x,y ) as in the traditional TF/IDF score, but giving a weight to each component of the TF/IDF formula according to the similarity score produced by s′. Specifically, let v_x and v_y be the feature vectors for x and y, as explained when we discussed the TF/IDF similarity measure. The vectors v_x and v_y are normalized to length 1, so that the traditional TF/IDF score can be computed as the dot product of the two vectors. Then we have

where is the term that maximizes for all . Figure 4.13(c) shows how to compute s (x,y ) given the examples in Figures 4.13(a-b).

The Monge-Elkan Similarity Measure

The Monge-Elkan similarity measure can be effective for domains in which more control is needed over the similarity measure. To apply this measure to two strings x and y, first we break them into multiple substrings, say and , where the A_i and B_j are substrings. Next, we compute

where s′ is a secondary similarity measure, such as Jaro-Winkler. To illustrate the above formula, suppose and . Then

Note that we ignore the order of the matching of the substrings and only consider the best match for the substrings of x in y. Furthermore, we can customize the secondary similarity measure s′ to a particular application.

For example, consider matching strings x = Comput. Sci. and Eng. Dept., University of California, San Diego and y = Department of Computer Science, Univ. Calif., San Diego. To employ the Monge-Elkan measure, first we break x and y into substrings such as Comput., Sci., and Computer. Next we must design a secondary similarity measure s′ that works well for such substrings. In particular, it is clear that s′ must handle matching abbreviations well. For example, s′ may decide that if a substring A_i is a prefix of a substring B_j, such as Comput. and Computer, then they match, that is, their similarity score is 1.

Selecting the Subset Intelligently

So far we arbitrarily selected a subset x′ of x and checked its overlap with the entire set y. We can do even better by selecting a particular subset x′ of x and checking its overlap with only a particular subset y′ of y. Specifically, suppose we have imposed an ordering over the universe of all possible terms. For example, we can order terms in increasing frequency, as computed over the union of sets X and Y of Figure 4.15(b). Figure 4.16(a) shows all terms found in in this order.

Figure 4.16 We can build an inverted index over only the prefixes of strings in Y, then use this index to perform string matching.

We reorder the terms in each set and according to the order . Figure 4.16(b) shows the reordered sets X and Y. Given a reordered set x, we refer to the subset x′ that contains the first n terms of x as the prefix of size n (or the n th prefix) of x. For example, the 2nd prefix of x₃= {dane, mendota, monona, lake} is {dane, mendota}. Given the above, we can establish the following property:

Given the above property, we can revise procedure FindCands as follows. Suppose again that we consider overlap of at least k (that is, ).

Figure 4.17 The inverted indexes over (a) the prefixes of size of all y ε Y and (b) all y ε Y. The former is often significantly smaller than the latter in practice.

Consider for example x = {mendota, lake}, and therefore x′= {mendota}. Using mendota to look up the inverted index in Figure 4.17(a) yields y₆. Thus, FindCands returns y₆ as the sole candidate that may match x. Note that if we check the overlap between x′ and the entire y, then y₇ is also returned. Thus, checking the overlap between prefixes can reduce the size of the resulting set. In practice, this reduction can be quite significant.

It is also important to note that the size of the inverted index is much smaller. For comparison purposes, Figure 4.17(b) shows the inverted index for the entire sets (reproduced from Figure 4.15(c)). The index we create here does not contain an entry for the term lake, and its index list for mendota is also smaller than the same index list in the entire-sets index.

Applying Prefix Filtering to the Jaccard Measure

The following equation enables us to extend the prefix filtering method to the Jaccard measure.

(4.4)

The equation shows how to convert the Jaccard measure to the overlap measure, except for one detail. The threshold α as defined above is not a constant and depends on and . Thus, we cannot build the inverted index over the prefixes of using α. To address this, we index the “longest” prefixes. In particular, it can be shown that we only have to index the prefixes of length of the to ensure that we do not miss any correct matching pairs.