Find The Nearest Word Using The Levenshtein Function In PHP

The levenshtein() function is part of a set of functions that are used to look at the structure of a string depending on how the string sounds, using levenshtein() allows you to look at the total difference between two strings, defined as a distance value. The important feature of this is that you can compare one string to another and see if they are similar.

The levenshtein() function takes two parameters, these are the two strings that you want to compare with each other. If the two strings are the same then the distance is zero, the higher this value is the more distance there is between two strings. Here are some examples.

echo levenshtein('word','word'); // 0
echo levenshtein('stone','magnet'); // 4
echo levenshtein('window','windmill'); // 4
echo levenshtein('wibble','wobble'); // 1
echo levenshtein('test','toast'); // 2
echo levenshtein('I','antidisestablishmentarianism'); // 28

So does this have any practical uses? The short answer is yes. One of the best things you can do with this function is to create either a spell checker or a Google style "did you mean" along with your search queries.

In order to do this you must first load in a dictionary of words that you can use. I found a good set of word lists on the Internet and doctored this to reduce the word count a little. This new English word list has 6,752 words and is about 65KB in size, which means it can be loaded into memory with minimal fuss.

This dictionary is loaded into memory by the use of the following bit of code.

$dictionary = 'english.txt';
$handle = fopen($dictionary, "r");
 
while(!feof($handle)){
 $words .= fread($handle, 8192);
}
 
fclose($handle);
$words = explode("\n",$words);

We now have an array of words. If we were to input a misspelled word the script now needs to use the dictionary to compare this word and find the one that is closest to the inputted word.

$input = stripslashes(strip_tags($_GET['q']));

First we loop through every word in our dictionary and compare it against out current word.

foreach ($words as $word) {
  $lev = levenshtein($input, $word);
}

There are two situations that we should encounter on each iteration of the loop.

1. The input word will find an exact match in the array of words. This is found by a levenshtein distance of zero.
2. The levenshtein() of the current word will be less than that of any other word looked at so far.

To account for the first situation we just say that if the levenshtein value is zero then break out of the loop. There is no point in running all the way through the rest of the array if we know that we already have what we are looking for.

The second situation is resolved by storing the smallest distance and using this to see if the next word is any less, and so on. Once the loop has finished we should have a word that closely matches our inputted word. We should set this distance to -1 initially as the levenshtein() function will never return less than zero.

$distance = -1;
 
foreach($words as $word){  
 $lev = levenshtein($input, $word);  
 
 // exact match
 if($lev == 0){  
  $closest = $word;  
  $distance = 0;  
  // no need to continue as we have found exact match
  break;  
 }  
 
 // if distance is less than the currently stored distance and it is less than our initial value
 if($lev <= $distance || $distance < 0){
  $closest  = $word;  
  $distance = $lev;  
 }
}

The $closest variable now contains our closest (or exactly) matching word and the $distance value shows the distance between the two words, which might be zero.

We can now print out the results. If we are creating this for a search function then we don't need to print out an exact match, just the closest matching word. A simple if statement to check if the distance is greater than zero solves this.

if ($distance > 0) {
  echo "Did you mean: ".$closest."?";
}

Here is an example page of the code in action, I have printed out the input variable for convenience.

More information about levenshtein can be found at the levenshtein wikipedia page.