Download Pro Full-Text Search in SQL Server 2008

CHAPTER 11 ■ ADVANCED SEARCH TECHNIQUES
Figure 11-8. LCS and score for the words Joel and Joseph
LCS is useful for calculating a similarity metric between two strings; however, it’s a rather
inefficient algorithm of complexity O(mn), where m and n are the lengths of the two input
strings. This algorithm literally builds a matrix with dimensions [m, n], and populates the
matrix as it calculates the similarity between the two strings. Because of this complexity, we
recommend using another method to narrow down your result set before applying a string
similarity algorithm such as LCS to further narrow down your results.
Edit Distance
Another algorithm, closely related to LCS, is edit distance. As we mentioned previously in this
chapter, edit distance is a generalized form of Hamming distance. Like Hamming distance and
LCS, edit distance is a measure of the similarity (or difference) between two strings.
We’ve implemented an edit distance algorithm known as the Damerau-Levenshtein Edit
Distance as a SQL CLR function. This algorithm acts on two input strings in a manner similar
to LCS, by building a matrix. Unlike LCS, Damerau-Levenshtein counts the number of operations required to convert one input string into another. The algorithm accounts for four types
of operations:
• Insertions: An insertion is a single character that must be inserted into one string to turn
it into the other string. For instance, the word you needs to have the letter r inserted to
turn it into the word your.
• Deletions: A deletion is a single character that must be deleted from one string to turn it
into the other string. As an example, the word places needs to have the letter s deleted to
turn it into the word place.
• Replacements: A replacement is a single character that must be replaced in one string to
turn it into the other string. The letter u must be replaced with a in the word mush to turn
it into the word mash, for instance.
• Transpositions: A transposition is a side-by-side swap of two characters in one string to
turn it into the other string. Consider the word cast, which requires a transposition of the
letters s and t to turn it into the word cats.
The Damerau-Levenshtein Edit Distance algorithm is implemented as the function
dbo.DamLev. You can call this function with two strings to calculate the edit distance between
them. Listing 11-6 calculates the edit distance between the words lastly and listen. The results
are shown in Figure 11-9.
www.it-ebooks.info
249