LEVENSHTEIN

Description

The LEVENSHTEIN function calculates the Levenshtein edit distance between two strings.

The Levenshtein edit distance is the minimum number of single-character edits required to transform one string into another. Supported edit operations include:

• Insert a character
• Delete a character
• Substitute a character

This function calculates distance by UTF-8 characters, not by bytes. Therefore, multibyte characters such as Chinese characters are treated as one character.

Alias

• LEVENSHTEIN_DISTANCE
• EDIT_DISTANCE

Syntax

LEVENSHTEIN(<str1>, <str2>)
LEVENSHTEIN_DISTANCE(<str1>, <str2>)
EDIT_DISTANCE(<str1>, <str2>)

Parameters

Parameter	Description
<str1>	The first string. Type: VARCHAR
<str2>	The second string. Type: VARCHAR

Return Value

Returns an INT value representing the Levenshtein edit distance between the two strings.

Special cases:

• If any argument is NULL, returns NULL.
• If the two strings are identical, returns 0.
• If one string is empty, returns the character count of the other string.
• This function is commutative, meaning LEVENSHTEIN(a, b) and LEVENSHTEIN(b, a) return the same result.

Examples

1. Basic usage

SELECT levenshtein('kitten', 'sitting');

+----------------------------------+
| levenshtein('kitten', 'sitting') |
+----------------------------------+
|                                3 |
+----------------------------------+

kitten can be transformed into sitting with 3 edits: substitute k with s, substitute e with i, and insert g at the end.

2. Identical strings

SELECT levenshtein('abc', 'abc');

+---------------------------+
| levenshtein('abc', 'abc') |
+---------------------------+
|                         0 |
+---------------------------+

3. Empty string

SELECT levenshtein('', 'abc'), levenshtein('数据库', '');

+------------------------+------------------------------+
| levenshtein('', 'abc') | levenshtein('数据库', '')    |
+------------------------+------------------------------+
|                      3 |                            3 |
+------------------------+------------------------------+

4. UTF-8 characters

SELECT levenshtein('你好世界', '你好世间');

+---------------------------------------------+
| levenshtein('你好世界', '你好世间')         |
+---------------------------------------------+
|                                           1 |
+---------------------------------------------+

Replacing 界 with 间 requires 1 edit.

5. Adjacent transposition is counted as two edits

SELECT levenshtein('abcd', 'abdc');

+-----------------------------+
| levenshtein('abcd', 'abdc') |
+-----------------------------+
|                           2 |
+-----------------------------+

Levenshtein distance does not treat adjacent character transposition as a single operation, so the distance between abcd and abdc is 2.

6. Use aliases

SELECT levenshtein_distance('abcd', 'abdc'), edit_distance('kitten', 'sitting');

+--------------------------------------+------------------------------------+
| levenshtein_distance('abcd', 'abdc') | edit_distance('kitten', 'sitting') |
+--------------------------------------+------------------------------------+
|                                    2 |                                  3 |
+--------------------------------------+------------------------------------+

7. NULL arguments

SELECT levenshtein(NULL, 'abc'), levenshtein('abc', NULL);

+--------------------------+--------------------------+
| levenshtein(NULL, 'abc') | levenshtein('abc', NULL) |
+--------------------------+--------------------------+
|                     NULL |                     NULL |
+--------------------------+--------------------------+