Text::LevenshteinXS

📦 std

The Levenshtein edit distance of two strings: the fewest insertions, deletions and substitutions that turn one into the other.

distance($s, $t) is exported by default. It compares bytes: a character string counts the bytes of its UTF-8 form, and a string ends at its first NUL byte, as the C strings of upstream’s XS do.

This is a native implementation of Text::LevenshteinXS 0.03’s LevenshteinXS.xs; its Text/LevenshteinXS.pm is used unchanged.

Synopsis

use Text::LevenshteinXS;

print distance("foo", "four"), "\n";     # 2
print distance("kitten", "sitting"), "\n";  # 3

Differences from upstream

One, where perl 5.44 with LevenshteinXS.xs fails (t/81-xs-native/Text-LevenshteinXS/150-or-better.t): long strings. LevenshteinXS.xs allocates a table of (n+1)(m+1) ints for strings of n and m bytes, does not check the allocation, and indexes the table with an int; when the memory is not there (two strings of 20000 bytes need 1.6 GB), or once n*m passes 2**31, it dumps core. Here the distance is computed in two rows of the shorter string’s length.

Functions

Edit distance

distance

distance($s, $t): the Levenshtein distance of the two strings’ bytes.