Реализация расстояния Левенштейна для mysql/нечеткого поиска?

Я хотел бы иметь возможность искать таблицу следующим образом для кузанта, как получить все, что в пределах 1 дисперсии.

Данные:

O'Brien
Smithe
Dolan
Smuth
Wong
Smoth
Gunther
Smiht

Я изучил использование расстояния Левенштейна, кто-нибудь знает, как реализовать это с ним?

Ответ 1

Помогает ли это? Запрос расстояния между MySQL Levenshtein

EDIT: устаревшая ссылка Леванштейн Расстояние как хранимая функция MySQL (Google Cache), благодаря Роберту, указав это на комментарий.

Ответ 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 ;