Aplikacje internetowe

Bełdziowe spojrzenie na aplikacje internetowe

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: , , ,
Kategoria: Inne, PHP


13 komentarzy

  1. 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?

  2. nie, ponieważ szukamy słów, które zawierają dokładnie takie same n-gramy, jak podane przez użytkownika słowo :)

  3. No, ok, a masz jakiś pomysł jak zaadapować to w wyszukiwarce na LIKE (wiem, wiem, herezje i FULL-TEXT lepszy, ale…)

  4. nie do końca wiem o co chodz, opisz bardziej problem

  5. 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

  6. To nic z LIKE tu nie robisz. Musisz wygenerować n-gramy dla nazwisk wszystkich lekarzy i korzystasz z powyższego kodu.

  7. 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…

  8. cóż na tym to polega, że generuje się duży zestaw danych :-)

  9. i płaci za drogi serwer ;)

  10. oj tam :) milion n-gramow + słówa to jakieś 40 MB tak więc bez przesady :P

  11. no, może i tak, ale to i tak duże obciążenie :P

  12. Sebastian napisał(a):

    Mozna tez napisac procedure, ktora uzywa http://www.artfulsoftware.com/infotree/queries.php?&bw=1400#552

  13. Dzieki za dobry tekst, a takze za komentarze, tez mialem podobne pytanie, a tu w komentarzach wszystko ;-) pozdrawiam!

Dodaj komentarz