turicreate.toolkits.distances.levenshtein

turicreate.toolkits.distances.levenshtein(x, y)

Compute the Levenshtein distance between between strings. The distance is the number of insertion, deletion, and substitution edits needed to transform string x into string y. The mathematical definition of Levenshtein is recursive:

\[ \begin{align}\begin{aligned}D(x, y) = d(|x|, |y|)\\d(i, j) = \max(i, j), \quad \mathrm{if } \min(i, j) = 0\\d(i, j) = \min \Big \{d(i-1, j) + 1, \ d(i, j-1) + 1, \ d(i-1, j-1) + I(x_i \neq y_i) \Big \}, \quad \mathrm{else}\end{aligned}\end{align} \]

Parameters:

x : string

First input string.

y : string

Second input string.

Returns:

out : float

Levenshtein distance between x and y.

References

• Wikipedia - Levenshtein distance

Examples

>>> tc.distances.levenshtein("fossa", "fossil")
2.0