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

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

44 голосов
/ 11 марта 2009

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

Данные: 

O'Brien
Smithe
Dolan
Smuth
Wong
Smoth
Gunther
Smiht

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

Ответы [ 9 ]

11 голосов
/ 13 марта 2009

Для эффективного поиска с использованием расстояния Левенштейна необходим эффективный специализированный индекс, такой как bk-tree . К сожалению, ни одна система баз данных, о которой я знаю, включая MySQL, не реализует индексы bk-tree. Это еще более усложняется, если вы ищете полнотекстовый поиск, а не только один термин в строке. Я не могу придумать, каким образом вы могли бы выполнить полнотекстовое индексирование таким образом, чтобы можно было осуществлять поиск на основе расстояния Левенштейна.

7 голосов
/ 12 ноября 2013

Существует mysql UDF реализация функции расстояния Левенштейна

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

Он реализован на C и имеет лучшую производительность, чем «запрос расстояния MySQL Левенштейна», упомянутый schnaader

5 голосов
/ 13 марта 2009

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

4 голосов
/ 03 августа 2014

Функция, заданная для levenshtein <= 1 выше, неверна - она ​​дает неверные результаты, например, "кровать" и "ставка". </p>

Я изменил приведенный выше «запрос расстояния MySQL Левенштейна» в первом ответе, чтобы принять «предел», который немного ускорит его. По сути, если вас волнует только Левенштейн <= 1, установите ограничение на «2», и функция вернет точное расстояние Левенштейна, если оно равно 0 или 1; или 2, если точное расстояние Левенштейна равно 2 или больше. </p>

Этот мод делает это на 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$$
3 голосов
/ 30 апреля 2011

Вы можете использовать эту функцию 


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
2 голосов
/ 01 июля 2014

Если вы хотите знать только, является ли расстояние Левенштейна не более 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.

Поскольку эта функция не полностью вычисляет расстояние Левенштейна, она работает намного быстрее.

Вы также можете изменить эту функцию таким образом, чтобы она возвращала true, если расстояние Левенштейна не более 2 или 3, вызывая ее self рекурсивно. Если MySQL не поддерживает рекурсивные вызовы, вы можете дважды скопировать слегка измененные версии этой функции и вызвать их вместо этого. Но вы не должны использовать рекурсивную функцию для вычисления точного расстояния Левенштейна.

2 голосов
/ 03 мая 2009

Я настраиваю поиск на основе Левенштейна или Дамерау-Левенштейна (возможно, последнего) для множественных поисков по проиндексированному тексту на основе статьи Гонсало Наварро и Рикардо Баеза-йатса: текст ссылки

После построения массива суффиксов ( см. Википедию ), если вас интересует строка, содержащая не более k несовпадений в строке поиска, разбейте строку поиска на k + 1 кусочки; по крайней мере один из них должен быть неповрежденным. Найдите подстроки с помощью бинарного поиска по массиву суффиксов, затем примените функцию расстояния к патчу вокруг каждого совпадающего фрагмента.

0 голосов
/ 10 мая 2017

На основании ответа Челлы и статьи Райана Гинстрома , нечеткий поиск может быть реализован так: 

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 ;
0 голосов
/ 16 апреля 2012

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

  • У меня очень ограниченное пространство поиска (строка из 9 символов ограничена числовыми значениями).

Создайте новую таблицу (или добавьте столбцы к целевой таблице) со столбцами для каждой позиции символа в целевом поле. то есть. Мой VARCHAR (9) закончился как 9 столбцов TINYINT + 1 столбец Id, который соответствует моей основной таблице (добавьте индексы для каждого столбца). Я добавил триггеры, чтобы эти новые столбцы всегда обновлялись при обновлении моей основной таблицы.

Для выполнения запроса по k-расстоянию используйте следующий предикат:

(Столбец1 = s [0]) + (Столбец2 = s [1]) + (Столбец3 = s [2]) + (Столбец4 = s [3]) + ...> = m

где s - строка поиска, а m - требуемое количество совпадающих символов (или m = 9 - d в моем случае, где d - максимальное расстояние, которое я хочу вернуть).

После тестирования я обнаружил, что запрос более 1 миллиона строк, который занимал в среднем 4,6 секунды, возвращал совпадающие идентификаторы менее чем за секунду. Второй запрос на возврат данных для совпадающих строк в моей основной таблице также занял менее секунды. (Объединение этих двух запросов в качестве подзапроса или объединения привело к значительному увеличению времени выполнения, и я не уверен, почему.)

Хотя это не Дамерау-Левенштейн (не учитывается замена), этого достаточно для моих целей.

Хотя это решение, вероятно, плохо масштабируется для большего (длинного) пространства поиска, оно очень хорошо сработало для этого ограничительного случая.

...