levenshtein()

Purpose

levenshtein() counts how many single-character edits are needed to turn one string into another. An edit is an insertion, a replacement or a deletion. The result is a plain integer: 0 means the strings are identical, and larger numbers mean they are further apart. It is a common building block for "did you mean?" suggestions, fuzzy matching of user input and simple typo detection.

Signature

Parameters and defaults

• $string1 is the starting string.
• $string2 is the target string.
• $insertion_cost is the cost of inserting one character. It defaults to 1.
• $replacement_cost is the cost of replacing one character with another. It defaults to 1.
• $deletion_cost is the cost of deleting one character. It defaults to 1.

The direction matters when costs differ. The function describes the work of changing $string1 into $string2, so insertions add characters that $string2 has and $string1 lacks, and deletions remove characters that only $string1 has. If the costs are not all 1, the algorithm picks the cheapest combination of edits. For example, when an insertion plus a deletion costs less than a replacement, it prefers those two edits over one replacement.

Return value and failure cases

The function returns the total cost as an int. With default costs this is the minimal number of edits. In PHP 8.0.0 and later you can pass either two arguments or all five, and the old limit on strings longer than 255 characters is gone, so the old -1 result for long strings no longer applies. You should not need to check for -1 in PHP 8.4 code.

There is no special failure return value. The parameters are typed, so passing a value that cannot be used as the declared type raises a TypeError, for instance an array or, under declare(strict_types=1), a number where a string is expected.

The algorithm runs in time proportional to the product of the two string lengths. That is cheaper than similar_text(), but it still grows quickly, so avoid comparing very large strings against very large lists.

Example 1: basic distances

This example shows a mixed edit, a delete-plus-insert case, identical strings and an empty string. Comparing with an empty string costs one insertion per character of the other string.

<?php
echo json_encode([
    'kitten_sitting' => levenshtein('kitten', 'sitting'),
    'flaw_lawn' => levenshtein('flaw', 'lawn'),
    'same' => levenshtein('php', 'php'),
    'empty' => levenshtein('', 'php'),
], JSON_UNESCAPED_UNICODE | JSON_UNESCAPED_SLASHES);
echo PHP_EOL;

{"kitten_sitting":3,"flaw_lawn":2,"same":0,"empty":3}

Example 2: custom costs

Here the same pair of strings gives different results depending on the costs. With an expensive replacement, one replacement is swapped for a deletion and an insertion. Inserting and deleting the same character can also cost different amounts.

<?php
echo json_encode([
    'default' => levenshtein('cat', 'cut'),
    'expensive_replace' => levenshtein('cat', 'cut', 1, 5, 1),
    'insert_cost' => levenshtein('cat', 'cart', 5, 1, 1),
    'delete_cost' => levenshtein('cart', 'cat', 5, 1, 1),
], JSON_UNESCAPED_UNICODE | JSON_UNESCAPED_SLASHES);
echo PHP_EOL;

{"default":1,"expensive_replace":2,"insert_cost":5,"delete_cost":1}

Example 3: closest match

A typical use is picking the nearest candidate from a list. Because the comparison uses <, the first candidate wins when two have the same distance.

<?php
function closestWord(string $input, array $words): array
{
    $best = null;
    $bestDistance = PHP_INT_MAX;

    foreach ($words as $word) {
        $distance = levenshtein($input, $word);
        if ($distance < $bestDistance) {
            $best = $word;
            $bestDistance = $distance;
        }
    }

    return ['word' => $best, 'distance' => $bestDistance];
}

echo json_encode(closestWord('bananna', ['apple', 'banana', 'orange', 'grape']), JSON_UNESCAPED_UNICODE | JSON_UNESCAPED_SLASHES);
echo PHP_EOL;

{"word":"banana","distance":1}

Edge cases

• Case sensitivity: levenshtein('PHP', 'php') is 3, because each letter differs. Normalize case first, for example with strtolower(), when you want case-insensitive matching.
• Bytes, not characters: the function works on bytes. An accented UTF-8 letter such as é occupies two bytes, so levenshtein('e', 'é') is 2 rather than 1. For accurate multibyte comparison you need to map characters to a single-byte representation or use another approach.
• Empty strings: the distance to an empty string equals the length in bytes of the other string with default costs.
• Asymmetric costs: swapping the arguments can change the result when insertion and deletion costs differ.

Common mistakes

1. Treating the distance as a percentage. It is an absolute count, so a distance of 2 is large for a 3-letter word and small for a 30-letter one. Divide by the longer length if you need a relative score.
2. Forgetting to normalize case, whitespace or accents before comparing user input.
3. Passing the arguments in the wrong order when using custom costs.
4. Still checking for -1 from the pre-8.0 long-string behavior.
5. Running it against huge lists on every request without limiting candidates.

Related functions

• similar_text() calculates a similarity count and percentage, but is slower.
• soundex() creates a phonetic key for English-sounding words.
• metaphone() creates another phonetic key.

Recap

levenshtein() returns the cheapest total cost of insertions, replacements and deletions needed to turn the first string into the second. The default cost for each edit is 1, the work is byte based and case sensitive, and the result is an integer you can compare or normalize for fuzzy matching.