PHP: Building a “Did you mean X?” suggestion engine using the levenshtein function

If you’ve ever used command line tools like WP-CLI (WordPress) or Artisan (Laravel), and you mistype a command, they’ll prompt you with the closet suggested command.

I’ve always wondered how the guessing of which command you meant to use worked. Until now. It turns out these work using a built-in PHP function called levenshtein.

What does the levenshtein function do?

It calculates the Levenshtein distance between two strings. Or, in English, the number of changes (insertion, deletion or replacement of characters) that would need to be made to a string for it to match another string.

Simple Example

In this example, we’ll compare the difference between scheme and schema.

$result = levenshtein('scheme', 'schema'); 

This returns a result of 1, because the simplest change is to replace the “e” with an “a”.

Closest Command Example

Back to our original goal, how do we use levenshtein to find the closest command?

You’ll need an array of all supported commands, and then you run levenshtein over that array to find the result with the least number of changes required.

In this function, we’re first checking to see if the input command is in the commands array, and if so just returning that. This is faster than calculating the levenshtein value, which would equal 0. If it’s not an exact match, we loop over the commands array to find the command with the least number of changes required.

function find_closest_command(string $input) {
     $commands = [
          'export',
          'db',
          'import',
          'schema:dump',
          'config',     
     ];

     if (in_array($input, $commands, true)) {
        return $input;
     }


     $shortest = -1;
     $closest = $input;

     foreach($commands as $command) {
          $levenshtein = levenshtein($input, $command);

          if ($levenshtein <= $shortest || $shortest < 0) {
              $closest  = $command;
              $shortest = $levenshtein;
          }
     }

     return $closest;
}


$input = 'scheme:dump';
$closest = find_closest_command($input);
if ($input === $closest) {
    echo 'Exact Match';
} else { 
    echo "Did you mean $closest?";
}

Running this results in the expected “Did you mean schema:dump?” seen in the screenshot at the top of this post!