Fuzzy String Search Using Levenshtein Distance

Fuzzy search tolerates typos by measuring how many single-character edits (insertions, deletions, substitutions) separate the query from each candidate. This is what PHP’s built-in levenshtein() computes. The function lowercases both sides for case-insensitive comparison. If the query is a substring of a candidate, the distance is forced to 0 regardless of what levenshtein returns, so prefix matches always rank first.

Candidates with a distance above maxDistance are discarded. The remaining matches are annotated with a percentage similarity score computed as 1 - distance / max(strlen(query), strlen(candidate)) and sorted by distance ascending so the closest matches appear first.

<?php

/**
 * Fuzzy search using Levenshtein distance.
 * Returns matches sorted by similarity, filtered by max allowed distance.
 */
function fuzzySearch(string $query, array $haystack, int $maxDistance = 3): array
{
    $query   = strtolower($query);
    $results = [];

    foreach ($haystack as $item) {
        $lower    = strtolower($item);
        $distance = levenshtein($query, $lower);

        // Also check if query is a substring (distance 0 for exact prefix)
        if (str_contains($lower, $query)) {
            $distance = 0;
        }

        if ($distance <= $maxDistance) {
            $results[] = [
                'item'       => $item,
                'distance'   => $distance,
                'similarity' => round((1 - $distance / max(strlen($query), strlen($lower))) * 100),
            ];
        }
    }

    usort($results, fn($a, $b) => $a['distance'] <=> $b['distance']);
    return $results;
}

// Demo: command name typo correction
$commands = [
    'migrate', 'migrate:fresh', 'migrate:rollback', 'make:model',
    'make:controller', 'make:migration', 'route:list', 'route:clear',
    'cache:clear', 'config:cache', 'queue:work', 'queue:listen',
    'serve', 'tinker', 'test',
];

$typos = ['migarte', 'mak:model', 'rote:list', 'cach:clear', 'tinkr'];

foreach ($typos as $typo) {
    echo "Input: \"$typo\"\n";
    $matches = fuzzySearch($typo, $commands, maxDistance: 4);
    foreach (array_slice($matches, 0, 3) as $m) {
        printf("  -> \"%s\" (distance: %d, similarity: %d%%)\n",
            $m['item'], $m['distance'], $m['similarity']);
    }
    echo "\n";
}