LEVENSHTEIN

Описание

Функция LEVENSHTEIN вычисляет расстояние Левенштейна между двумя строками.

Расстояние Левенштейна — это минимальное количество операций редактирования отдельных символов, необходимых для преобразования одной строки в другую. Поддерживаются следующие операции редактирования:

• Вставка символа
• Удаление символа
• Замена символа

Функция вычисляет расстояние по символам UTF-8, а не по байтам. Поэтому многобайтовые символы, например китайские иероглифы, учитываются как один символ каждый.

Псевдонимы

• LEVENSHTEIN_DISTANCE
• EDIT_DISTANCE

Синтаксис

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

Параметры

Параметр	Описание
<str1>	Первая строка. Тип: VARCHAR
<str2>	Вторая строка. Тип: VARCHAR

Возвращаемое значение

Возвращает значение типа INT, представляющее расстояние Левенштейна между двумя строками.

Особые случаи:

• Если хотя бы один аргумент равен NULL, возвращает NULL.
• Если строки совпадают, возвращает 0.
• Если одна строка пустая, возвращает количество символов в другой строке.
• Функция коммутативна: LEVENSHTEIN(a, b) и LEVENSHTEIN(b, a) возвращают одинаковый результат.

Примеры

1. Базовое использование

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

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

kitten можно преобразовать в sitting за 3 операции: заменить k на s, заменить e на i и вставить g в конце.

2. Одинаковые строки

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

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

3. Пустая строка

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

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

4. Символы UTF-8

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

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

Для замены 界 на 间 требуется 1 операция.

5. Перестановка соседних символов считается двумя операциями

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

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

При вычислении расстояния Левенштейна перестановка соседних символов не считается одной операцией, поэтому расстояние между abcd и abdc равно 2.

6. Использование псевдонимов

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

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

7. Аргументы NULL

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

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