Did you mean… ? In php

In a new website I am developing for a client I had to add the usual "Did you mean... ?" in the search results for her. Si I started thinking for the easiest way to do this.

There are actually a lot of php functions out there to look for similar text. The most obvious one?
similar_text()
You must pass 2 parameters plus an optional third. The two first are the strings to compare, and the optional one is the percentage of "closeness" you want them to have. It is quite useful, although it is too expensive in terms of time to use with huge database searches, so I wouldn't recommend it.

There are two other methods that might be good for some cases, and another function that is just the best. I'll show you first the best way to achieve this:
It is the Levenshtein algorithm, which basically finds the number of characters you must add, edit, or remove from a string to make it match another one. At first it doesn't sound too useful, but take a look at this example:

  1.  
  2. < ?php
  3. // input misspelled word
  4. $input = 'carrrot';
  5.  
  6. // array of words to check against
  7. $words = array('apple','pineapple','banana','orange',
  8. 'radish','carrot','pea','bean','potato');
  9.  
  10. // no shortest distance found, yet
  11. $shortest = -1;
  12.  
  13. // loop through words to find the closest
  14. foreach ($words as $word) {
  15.  
  16. // calculate the distance between the input word,
  17. // and the current word
  18. $lev = levenshtein($input, $word);
  19.  
  20. // check for an exact match
  21. if ($lev == 0) {
  22.  
  23. // closest word is this one (exact match)
  24. $closest = $word;
  25. $shortest = 0;
  26.  
  27. // break out of the loop; we've found an exact match
  28. break;
  29. }
  30.  
  31. // if this distance is less than the next found shortest
  32. // distance, OR if a next shortest word has not yet been found
  33. if ($lev <= $shortest || $shortest < 0) {
  34. // set the closest match, and shortest distance
  35. $closest = $word;
  36. $shortest = $lev;
  37. }
  38. }
  39.  
  40. echo "Input word: $input\n";
  41. if ($shortest == 0) {
  42. echo "Exact match found: $closest\n";
  43. } else {
  44. echo "Did you mean: $closest?\n";
  45. }
  46.  
  47. ?>

This is an example where even a misspelled word can be found. It uses the Levenshtein to look for the word which is the most similar one, and then it is returned.
This is the output of the code before:

Input word: carrrot
Did you mean: carrot?

The use of this function is quite simple, although there are many optional parameters for more precise use. See the php.net reference for this function.

The other ways I said that could be used for this are soudex and metaphone, although their use might be more complicated for this particular suggestions use.
Soundex will create a key that is the same for all words that are pronounced the same.
For example, the following code:

  1.  
  2. < ?php
  3. echo soundex('beard').'<br />';
  4. echo soundex('bird').'<br />';
  5. echo soundex('bear');
  6. ?>
  7.  

Will produce this output:

B630
B630
B600

Where beard and bird are the same. This could make suggestions fast if you have already created a column in the mysql tables with the soundex key of the tags for example, so that you could search not only for the string, but also for its soundex key...
UPDATE: You can use MySQL's built in function SOUNDEX() to search both for the string as-is, or for the soundex too, to provide also misspelled words.

And finally, the metaphone function, is a variation of the soundex key that produces also a key that is the same for all words pronounced the same, but more accurately than soundex, since metaphone actually knows the rules of English pronounciation.
The use would be exactly the same as soundex, and if you are going to use something of the sort I would recommend metaphone over soundex for its improved accuracy.
But bear in mind that both soundex and metaphone won't probably work fine in most other languages, or at least for languages with phonemes that don't exist in English.

Hope you found this useful,
Alex

About Alex

Hello! I'm Alejandro U. Alvarez, an engineering student at Universidad de Oviedo (Spain). I started programming during my Freshman year in Brookline High School (Boston, MA), and then got more and more interested in web development. I'm almost in love with JavaScript, although I keep an open mind with other languages

14 thoughts on “Did you mean… ? In php

  1. “(…) already created a column in the mysql tables with the soundex key (…)”
    Or use SOUNDEX() function provided by MySQL.

    1. Nice, thanks for the advice, I didn’t know MySQL had that function. Then yes, use it directly, unless you want to use the metaphone function, which apparently isn’t included yet in MySQL (There is a request to have it included in following versions already)

      Thanks for that, I’ll update the post now to reflect that,
      Alex

  2. how big is the dictionary that you use? Levenshtein is O(mxn). you cant get much better for this sort of operation, but assuming that the input is 7 chars, and target string is an average length of 6, then we have 42 operations to determine its length. assuming a rather puny dictionary size of a 1000 words every page view/search will require 42000 operations? that sort of math doesnt scale.

    you may want to look at storing the results of each search in a dbms as a sort of long term cache.

    1. Well of course I wouldn’t use Levenshtein for large volumes of data without some sort of index or cache as you say…
      In case you want to do it with large dictionaries I would probably create a column with the soundex or metaphone keys and then search both for the string as-is and then for the soundex key.
      Using it that way you could even display the percentage of closeness…

      Probably i would say that Levenshtein is great for small sized databases, or array search. But for large scale search the soundex is just perfect.

      Thanks for the correction,
      Alex

  3. @Sergei:
    Nice!
    Although I’m not sure that they are using the best approach, since it is language-dependent, whereas I doubt Google actually performs a real spell check.
    I am guessing it searches for similar words using one of the functions (Or altered versions of them) to get slighly variated words, and then performs searches also with them…

    But you never know ;)

    1. Well that might be indeed a better solution, although I would like to test both with several different terms and cases and note down results and processing time to ensure what is the best way to approach this.
      Your might be better, although for normal sites that don’t really need that good search engines I guess it would be easier for them to run the MySQL query using SOUNDEX() and the soundex key of the input word…

      Thanks for that ;)

Leave a Reply