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 Applications | PHP Web Applications | Web Aplications |
| Book Title | Rank | Value | Rank | Value | Rank | Value |
| Web Database Applications with PHP & MySQL | 1 | 82% | 1 | 68% | 1 | 59% |
| Creating Database Web Applications with PHP and ASP | 2 | 71% | 3 | 59% | 3 | 50% |
| Building Database Applications on the Web Using PHP3 | 3 | 70% | 4 | 58% | 4 | 49% |
| Building Web Database Applications with Visual Studio 6 | 4 | 67% | 5 | 47% | 5 | 46% |
| Web Application Development with PHP | 5 | 51% | 2 | 67% | 2 | 56% |
| WebRAD: Building Database Applications on the Web with Visual FoxPro and Web Connection | 6 | 49% | 6 | 34% | 6 | 32% |
| Structural Assesment: The Role of Large and Full Scale Testing | 7 | 12% | 8 | 7% | 8 | 7% |
| How to Find a Scholarship Online | 8 | 10% | 7 | 11% | 7 | 12% |
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.
Next: A Java Implementation >>
More Development Cycles Articles
More By Simon White
