In a previous article, Tame the Beast by Matching Similar Strings, I presented a brief survey of approximate string matching algorithms, and argued their importance for information retrieval tasks. A classic example of information retrieval using similarity searching is entering a keyword into the search string box on Amazon’s web site in order to retrieve descriptions of products related to that keyword. Approximate string matching algorithms can be classified as equivalence algorithms and similarity ranking algorithms. In this article, I present a new similarity ranking algorithm, together with its associated string similarity metric. I also include Java source code, so you can easily incorporate the algorithm into your own applications.
How to Strike a Match - A Java Implementation (Page 4 of 6 )
In this section, I describe an implementation of the similarity algorithm in Java. The code is not difficult to understand, so if Java is not your main programming language, it should not be a big task to translate it to your favourite language.
Overview
I have implemented the algorithm as a single class with three static methods. Two of those methods are private, so only one, compareStrings(), is exposed to users of the class. Here is the outline of the class, with the bodies of the methods removed:
import java
.util.ArrayList; public class LetterPairSimilarity { public static double compareStrings(String str1, String str2) {} private static ArrayList wordLetterPairs(String str) {} private static String[] letterPairs(String str) {} }
Until now, I have not discussed how I deal with white space in the input strings. My approach is to dismiss from consideration any character pairs that include white space. In effect, this means first finding the words (or tokens) in your input strings before looking for adjacent character pairs. You can now see how this approach maps to the methods outlined above. CompareStrings() calls wordLetterPairs() for each of its inputs. WordLetterPairs() identifies the words in its input string, and uses the method letterPairs() to compute the pairs of adjacent characters in each of those words. When compareStrings() has collected the character pairs for each of its input strings, it computes the return value according to the similarity metric. I will now discuss the bodies of the methods in detail, in a bottom-up order.
Computing Letter Pairs
The basis of the algorithm is the method that computes the pairs of characters contained in the input string. This method creates an array of Strings to contain its result. It then iterates through the input string, to extract character pairs and store them in the array. Finally, the array is returned.
/** @return an array of adjacent letter pairs contained in the input string */ private static String[] letterPairs(String str) { int numPairs = str.length()-1; String[] pairs = new String[numPairs]; for (int i=0; i<numPairs; i++) { pairs[i] = str.substring(i,i+2); } return pairs; }
Development Cycles 
