grapheme_levenshtein() in PHP 8.5: what the docs don't tell you

#php

PHP's levenshtein() has always counted bytes. For English that's invisible. For Hungarian, Polish, Czech, or anything with accents, it quietly lies:

levenshtein('szőke', 'szoke'); // 2, but it's one edit

The ő is two bytes in UTF-8 (C5 91), so the function sees two edits. PHP 8.5 finally adds grapheme_levenshtein(), which counts user-perceived characters instead. Every article I found about it explains the syntax. None of them measured it, so I did.

Setup

PHP 8.5.10 (CLI, built from source), ICU 74.2, default settings, no JIT
Synthetic Hungarian-style words (with sz, cs, ő, ű, ...), each compared with a copy containing one random edit
20,000 pairs per length, best of 3 rounds, nanoseconds per comparison
Single vCPU sandbox: absolute numbers will differ on your machine, the ratios are what matter.

What it fixes

Pair	`levenshtein()`	code points	`grapheme_levenshtein()`
`szőke` vs `szoke`	2	1	1
`Kovács` vs `Kovacs`	2	1	1
`ő` vs `ö`	2	1	1
`é` (NFC) vs `é` (NFD)	3	2	0
👩‍💻 vs 👩	7	2	1

The NFC/NFD row is the real win. The same visible é can be stored as one code point or two (e + combining accent), depending on where the data came from. The byte version reports 3 edits between two strings that look identical. The grapheme version correctly reports 0.

What it costs

Length	`levenshtein()`	`grapheme_levenshtein()`	with `locale='hu'`	userland, code points
8 chars	0.22 µs	3.3 µs	4.0 µs	3.8 µs
24 chars	1.3 µs	14.1 µs	17.6 µs	29.2 µs
64 chars	6.4 µs	76.9 µs	98.2 µs	196.1 µs

Three things stand out:

It is 11-15x slower than the byte version. Correctness isn't free: the function segments both strings into grapheme clusters and compares them through ICU.
It beats a userland implementation by about 1.2x on short strings and 2-2.6x on longer ones. If you were using a pure PHP multibyte Levenshtein, switching is a clear win.
The $locale parameter adds 23-28% on top.

The manual documents the complexity as O(m*n). In practice that means you should not run it over a whole table: at 24 characters, 1M rows is roughly 14 seconds of CPU per query, versus about 1.3 seconds for the byte version.

Two surprises

Invisible characters can compare as equal. In my tests on 8.5.10:

grapheme_levenshtein("\x01", "\x02");          // 0
grapheme_levenshtein("\u{200B}", "\u{200C}");  // 0
grapheme_levenshtein("\x01", "");              // 1

Two different control or zero-width characters are treated as identical to each other, yet each one differs from an empty string. The equality check is a collation comparison, and ICU collation ignores some characters completely. Mid-word cases behave less predictably ("a\u{200B}b" vs "a\u{200C}b" gave 1, while "a\x01b" vs "a\x02b" gave 0). A soft hyphen (U+00AD) is not ignored and costs one edit. This matches a recently reported php-src issue, so check the current status before relying on either behavior.

For search this is mostly harmless, but if you use the distance for deduplication or validation, strip control and format characters first.

The locale parameter changed nothing in my tests. I compared hu against en on every case above, including cs vs c and sz vs s, where you might hope for Hungarian digraph awareness. The results were identical in all cases. It only added the 23-28% cost. I'm not claiming it never matters (I can't rule out effects on other scripts or case-insensitive comparisons), but for Hungarian names it bought me nothing.

Also note that the comparison is case-sensitive: Kovács vs kovács is 1.

So how should you use it?

Don't scan with it, re-rank with it. Let the database produce candidates cheaply and let PHP do the precise scoring on a handful of rows.

-- PostgreSQL + pg_trgm: fast candidate generation
SELECT name
FROM people
WHERE name % :query
ORDER BY similarity(name, :query) DESC
LIMIT 50;

function clean(string $s): string
{
    // strip control/format characters, then lowercase
    return mb_strtolower(preg_replace('/[\p{Cc}\p{Cf}]/u', '', $s));
}

function rerank(string $query, array $candidates, int $maxDistance = 2): array
{
    $q = clean($query);
    $scored = [];
    foreach ($candidates as $name) {
        $d = grapheme_levenshtein($q, clean($name));
        if ($d !== false && $d <= $maxDistance) {
            $scored[$name] = $d;
        }
    }
    asort($scored);
    return $scored;
}

rerank('Szoke', ['Szőke', 'Szűcs', 'Szabó', 'SZOKE']);
// ['SZOKE' => 0, 'Szőke' => 1]

Re-ranking 50 candidates of around 24 characters costs about 0.7 ms (50 x 14 µs), which is nothing next to the query itself. That's the sweet spot: the accuracy of a grapheme-aware distance at a cost you never notice.

Takeaways

Use grapheme_levenshtein() over levenshtein() whenever your data has accents or mixed Unicode normalization.
Expect ~12x the cost of the byte version, and never run it over a full table.
Normalize case and strip invisible characters yourself.
Measure before you reach for $locale.

I ran into all of this while building Fuzzphony, a PostgreSQL-native search library for PHP and Symfony. If you have your own numbers from a different machine or dataset, I'd love to see them in the comments.

DEV Community