Czy chodziło Ci o … – czyli n-gramy
Podczas tworzenia modułu wyszukiwarki dobrym zwyczajem jest stworzenia mechanizmu „Czy chodziło Ci o …” czyli modułu sprawdzającego i korygującego ewentualne błędy w słowach wpisanych przez użytkownika. W przypadku określonego zakresu słów obsługiwanego przez ową wyszukiwarkę możemy posłużyć się mechanizmem n-gramów. Jego opis można znaleźć np. na stronie Wikipedii (ang.), poniżej przykład demonstrujący idee działania.
Przykład działania
Tekst wejściowy: ala ma kota Otrzymane n-gramy: ala, la_, a_m, _ma, ma_, a_k, _ko, kot, ota (gdzie "_" reprezentuje spacje)
Jak widać wynikiem jest 9 kolejnych, trzyznakowych podciągów.
Ilość znaków tworzących podciągi jest wybierana przez osobę projektująca system. W naszym przypadku wybraliśmy następujące wartości:
- 2 znaki dla ciągów o maksymalnej długości 6 znaków,
- 4 znaki dla ciągów powyżej 8 znaków
- 3 znaki dla wszystkich ciągów
Z powyższej listy wynika, że dla słowa dlugieslowo zostaną wygenerowane n-gramy 3 oraz 4 znakowe.
Czas na trochę kodu.
Generowanie n-gramów
Zacznijmy od połączenia się z bazą danych oraz zdefiniowaniem słów, dla których chcemy wygenerować n-gramy.
mysql_connect( 'server', 'user', 'pass' ); mysql_select_db( 'db' ); $words = array( 'kosmos', 'polska', 'komputer', 'programista' );
Tabela, w której będziemy przechowywać n-gramy ma następującą strukturę:
CREATE TABLE IF NOT EXISTS `ngrams` ( `ngram` varchar(4) NOT NULL, `word` varchar(50) NOT NULL, PRIMARY KEY (`ngram`,`word`) ) ENGINE=MyISAM;
Teraz dla zadeklarowanych słów musimy wygenerować zestawy n-gramów, a następnie utworzyć z nich zapytanie SQL.
$query = 'INSERT INTO ngrams VALUES '; foreach( $words as $word ) { $ngrams = array( ); $length = strlen( $word ); if( $length <= 6 ) $ngrams = array_merge( $ngrams, getNGramArray( $word, 2 ) ); if( $length >= 8 ) $ngrams = array_merge( $ngrams, getNGramArray( $word, 4 ) ); $ngrams = array_merge( $ngrams, getNGramArray( $word, 3 ) ); foreach( $ngrams as $gram ) $query .= ' ( "'. $gram .'", "'. $word .'" ), '; } mysql_query( $query );
Funkcja generująca tablicę n-gramów wygląda następująco:
function getNGramArray( $string, $qua ) { $to = strlen( $string ) - $qua; for( $i = 0; $i <= $to; $i++ ) $ngrams[ ] = substr( $string, $i, $qua ); return array_unique( $ngrams ); }
Powyższy kod zadba o wygenerowanie n-gramów dla podanych przez nas słów. Teraz zajmijmy się ich wyciąganiem na podstawie danych przekazanych przez użytkownika.
Wyciąganie danych
Kod wyszukiwania słów na podstawie danych przekazanych od użytkownika niewiele różni się od kodu z powyższego punktu. Tak jak poprzednio musimy wygenerować tablice n-gramów dla podanego słowa, a następnie zbudować z niej zapytanie SQL. Zadaniem owego zapytania jest pobranie z bazy słów, których budowa podobna jest do słowa podanego przez użytkownika.
$query = mysql_query( 'SELECT word, COUNT( ngram ) AS d FROM ngrams WHERE ('. $ngramString .' ) AND LENGTH( word ) BETWEEN '. ( $length - 2 ) .' AND '. ( $length + 2 ) .' GROUP BY word ORDER BY d DESC' ); while( $row = mysql_fetch_array( $query, MYSQL_ASSOC ) ) { if ( $row[ 'lvl' ] = levenshtein( $word, $row[ 'word' ] ) > 3 ) continue; $words[ ] = $row; }
W powyższym kodzie pobieramy z bazy słowa, które mają minimum jeden wspólny n-gram ze słowem podanym przez użytkownika, a do tego ich długość jest równa długości słowa podanego przez użytkownika ± 2 znaki. Dzięki temu wyeliminujemy słowa będące za długie / za krótkie w stosunku do słowa szukanego.
Dodatkowo w pętli możemy przeprowadzić dodatkowe operacje mające na celu wytypowanie najtrafniejszych wyników. W powyższym przykładzie obliczamy odległość Levenshteina, która mówi nam ile znaków trzeba przestawić aby wyraz pobrany z bazy oraz wyraz podany przez użytkownika były takie same. Jeśli odległość ta jest większa niż trzy znaki pomijamy dane słowo.
Poniżej pliki z całością kodu
Tagi: czy chodziło Ci o, did you mean, n-gram, ngrams
Kategoria: Inne, PHP
Jesteś zajebisty po prostu :)
Tylko jedno malutkie pytanie, bo nie jestem pewien…
Jak masz
foreach( $ngrams as $gram )
$ngramString .= ‚ ngram = „‚. $gram .'” OR’;
To czy tu nei powinno być LIKE?
nie, ponieważ szukamy słów, które zawierają dokładnie takie same n-gramy, jak podane przez użytkownika słowo :)
No, ok, a masz jakiś pomysł jak zaadapować to w wyszukiwarce na LIKE (wiem, wiem, herezje i FULL-TEXT lepszy, ale…)
nie do końca wiem o co chodz, opisz bardziej problem
Powiedzmy że mam baze danych z wypisanymi lekarzami:
Jan Kowalski | Kardiochirurg
Bronisław Miodek | Okulista
i chcę na podstawie nazwy, znaleźć Miodka, po wpisaniu Moidek
To nic z LIKE tu nie robisz. Musisz wygenerować n-gramy dla nazwisk wszystkich lekarzy i korzystasz z powyższego kodu.
ok, ok, ale popatrz, co jeśli tych rekordów mam z milion, no albo chociażby nawet 1000? To staje się pamięcio żerne…
cóż na tym to polega, że generuje się duży zestaw danych :-)
i płaci za drogi serwer ;)
oj tam :) milion n-gramow + słówa to jakieś 40 MB tak więc bez przesady :P
no, może i tak, ale to i tak duże obciążenie :P
Mozna tez napisac procedure, ktora uzywa http://www.artfulsoftware.com/infotree/queries.php?&bw=1400#552
Dzieki za dobry tekst, a takze za komentarze, tez mialem podobne pytanie, a tu w komentarzach wszystko ;-) pozdrawiam!