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

• generowanie danych
• pobieranie danych