Home arrow Development Cycles arrow Tame the Beast by Matching Similar Strings

Tame the Beast by Matching Similar Strings

My interest in string similarity stems from a desire for good user interface design. Computers are seen by many as unfriendly, unforgiving beasts that respond unkindly to requests that are almost meaningful. In this article, I demonstrate how computers can be programmed to be more forgiving of their users’ mistakes, with no additional burden on the user such as learning a special query format. Moreover, the techniques described are very widely applicable and often easy to implement.

Author Info:
By: Simon White
Rating: 5 stars5 stars5 stars5 stars5 stars / 39
February 09, 2004
  1. · Tame the Beast by Matching Similar Strings
  2. · Equivalence Methods
  3. · Synonyms and Regular Expressions
  4. · The Soundex Algorithm
  5. · Similarity Ranking Methods
  6. · Editing and Hamming Distances
  7. · Conclusions

print this article

Tame the Beast by Matching Similar Strings
(Page 1 of 7 )

Although my interest is in the user-interface, it is not the only place where such techniques can be employed. For example, the Hamming distance (described later) was traditionally used to recover from low-level bit transfer errors in electronic communications. In the future, I believe some of the techniques could be used to aid communication among independently acting computer programs (intelligent agents) as they try to make sense of what another agent ‘said’. But for now, I would like you to think of realigning an ‘unexpected’ input string with an input that is expected, or known to be valid, in the context of a user-interface.

Let me be a little more concrete. When you enter a search string to look for a book at Amazon.com, your input is matched against the descriptions of known products held in a database. It is quite likely that your input does not exactly match any of the ‘expected’ inputs (that is, book titles or authors) in the database. For example, if you enter the string ‘Web Database Applications’, you would like the search to return the book with the title ‘Web Database Applications with PHP and MySQL’, even though it is not an exact match. And you might also expect to see the same book listed if you entered ‘PHP Web Applications’, or even the misspelling ‘Web Aplications’. The task is therefore to find which of the expected strings (in this case product descriptions) are similar, or perhaps most similar, to the user’s input.

There are two main classes of algorithms for matching string similarity, equivalence methods and similarity ranking methods.

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