How to Strike a Match
(Page 1 of 6 )
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.
The algorithm has been successfully applied to the retrieval of terms from a domain-specific electronic thesaurus, and also to the retrieval of geographical place names.
The algorithm was driven by the following requirements:
- A true reflection of lexical similarity — strings with small differences should be recognised as being similar. In particular, a significant substring overlap should point to a high level of similarity between the strings.
- A robustness to changes of word order — two strings which contain the same words, but in a different order, should be recognised as being similar. On the other hand, if one string is just a random anagram of the characters contained in the other, then it should (usually) be recognised as dissimilar.
- Language Independence — the algorithm should work not only in English, but in many different languages.
For example, ‘FRANCE’ should be similar to ‘FRANÇAIS’ and ‘REPUBLIC OF FRANCE’, and ‘REPUBLIC OF FRANCE’ should be similar to both ‘FRENCH REPUBLIC’ and ‘REPUBLIQUE FRANCAISE’. We can also make relative statements of similarity. For example ‘FRENCH’ should be more similar to ‘FRENCH FOOD’ than it is to ‘FRENCH CUISINE’, because the size of the common substring is the same in both cases and ‘FRENCH FOOD’ is the shorter of the two strings.
Existing Algorhitms
Existing algorithms, such as the Soundex Algorithm, Edit Distance, and Longest Common Substring, do not perform well against these requirements. (See my previous article for descriptions of the algorithms.)
- The Soundex Algorithm is an equivalence algorithm, so simply states whether or not two strings are similar. However, it would not recognise any similarity between ‘FRANCE’ and ‘REPUBLIC OF FRANCE’, as they start with different letters.
- The Edit Distance algorithm would acknowledge some similarity between the two strings, but would rate ‘FRANCE’ and ‘QUEBEC’ (with a distance of 6) to be more similar than ‘FRANCE’ and ‘REPUBLIC OF FRANCE’ (which have a distance of 12).
- The Longest Common Substring would give ‘FRANCE’ and ‘REPUBLIC OF FRANCE’ quite a good rating of similarity (a common substring of length 6). However, it is disappointing that according to this metric, the string ‘FRENCH REPUBLIC’ is equally similar to the two strings ‘REPUBLIC OF FRANCE’ and ‘REPUBLIC OF CUBA’.
Next: The New Metric >>
More Development Cycles Articles
More By Simon White
