Searching a single MySQL text column with fuzzy matching

Question

I have a MySQL InnoDB table with a 'name' column (VARCHAR(255)) which I want users to be able to search against, returning all the matching rows. However, I can't just use a LIKE query because the search needs to allow for users typing in names which are similar to the available names (e.g. prefixing with 'The', or not knowing that the correct name includes an apostrophe).

Two examples are:

Name in DB: 'Rose and Crown'

Example possible searches which should match: 'Rose & Crown', 'Rose and Crown', 'rose and crown', 'The Rose and Crown'

Name in DB: 'Diver's Inn'

Example possible searches which should match: 'Divers' Inn', 'The Diver's Inn', 'Divers Inn'

I also want to be able to rank the results by a 'closest match' relevance, although I'm not sure how that would be done (edit distance perhaps?).

It's unlikely that the table will ever grow beyond a few thousand rows, so a method which doesn't scale to millions of rows is fine. Once entered, the name value for a given row will not change, so if an expensive indexing operation is required that's not a problem.

Is there an existing tool which will perform this task? I've looked at Zend_Search_Lucence but that seems to focus on documents, whereas I'm only interesting in searching a single column.

Edit: On SOUNDEX searching, this doesn't produce the results I want. For example:

SELECT soundex( 'the rose & crown' ) AS soundex1, soundex( 'rose and crown' ) AS soundex2;
soundex1    soundex2
T6265   R253265

Solution: In the end I've used Zend_Search_Lucence and just pretended that every name is in fact a document, which seems to achieve the result I want. I guess it's full text search in a way, even though each string is at most 3-4 words.

Answer 1

Full Text Search (FTS) is the terminology for the database functionality you desire. There's:

• Native MySQL support (requires that the table be MyISAM)

  WHERE MATCH(column) 
          AGAINST('Rose', 'Crown') 
  

• Sphinx (3rd party)

• Lucene/SOLR (3rd party)