Home arrow Development Cycles arrow Page 6 - How to Strike a Match
DEVELOPMENT CYCLES

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
TABLE OF CONTENTS:
  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
SEARCH DEVARTICLES

How to Strike a Match - Summary
(Page 6 of 6 )

In this article, I presented some requirements for a similarity ranking algorithm such that it would be applicable to many domains, in many languages. I described a metric and associated algorithm that meets those requirements by comparing the adjacent character pairs contained in two strings. I illustrated the algorithm with examples, and presented a Java implementation.

To close the article, I should like to return to some of the examples quoted at the start for which I argued the inadequacy of the existing algorithms. Contrary to the Soundex algorithm and the Edit Distance, my algorithm rates the strings ‘FRANCE’ and ‘REPUBLIC OF FRANCE’ to have a good similarity of 56%. On the other hand, the strings ‘FRANCE’ and ‘QUEBEC’ are seen to be reassuringly dissimilar, with a similarity of 0%. And ‘FRENCH REPUBLIC’ is more similar to ‘REPUBLIC OF FRANCE’ than it is to ‘REPUBLIC OF CUBA’ with similarities of 72% and 61%, respectively.


DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- 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 
Support 

Developer Shed Affiliates

 




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