similar_text in MySQL 1 lipca 2010

Już dawno miałem napisać ten wpis ale jakoś nie wyszło. Ostatnio spotkałem się z problemem jak na poziomie bazy danych wyciągnąć podobne stringi (podobieństwo procentowe). Chodziło o sprawdzanie literówek. W PHP istnieje funkcja similar_text() i robi dokładnie to o co mi chodziło.

    similar_text( 'abrakadabra', 'kadabra', $p );
    echo $p; // 77.7777777778

Wonderfully! Tylko, że mnie potrzeba było pobrać wszystkie podobne dane (powiedzmy 80%) z bazy wobec wpisanego ciągu, więc skrajnym idiotyzmem byłoby pobieranie wszystkich rekordów i mielenie tego przez PHP. Chodzi o zapytanie w stylu:

      SELECT foo.id FROM foo WHERE SIMILAR( foo.name, 'jakis string' ) > 0.8

Oczywiście funkcja SIMILAR nie występuje w MySQL`u a więc trzeba napisać własną. Nigdy nie pisałem własnej funkcji/procedury składowej w MySQL`u więc była to dla mnie ciekawa lekcja. No dobra… nawet nie napisałem tej funkcji, zainstalowałem tylko to co podał mi wookieb na forum php.pl. Ogólnie similar_text korzysta z algorytmu Olivera, natomiast istnieje też coś takiego jak Odległość Levenshteina, którą zresztą ma odzwierciedlenie w PHP levenshtein(). Odległość Levenshteina oczywiście jak można przeczytać na wiki do której podałem linka, zwraca liczbę całkowitą – najmniejsza ilość zmian jakie należy wykonać na ciągu A, aby go zamienić w ciąg B. Ofc. można liczyć z tego procent:

    $word  	= 'kadabra';
    $word2 	= 'abrakadabra';
	$len1 = strlen( $word );
	$len2 = strlen( $word2 );
    $len = $len1 > $len2 ? $len1 : $len2; 
	
    $p = round(( 1 -levenshtein( $word, $word2 ) / $len ) * 100);
    echo $p; // 64

No i właśnie takie rozwiązanie zastosowałem tyle, że na bazie danych. Wykonanie jest w sumie banalne, wystarczy zainstalować (? nie wiem czy to dobre słowo) dwie funkcje i gotowe. Tworzymy plik 1.sql:

DELIMITER //

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

DELIMITER ;

oraz 2.sql

DELIMITER //

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

DELIMITER ;

Odpalamy konsole, logujemy się, nastepnie:

mysql> use foo;
mysql> source c:/1.sql;
mysql> source c:/2.sql;
mysql> SELECT LEVENSHTEIN_RATIO( 'abrakadabra', kadabra ); // 64 :)

to wszystko co musimy zrobić. Jeśli chodzi o optymalizację (przy tabelce z ~1000 rekordów działa to ~7 sek.) to można by okrajać mielony obszar z tych ~1000 rekordów. Jednym pomysłem jest ucinanie go do rekordów o tej samej literze (ludzie raczej nie popełniają literówki w pierwszym znaku).

SELECT 
    id, name, LEVENSHTEIN_RATIO( name, 'luq' ) AS similar
FROM (
    SELECT id, name
    FROM table
    WHERE SUBSTRING( name, 1, 1 ) = 'l'
) AS foo
HAVING similar > 80

Drugim pomysłem (który wysnuł wookieb) jest stworzenie w tabelce pole zawierającego długość stringa (żeby tego nie liczyć, bo wtedy to byłoby wolniejsze) i okrajać sobie zakres szukania do rekordów mających długość +/- np. 2 znaki.

To by było na tyle. Z tego miejsca, serdeczne dzięki wookieb!