Home arrow Development Cycles arrow Page 3 - 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 - A Real World Example
(Page 3 of 6 )

Now for an example that is a little closer to the real world. Suppose we are building a web site that sells books, and we want to allow our users to type in a string to search against the titles of books in our database. When the user’s string does not exactly match any of the books in our database, we return a list of the books whose title is most similar.

Table 2 contains a list of book titles in its first column. If we search against these book titles with the query strings ‘Web Database Applications’, ‘PHP Web Applications’ and ‘Web Aplications’ using the metric described, then we get the results shown in the six right-most columns of the table.  (Note the intentional misspelling of ‘Applications’ in the third of these strings.) The ‘Rank’ columns indicate the order in which the books would be returned. Each rank is qualified by its corresponding percentage similarity value (rounded to the nearest whole number) in the next column. The three input strings were carefully chosen to target the book ‘Web Database Applications with PHP & MySQL’, but with a decreasing quality of input string as you move from ‘Web Database Applications’ to ‘Web Aplications’

Web Database ApplicationsPHP Web ApplicationsWeb Aplications
Book TitleRankValueRankValueRankValue
Web Database Applications with PHP & MySQL182%168%159%
Creating Database Web Applications with PHP and ASP271%359%350%
Building Database Applications on the Web Using PHP3370%458%449%
Building Web Database Applications with Visual Studio 6467%547%546%
Web Application Development with PHP551%267%256%
WebRAD: Building Database Applications on the Web with Visual FoxPro and Web Connection649%634%632%
Structural Assesment: The Role of Large and Full Scale Testing712%87%87%
How to Find a Scholarship Online810%711%712%

 Table 2: Three Searches for a Book

Two main results are shown in the table. Firstly, the targeted book is scored as the top match in each case, and secondly, the similarity values decrease as you move left to right in the table, reflecting the intended degradation in the quality of the input.

When presenting results of searches to users, you would normally set a threshold value of say, 20%, and only show the top 10 or so results that lie above the threshold. (We wouldn’t want to lose the trust of our users by showing results that are irrelevant.)

It is worth pointing out that I devised this example by searching the books at Amazon.com with exactly the same three input strings as shown above, and selecting the top matches. Interestingly, for the third query ‘Web Aplications’, Amazon does not show any web application development books in its search results. In fact, Amazon’s top match is ‘How to Find a Scholarship Online’, a result which appears to confuse writing web applications with writing applications on the web! This suggests that Amazon’s search mechanism is not robust to spelling errors, but nevertheless uses a similarity metric based on product descriptions in an attempt to return a good match.

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-2019 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials