Tame the Beast by Matching Similar Strings
(Page 1 of 7 )
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.
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.
Next: Equivalence Methods >>
More Development Cycles Articles
More By Simon White
/ 27 
