SQL, JSON i Ajax… czyli część 3. tworzenia mapy pod grę 7 lipca 2010

Dość długo zwlekałem z tym wpisem… szczerze mówiąc, bardzo dużo czasu i sił kosztuje mnie opisywanie mojego, hm… projektu, bo tak to można nazwać. Tak naprawdę więcej czasu spędziłem nad pisaniem poprzednich dwóch wpisów niż nad pisaniem kodu do nich. Sam nie jestem fanem tutoriali programistycznych i od dziś nie będę pisał na ten temat rozwodząc się nad moją każdą decyzją podjętą w czas projektowania tego wszystkiego. Będę zwracał uwagę na elementy ciekawe pomijając te błahe.

 

Okej, ostatnio zakończyliśmy na GUI pod edytor map, dziś dopiszemy trochę kodu aby nasz edytor zapisywać dane dt. mapy do bazy a także odczytywał stworzoną mapę po przeładowaniu strony tak, aby można było kontynuować prace nad całym naszym światem. Dodatkowo stworzymy kod który umożliwi nam w grze przesuwanie mapy. Szkoda czasu czas zaczynać.

 

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!