Home arrow Development Cycles arrow How to Strike a Match

How to Strike a Match

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.

Author Info:
By: Simon White
Rating: 5 stars5 stars5 stars5 stars5 stars / 39
April 07, 2004
  1. · How to Strike a Match
  2. · The New Metric
  3. · A Real World Example
  4. · A Java Implementation
  5. · Finishing the Java Implementation
  6. · Summary

print this article

How to Strike a Match
(Page 1 of 6 )

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’.

blog comments powered by Disqus

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials