Ответ 1
Помогает ли это? Запрос расстояния между MySQL Levenshtein
EDIT: устаревшая ссылка Леванштейн Расстояние как хранимая функция MySQL (Google Cache), благодаря Роберту, указав это на комментарий.
Реализация расстояния Левенштейна для mysql/нечеткого поиска?
Я хотел бы иметь возможность искать таблицу следующим образом для кузанта, как получить все, что в пределах 1 дисперсии.
Данные:
O'Brien Smithe Dolan Smuth Wong Smoth Gunther Smiht
Я изучил использование расстояния Левенштейна, кто-нибудь знает, как реализовать это с ним?
Ответы
Ответ 2
Для эффективного поиска с использованием расстояния levenshtein вам нужен эффективный специализированный индекс, например bk-tree. К сожалению, ни одна система баз данных, о которой я знаю, включая MySQL, не реализует индексы bk-tree. Это сложнее, если вы ищете полнотекстовый поиск, а не только один член в строке. Вне рук, я не могу думать о том, что вы можете делать полнотекстовое индексирование таким образом, чтобы можно было искать на основе levenshtein distance.
Ответ 3
Реализация для дамеру-левенштейна может быть найдена здесь: Алгоритм Дамерау-Левенштейна: Левенштейн с транспозициями Улучшение по сравнению с чистым расстоянием Левенштейна заключается в том, что рассматривается замена символов. Я нашел его в комментариях ссылки schnaader, спасибо!
Ответ 4
Существует реализация mysql UDF функции расстояния Левенштейна
https://github.com/jmcejuela/Levenshtein-MySQL-UDF
Он реализован на C и имеет более высокую производительность, чем "запрос расстояния MySQL Levenshtein", упомянутый schnaader
Ответ 5
Функция, приведенная выше для levenshtein <= 1, неверна - она дает неверные результаты, например, "кровать" и "ставка".
Я изменил "запрос расстояния между MySQL Levenshtein", указанный выше, в первом ответе, чтобы принять "предел", который немного ускорит его. В принципе, если вы только заботитесь о Levenshtein <= 1, установите предел на "2", и функция вернет точное расстояние levenshtein, если оно равно 0 или 1; или 2, если точное расстояние levenshtein 2 или больше.
Этот мод делает его на 15-50% быстрее - чем дольше ваше слово поиска, тем больше преимущество (потому что алгоритм может поручиться раньше). Например, при поиске по 200 000 слов, чтобы найти все совпадения на расстоянии 1 слова "хихиканье", оригинал занимает 3 минуты 47 секунд на моем ноутбуке, против 1:39 для "предельной" версии. Конечно, они слишком медленны для любого использования в режиме реального времени.
код:
DELIMITER $$
CREATE FUNCTION levenshtein_limit_n( s1 VARCHAR(255), s2 VARCHAR(255), n INT)
RETURNS INT
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost, c_min INT;
DECLARE s1_char CHAR;
-- max strlen=255
DECLARE cv0, cv1 VARBINARY(256);
SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0, c_min = 0;
IF s1 = s2 THEN
RETURN 0;
ELSEIF s1_len = 0 THEN
RETURN s2_len;
ELSEIF s2_len = 0 THEN
RETURN s1_len;
ELSE
WHILE j <= s2_len DO
SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
END WHILE;
WHILE i <= s1_len and c_min < n DO -- if actual levenshtein dist >= limit, don't bother computing it
SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = i, cv0 = UNHEX(HEX(i)), j = 1;
WHILE j <= s2_len DO
SET c = c + 1;
IF s1_char = SUBSTRING(s2, j, 1) THEN
SET cost = 0; ELSE SET cost = 1;
END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
IF c > c_temp THEN SET c = c_temp; END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
IF c > c_temp THEN
SET c = c_temp;
END IF;
SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
IF c < c_min THEN
SET c_min = c;
END IF;
END WHILE;
SET cv1 = cv0, i = i + 1;
END WHILE;
END IF;
IF i <= s1_len THEN -- we didn't finish, limit exceeded
SET c = c_min; -- actual distance is >= c_min (i.e., the smallest value in the last computed row of the matrix)
END IF;
RETURN c;
END$$
Ответ 6
Я настраиваю поиск на основе Левенштейна или Дамерау-Левенштейна (возможно, последнего) для нескольких поисков по индексированному тексту на основе статьи Гонсало Наварро и Рикардо Баэза-ятес: текст ссылки
После создания массива суффиксов (см. wikipedia), если вас интересует строка, содержащая не более k несоответствий в строке поиска, разбить строку поиска на k + 1 штуку; по крайней мере один из них должен быть неповрежденным. Найдите подстроки бинарным поиском по массиву суффиксов, затем примените функцию расстояния к патчу вокруг каждой согласованной части.
Ответ 7
эту функцию можно использовать
CREATE FUNCTION `levenshtein`( s1 text, s2 text) RETURNS int(11)
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
DECLARE s1_char CHAR;
DECLARE cv0, cv1 text;
SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
IF s1 = s2 THEN
RETURN 0;
ELSEIF s1_len = 0 THEN
RETURN s2_len;
ELSEIF s2_len = 0 THEN
RETURN s1_len;
ELSE
WHILE j <= s2_len DO
SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
END WHILE;
WHILE i <= s1_len DO
SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
WHILE j <= s2_len DO
SET c = c + 1;
IF s1_char = SUBSTRING(s2, j, 1) THEN
SET cost = 0; ELSE SET cost = 1;
END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
IF c > c_temp THEN SET c = c_temp; END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
IF c > c_temp THEN
SET c = c_temp;
END IF;
SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
END WHILE;
SET cv1 = cv0, i = i + 1;
END WHILE;
END IF;
RETURN c;
END
и для получения этой функции, как XX%, используйте эту функцию
CREATE FUNCTION `levenshtein_ratio`( s1 text, s2 text ) RETURNS int(11)
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, max_len INT;
SET s1_len = LENGTH(s1), s2_len = LENGTH(s2);
IF s1_len > s2_len THEN
SET max_len = s1_len;
ELSE
SET max_len = s2_len;
END IF;
RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100);
END
Ответ 8
Если вы хотите узнать, не превышает ли levenshtein-расстояние 1, вы можете использовать следующую функцию MySQL.
CREATE FUNCTION `lv_leq_1` (
`s1` VARCHAR( 255 ) ,
`s2` VARCHAR( 255 )
) RETURNS TINYINT( 1 ) DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, i INT;
SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), i = 1;
IF s1 = s2 THEN
RETURN TRUE;
ELSEIF ABS(s1_len - s2_len) > 1 THEN
RETURN FALSE;
ELSE
WHILE SUBSTRING(s1,s1_len - i,1) = SUBSTRING(s2,s2_len - i,1) DO
SET i = i + 1;
END WHILE;
RETURN SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i) OR SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i+1) OR SUBSTRING(s1,1,s1_len-i+1) = SUBSTRING(s2,1,s2_len-i);
END IF;
END
Это в основном один шаг в рекурсивном описании расстояния Левенштейна. Функция возвращает 1, если расстояние не больше 1, иначе оно возвращает 0.
Поскольку эта функция не полностью вычисляет расстояние levenshtein, она намного быстрее.
Вы также можете изменить эту функцию таким образом, чтобы она возвращала true, если расстояние levenshtein не более 2 или 3, вызвав его рекурсивно. Если MySQL не поддерживает рекурсивные вызовы, вы можете копировать несколько измененных версий этой функции два раза и вызывать их вместо этого. Но вы не должны использовать рекурсивную функцию для вычисления точного расстояния levenshtein.
Ответ 9
У меня был специализированный случай поиска по k-расстоянию, и после установки UDF Damerau-Levenshtein в MySQL было установлено, что запрос занимает слишком много времени. Я придумал следующее решение:
- У меня очень ограниченное пространство поиска (9 символов, ограниченных числовыми значениями).
Создайте новую таблицу (или добавьте столбцы в целевую таблицу) со столбцами для каждой позиции символа в целевом поле. то есть. Мой VARCHAR (9) оказался в виде 9 столбцов TINYINT + 1 Id, соответствующих моей основной таблице (добавьте индексы для каждого столбца). Я добавил триггеры для обеспечения того, чтобы эти новые столбцы всегда обновлялись при обновлении моей основной таблицы.
Для выполнения запроса k-distance используйте следующий предикат:
(Column1 = s [0]) + (Column2 = s [1]) + (Column3 = s [2]) + (Column4 = s [3]) +... >= m
где s - ваша строка поиска, а m - необходимое количество совпадающих символов (или m = 9 - d в моем случае, где d - максимальное расстояние, которое я хочу вернуть).
После тестирования я обнаружил, что запрос более 1 миллиона строк, занимающих в среднем 4,6 секунды, возвращал соответствующие идентификаторы менее чем за секунду. Второй запрос для возврата данных для совпадающих строк в моей основной таблице аналогичным образом занял второе место. (Объединение этих двух запросов в качестве подзапроса или соединения привело к значительному увеличению времени выполнения, и я не уверен, почему.)
Хотя это не Damerau-Levenshtein (не учитывает замену), это достаточно для моих целей.
Хотя это решение, вероятно, недостаточно хорошо масштабируется для большего (длинного) пространства поиска, оно очень хорошо работало для этого ограничительного случая.
Ответ 10
Основываясь на Ответ Chella и Ryan Ginstrom статья, нечеткий поиск мог быть реализованы так:
DELIMITER $$
CREATE FUNCTION fuzzy_substring( s1 VARCHAR(255), s2 VARCHAR(255) )
RETURNS INT
DETERMINISTIC
BEGIN
DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
DECLARE s1_char CHAR;
-- max strlen=255
DECLARE cv0, cv1 VARBINARY(256);
SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
IF s1 = s2 THEN
RETURN 0;
ELSEIF s1_len = 0 THEN
RETURN s2_len;
ELSEIF s2_len = 0 THEN
RETURN s1_len;
ELSE
WHILE j <= s2_len DO
SET cv1 = CONCAT(cv1, UNHEX(HEX(0))), j = j + 1;
END WHILE;
WHILE i <= s1_len DO
SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
WHILE j <= s2_len DO
SET c = c + 1;
IF s1_char = SUBSTRING(s2, j, 1) THEN
SET cost = 0; ELSE SET cost = 1;
END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
IF c > c_temp THEN SET c = c_temp; END IF;
SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
IF c > c_temp THEN
SET c = c_temp;
END IF;
SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
END WHILE;
SET cv1 = cv0, i = i + 1;
END WHILE;
END IF;
SET j = 1;
WHILE j <= s2_len DO
SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10);
IF c > c_temp THEN
SET c = c_temp;
END IF;
SET j = j + 1;
END WHILE;
RETURN c;
END$$
DELIMITER ;