Home/ Manual/ intl / grapheme/ grapheme_levenshtein

grapheme_levenshtein

PHP function Edit on GitHub ✎

Calculate Levenshtein distance between two strings in grapheme units

Description

Procedural

grapheme_levenshtein(string $string1, string $string2, int $insertion_cost = 1, int $replacement_cost = 1, int $deletion_cost = 1, string $locale = ""): int|false

The Levenshtein distance is defined as the minimal number of grapheme clusters that have to be replaced, inserted, or deleted to transform string1 into string2. The complexity of the algorithm is O(m*n), where n and m are the length of string1 and string2 in grapheme units.

Unlike levenshtein(), which operates on bytes, this function counts Unicode grapheme clusters, so composed and decomposed forms of the same character (e.g. U+00E9 and U+0065 U+0301, both representing é) are treated as equivalent and have a distance of zero.

If insertion_cost, replacement_cost and/or deletion_cost are unequal to 1, the algorithm adapts to choose the cheapest transforms. For example, if $insertion_cost + $deletion_cost < $replacement_cost, no replacements will be done, but rather inserts and deletions instead.

Parameters

string1: One of the strings being evaluated for Levenshtein distance. Must be valid UTF-8.
string2: One of the strings being evaluated for Levenshtein distance. Must be valid UTF-8.
insertion_cost: Defines the cost of insertion. Must be greater than 0.
replacement_cost: Defines the cost of replacement. Must be greater than 0.
deletion_cost: Defines the cost of deletion. Must be greater than 0.
locale: Locale

Return Values

Returns the Levenshtein distance between the two strings, measured in grapheme units, or false on failure. Use intl_get_error_message() to retrieve details about the failure.

Errors/Exceptions

Throws a ValueError if insertion_cost, replacement_cost, or deletion_cost is less than or equal to 0.

Returns false and sets an intl error if either input string is not valid UTF-8, if locale is not a valid locale identifier, or if an internal ICU error occurs.

Changelog

Version	Description
8.5.0	This function has been added.

Examples

grapheme_levenshtein() example

php

<?php

// Composed form (NFC): U+00E9 LATIN SMALL LETTER E WITH ACUTE
$e_composed = "\u{00E9}";

// Decomposed form (NFD): U+0065 + U+0301 (e + combining acute accent)
$e_decomposed = "\u{0065}\u{0301}";

// grapheme_levenshtein treats them as the same grapheme cluster
var_dump(grapheme_levenshtein($e_composed, $e_decomposed));

// levenshtein() operates on bytes and sees them as different
var_dump(levenshtein($e_composed, $e_decomposed));

?>

The above example will output:

output

int(0)
int(3)