Перейти к содержимому
Последнее обновление

DAMERAU_LEVENSHTEIN_DISTANCE

Описание​

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

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

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

По сравнению с LEVENSHTEIN, функция DAMERAU_LEVENSHTEIN_DISTANCE считает перестановку соседних символов одной операцией редактирования, поэтому лучше подходит для обработки ошибок ввода, вызванных обратным порядком символов. Например, для преобразования abcd в abdc достаточно переставить соседние символы c и d, поэтому расстояние Дамерау-Левенштейна равно 1, а расстояние Левенштейна равно 2.

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

Синтаксис​

DAMERAU_LEVENSHTEIN_DISTANCE(<str1>, <str2>)

Параметры​

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

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

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

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

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

Примеры​

  1. Базовое использование
SELECT damerau_levenshtein_distance('kitten', 'sitting');
+---------------------------------------------------+
| damerau_levenshtein_distance('kitten', 'sitting') |
+---------------------------------------------------+
|                                                 3 |
+---------------------------------------------------+
  1. Перестановка соседних символов
SELECT damerau_levenshtein_distance('abcd', 'abdc');
+----------------------------------------------+
| damerau_levenshtein_distance('abcd', 'abdc') |
+----------------------------------------------+
|                                            1 |
+----------------------------------------------+

abcd можно преобразовать в abdc, переставив соседние символы c и d, поэтому расстояние равно 1.

  1. Отличие от LEVENSHTEIN
SELECT levenshtein('abcd', 'abdc'), damerau_levenshtein_distance('abcd', 'abdc');
+-----------------------------+----------------------------------------------+
| levenshtein('abcd', 'abdc') | damerau_levenshtein_distance('abcd', 'abdc') |
+-----------------------------+----------------------------------------------+
|                           2 |                                            1 |
+-----------------------------+----------------------------------------------+

LEVENSHTEIN не поддерживает перестановку, поэтому нужны 2 операции редактирования. DAMERAU_LEVENSHTEIN_DISTANCE поддерживает перестановку соседних символов, поэтому нужна только 1 операция редактирования.

  1. Символы UTF-8
SELECT damerau_levenshtein_distance('你好', '好你');
+--------------------------------------------------+
| damerau_levenshtein_distance('你好', '好你')     |
+--------------------------------------------------+
|                                                1 |
+--------------------------------------------------+

你 и 好 являются двумя символами UTF-8, а для перестановки соседних символов нужна 1 операция редактирования.

  1. Вставка, удаление и замена
SELECT
    damerau_levenshtein_distance('', 'abc'),
    damerau_levenshtein_distance('数据库', '数据'),
    damerau_levenshtein_distance('flaw', 'lawn');
+-----------------------------------------+-----------------------------------------------------+----------------------------------------------+
| damerau_levenshtein_distance('', 'abc') | damerau_levenshtein_distance('数据库', '数据')      | damerau_levenshtein_distance('flaw', 'lawn') |
+-----------------------------------------+-----------------------------------------------------+----------------------------------------------+
|                                       3 |                                                   1 |                                            2 |
+-----------------------------------------+-----------------------------------------------------+----------------------------------------------+
  1. Пример полного расстояния Дамерау-Левенштейна
SELECT damerau_levenshtein_distance('CA', 'ABC');
+-------------------------------------------+
| damerau_levenshtein_distance('CA', 'ABC') |
+-------------------------------------------+
|                                         2 |
+-------------------------------------------+

Эта функция вычисляет полное расстояние Дамерау-Левенштейна. Для CA и ABC минимальное расстояние редактирования равно 2.

  1. Аргументы NULL
SELECT damerau_levenshtein_distance(NULL, 'abc'), damerau_levenshtein_distance('abc', NULL);
+-------------------------------------------+-------------------------------------------+
| damerau_levenshtein_distance(NULL, 'abc') | damerau_levenshtein_distance('abc', NULL) |
+-------------------------------------------+-------------------------------------------+
|                                      NULL |                                      NULL |
+-------------------------------------------+-------------------------------------------+
  1. Слишком большой объём входных данных
SELECT damerau_levenshtein_distance(repeat('a', 4096), repeat('b', 4096));
ERROR 1105 (HY000): errCode = 2, detailMessage = (127.0.0.1)[INVALID_ARGUMENT]damerau_levenshtein_distance distance matrix is too large: 16793604 cells exceeds limit 16777216
Report issue