Czy istnieje sposób wyszukiwania bazy danych SQL dla podobnych słów (czyli nie identycznych słów)?

Question

Czy istnieje sposób wyszukiwania bazy danych MySQL dla podobnych słów (nie oznacza to samo słowo). Na przykład: użytkownik wyszukuje w bazie danych słowo "abcd" i jest słowo "abd" w bazie danych, więc wyszukiwarka lub program Zapytaj użytkownika "Czy masz na myśli [abd]?" Jak w większości wyszukiwarek w sieć? Proszę zauważyć, że słowo wyszukiwania nie jest częścią istniejącego słowa (nie można używać „jak”)

Answer 1

Zobacz algorytm Damerau-Levenshtein distance. Oblicza "odległość" między dwoma ciągami i określa, ile kroków zajmuje przekształcenie jednego ciągu w drugi. Im mniej kroków, tym bliżej są dwa łańcuchy.

This Artykuł przedstawia algorytm zaimplementowany jako funkcja przechowywana w MySQL.

Algorytm jest o wiele lepszy niż LIKE lub SOUNDEX.

Wierzę, że Google korzysta z danych pochodzących z tłumu, a nie z algorytmu. tzn. jeśli użytkownik wpisze abcd, kliknie przycisk "Wstecz", a następnie od razu przeszuka abd, ustali związek między dwoma wyszukiwanymi terminami, ponieważ użytkownik nie był zadowolony z wyników. Gdy masz bardzo duże wyszukiwanie w społeczności, pojawia się wzorzec.

Answer 2

Zależy jak daleko od siebie są, można spojrzeć na soundex być może ..

http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#function_soundex

Answer 3

Wymień Levenshtein_distance

Answer 4

Inną techniką jest tworzenie indeksów na trigrams.

Answer 5

Ponieważ ogniwo w odpowiedzi Dave Barkera jest martwy, oto kod z an archived version of the website:

CREATE FUNCTION LEVENSHTEIN (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; 
     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(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 

do uwaga:

• Maksymalna długość ciągów wejściowych wynosi 255 znaków. Jestem pewien, że możesz edytować tę funkcję, aby w razie potrzeby obsługiwać więcej.

• Przetestowałem to z międzynarodowymi znakami na kolumnie utf8_bin i wydawało się, że działa, ale nie testowałem tej możliwości w trybie ekstensywnym.

• Testowałem go tylko na MySQL 5.0+. Nie mam pojęcia, jak to będzie działać w wersjach mniejszych.

A jako bonus I stworzył również funkcję pomocniczą, która zwraca wskaźnik (w procentach) różnych: samych znaków, które mogą być bardziej pomocny niż tylko prostej edycji odległości (Idea stąd).

CREATE FUNCTION LEVENSHTEIN_RATIO (s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    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