Implementarea distanței Levenshtein pentru căutarea mysql/fuzzy? (Programare, Mysql, Bază De Date, Algoritm, Căutare, Distanța Levenshtein)

Andrew Clark a intrebat.

Aș dori să pot căuta un tabel după cum urmează pentru smith ca să obțin tot ceea ce se află în cadrul 1 varianță.

Date:

O'Brien
Smithe
Dolan
Smuth
Wong
Smoth
Gunther
Smiht

M-am uitat în utilizarea distanței Levenshtein, știe cineva cum să implementeze acest lucru cu ea?

9 răspunsuri
Nick Johnson

Pentru a căuta în mod eficient folosind distanța levenshtein, aveți nevoie de un index eficient, specializat, cum ar fi un bk-tree. Din păcate, niciun sistem de baze de date pe care îl cunosc, inclusiv MySQL, nu implementează indici bk-tree. Acest lucru se complică și mai mult dacă doriți să căutați un text complet, în loc să căutați doar un singur termen pe rând. Pe scurt, nu mă pot gândi la nicio modalitate de indexare full-text care să permită căutarea pe baza distanței levenshtein.

Hongzheng

Există o implementare mysql UDF a funcției Distanța Levenshtein

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

Este implementată în C și are o performanță mai bună decât „interogarea distanței Levenshtein MySQL” menționată de schnaader

Comentarii

  • Este acest lucru suficient de rapid pentru utilizarea în timp real, atunci când căutați, să zicem, 200.000 de înregistrări? –  > Por srayner.
  • Nu sunt sigur ce înțelegeți prin timp real. Pe o cutie de testare cu două procesoare Intel(R) Xeon(R) CPU E5-2680 0 @ 2,70 GHz și 64G de memorie, următoarele interogări s-au terminat în 0,30 secunde. ‘select min(levenshtein(country, ‘GC’)) from countries;’. Tabelul countries are o coloană country de 2 caractere. Iar tabelul conține 1 milion de rânduri + –  > Por Hongzheng.
  • @Hongzheng este doar pe 2 litere încercați să faceți benchmarking cu numere mai mari – -.  > Por talsibony.
  • @talsibony de ce nu încerci tu însuți? –  > Por Pablo Pazos.
Ponk

O implementare pentru distanța damerau-levenshtein poate fi găsită aici:Algoritmul Damerau-Levenshtein: Levenshtein cu transpuneriÎmbunătățirea față de distanța Levenshtein pură constă în faptul că este luată în considerare și permutarea caracterelor. Am găsit-o în comentariile de la linkul lui Schnaader, mulțumesc!

Comentarii

  • Din păcate, acest lucru are ca rezultat faptul că este cu 10% mai lent. Am implementat totuși lungimea șirului, el propune să se folosească șirul la maxim sau mai mic, eu am implementat o comparație doar pe lungimea șirului +/- 1. –  > Por Andrew Clark.
stopthe

Funcția dată pentru levenshtein <= 1 de mai sus nu este corectă – dă rezultate incorecte pentru, de exemplu, „bed” și „bid”.

Am modificat „interogarea MySQL Levenshtein distance query” dată mai sus, în primul răspuns, pentru a accepta o „limită” care să o accelereze un pic. Practic, dacă vă interesează doar Levenshtein <= 1, setați limita la „2” și funcția va returna distanța levenshtein exactă dacă este 0 sau 1; sau un 2 dacă distanța levenshtein exactă este 2 sau mai mare.

Această modificare face ca funcția să fie cu 15% până la 50% mai rapidă – cu cât cuvântul căutat este mai lung, cu atât mai mare este avantajul (deoarece algoritmul poate renunța mai devreme.) De exemplu, în cazul unei căutări pe 200 000 de cuvinte pentru a găsi toate corespondențele aflate la distanța 1 față de cuvântul „giggle”, originalul durează 3 min 47 sec. pe laptopul meu, față de 1:39 pentru versiunea cu „limită”. Desigur, ambele sunt prea lente pentru a fi utilizate în timp real.

Cod:

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$$

Alaa

puteți utiliza această funcție

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

iar pentru a o obține în proporție de XX% folosiți această funcție

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

Comentarii

  • Scuze pentru întrebarea de noob, dar când copiez acest lucru într-un fișier text leven, și apoi rulează . leven, primesc mai multe erori de la MySQL 5: ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server... near '' at line 4. –  > Por max.
Hugh

Sunt în curs de a configura o căutare bazată pe Levenshtein sau Damerau-Levenshtein (probabil cea din urmă) pentru căutări multiple pe un text indexat, pe baza unei lucrări de Gonzalo Navarro și Ricardo Baeza-yates: link text

După construirea unui tablou de sufixe (a se vedea wikipedia), dacă vă interesează un șir cu cel mult k neconcordanțe cu șirul de căutare, rupeți șirul de căutare în k+1 bucăți; cel puțin una dintre acestea trebuie să fie intactă. Găsiți subșirurile prin căutare binară în matricea de sufixe, apoi aplicați funcția de distanță la zona din jurul fiecărei bucăți potrivite.

AbcAeffchen

Dacă doriți doar să știți dacă distanța levenshtein este cel mult 1, puteți utiliza următoarea funcție 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

Aceasta este practic un singur pas în descrierea recursivă a distanței levenshtein.Funcția returnează 1, dacă distanța este de cel mult 1, altfel returnează 0.

Deoarece această funcție nu calculează complet distanța levenshtein, este mult mai rapidă.

De asemenea, puteți modifica această funcție astfel încât să returneze true dacă distanța levenshtein este cel mult 2 sau 3, apelând-o în mod recursiv. În cazul în care MySQL nu acceptă apelurile recursive, puteți copia versiunile ușor modificate ale acestei funcții de două ori și le puteți apela în locul lor. Dar nu trebuie să utilizați funcția recursivă pentru a calcula distanța levenshtein exactă.

Comentarii

  • Vă referiți la cel puțin 1? –  > Por Mark Fisher.
  • @MarkFisher Nu. Aceasta returnează 1 (adevărat) dacă distanța este mai mică sau egală cu 1. –  > Por AbcAeffchen.
greg

Am avut un caz specializat de căutare a distanței k și, după instalarea UDF Damerau-Levenshtein în MySQL, am constatat că interogarea dura prea mult. Am găsit următoarea soluție:

  • Am un spațiu de căutare foarte restrictiv (șir de 9 caractere limitat la valori numerice).

Creați un tabel nou (sau adăugați coloane la tabelul țintă) cu coloane pentru fiecare poziție de caracter din câmpul țintă. De exemplu, VARCHAR(9) a ajuns să fie 9 coloane TINYINT + 1 coloană Id care se potrivește cu tabelul meu principal (adăugați indici pentru fiecare coloană). Am adăugat declanșatoare pentru a mă asigura că aceste noi coloane sunt actualizate întotdeauna atunci când tabelul meu principal este actualizat.

Pentru a efectua o interogare k-distance, utilizați următorul predicat:

(Column1=s[0]) + (Column2=s[1]) + (Column3=s[2]) + (Column4=s[3]) + … >= m

unde s este șirul de căutare și m este numărul necesar de caractere care corespund (sau m = 9 – d în cazul meu, unde d este distanța maximă pe care vreau să o obțin).

După testare, am constatat că o interogare de peste 1 milion de rânduri, care dura în medie 4,6 secunde, a returnat id-uri corespunzătoare în mai puțin de o secundă. O a doua interogare pentru a returna datele pentru rândurile corespunzătoare din tabelul meu principal a durat, în mod similar, mai puțin de o secundă. (Combinarea acestor două interogări sub forma unei subinterogări sau a unei îmbinări a dus la timpi de execuție semnificativ mai lungi și nu sunt sigur de ce).

Deși acest lucru nu este Damerau-Levenshtein (nu ține cont de substituție), este suficient pentru scopurile mele.

Deși această soluție probabil că nu se adaptează bine la un spațiu de căutare mai mare (lungime), a funcționat foarte bine în acest caz restrictiv.

D. Savina

Pe baza răspunsului lui Chella și al lui Ryan Ginstrom , o căutare fuzzy ar putea fi implementată astfel:

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 ;