Princip fulltextu
Základní princip fulltextového (či plnotextového) vyhledávání lze snadno pochopit pomocí analogie s běžnou odbornou knihou, která obsahuje rejstřík. Představme si tlustou knihu o programování v unixových systémech a úkol najít všechny zmínky o procesech. Jednou z možností je čtení od první do poslední stránky. Byla by to však nejspíš práce na několik dní. Daleko rychleji budeme hotovi, když se podíváme do rejstříku, ve kterém je požadovaná informace uložena přesně ve tvaru, v jakém ji potřebujeme:
... počítač, 3, 115, 220 proces, 22, 99, 131, 158, 205 ps, 99, 132, 135 ...
První informaci o procesech najdeme na stránce 22. Převedeme-li knižní analogii na vyhledávání v článcích webového magazínu, zajímá nás v nejjednodušším případě množina článků, ve kterých je obsaženo určité slovo či slova. Způsob uložení dokumentů není podstatný, pokud jsou opatřeny unikátním identifikátorem, což může být třeba i URL. Pro účely tohoto článku předpokládejme, že články jsou uloženy v relační databázi v tabulce Article, jejíž zkrácená definice vypadá takto:
CREATE TABLE Article ( IdArticle INTEGER NOT NULL, ArticleText TEXT NOT NULL, PRIMARY KEY (IdArticle) );
I když bychom mohli zvolit jiné řešení, budeme v databázi uchovávat také rejstřík. Díky tomu bude možné ukázat logiku fulltextového vyhledávače ve vysokoúrovňovém jazyce SQL a ignorovat implementační složitost nepodstatnou pro základní princip vyhledávání.
Rejstřík můžeme rozdělit na dvě části. V první řadě je to abecední seznam slov (čili slovník). Ke každému slovu pak můžeme přiřadit seznam článků, ve kterých se nachází. Soubor seřazených slov se seznamem dokumentů, v nichž se vyskytují, a případně s dalšími doplňujícími informacemi, se označuje jako invertovaný soubor nebo fulltextový index.
Invertovaný soubor zrealizujeme dvěma tabulkami. Tabulku pro slovník nazveme FT_Word (předpona identifikuje tabulky použité pro fulltext). V nejjednodušším případě postačí následující definice:
CREATE TABLE FT_Word ( IdWord INTEGER NOT NULL, Word VARCHAR(50), PRIMARY KEY (IdWord) ); CREATE UNIQUE INDEX FT_Word_Word_IX ON FT_Word (Word);
Unikátní index zaručuje, že každé slovo bude ve slovníku obsaženo pouze jednou, a také poslouží databázovému stroji k rychlému prohledávání tabulky. Seznam článků obsahujících dané slovo ve slovníku je realizován vazební tabulkou mezi tabulkami FT_Word a Article:
CREATE TABLE FT_Index ( IdWord INTEGER NOT NULL, IdArticle INTEGER NOT NULL, PRIMARY KEY (IdWord, IdArticle) ); ALTER TABLE FT_Index ADD FOREIGN KEY (IdWord) REFERENCES FT_Word (IdWord); ALTER TABLE FT_Index ADD FOREIGN KEY (IdArticle) REFERENCES Article (IdArticle);
Vytvoření invertovaného souboru
Stejně jako v případě knihy můžeme i v databázi vyhledávat sekvenčně stránku po stránce nebo dokument po dokumentu. V naší malé databázi například tímto dotazem:
SELECT IdArticle FROM Article WHERE ArticleText LIKE '%proces%';
Efektivita je však z hlediska spotřeby zdrojů počítače obdobně nízká jako efektivita člověka hledajícího termín listováním v knize. Na druhé straně tato metoda funguje bez předchozí přípravy. Naopak než budeme moci využít fulltextového vyhledávání, musíme nejdříve vygenerovat fulltextový index (čili naplnit tabulky FT_Word a FT_Index). Indexováním textu dochází k optimalizaci, protože náročné sekvenční procházení textu se provede pouze jednou. Často opakované vlastní vyhledávání pracuje s vhodně uspořádanými daty a trvá jen zlomek času.
Algoritmus vytváření invertovaného souboru lze popsat zhruba takto:
Pro každý článek {
Rozděl článek na slova
Pro každé slovo {
Když je slovo ve slovníku
Získej Id slova
Jinak
Vlož slovo do slovníku
Získej Id slova
Vlož do vazební tabulky záznam s Id slova a Id článku
}
}
Přesun části logiky do okamžiku, než bude položen první dotaz, vede k tomu, že vyhledávání bude napříště jen tak kvalitní, jak kvalitní bude obsah invertovaného souboru. Vrátíme-li se k příkladu s knihou, je pravděpodobné, že v rejstříku nebudou úplně všechny stránky, kde se vybrané slovo vyskytuje. Záměrně jsou vynechány stránky, kde je termín zmíněn pouze v okrajové souvislosti. V rejstříku také nebudou všechna slova, která jsou součástí textu knihy. Slůvko nebo se pravděpodobně vyskytuje téměř na každé stránce, nemá proto žádný smysl ho zařazovat do rejstříku. Slovům s malou schopností popsat informaci, po které se pídíme, jako jsou předložky, spojky a v angličtině třeba členy, se říká stop slova. Seznam stop slov může být součástí implementace výše uvedeného algoritmu. Pokud je právě zpracovávané slovo v seznamu stop slov, bude ignorováno. Některé systémy pro zjednodušení pokládají za stop slova všechna slova s počtem písmen menším než určitá hranice.
Položme si ještě jednu na první pohled jednoduchou otázku: co vlastně budeme považovat za slovo? Algoritmus, který vytváří invertovaný soubor, dostává na vstupu souvislý text. Předpokládejme, že se jedná o čistý text a ne třeba o HTML. Mohli bychom tedy říct, že slovo je souvislý řetězec určitých znaků (písmen a číslic) a hranice slov určují jiné znaky (mezery, interpunkční znaménka a jiné oddělovače). Takovému jednoduchému rozdělení textu pomocí oddělovačů se říká tokenizace a většina programovacích jazyků má ve standardní knihovně funkci, která odvede většinu potřebné práce za nás. V PHP se podobně jako v jazyce C používá funkce s názvemstrtok. Její použití ilustruje následující fragment kódu:
$text = "Kočka leze dírou (pes oknem), nebude-li pršet, nezmoknem.";
$delimiters = " \r\n\t.:!?,;-_'\"*/+=@()[]{}<>";
$token = strtok($text, $delimiters);
while ($token !== false) {
printf("%s\n", strtolower($token));
$token = strtok($delimiters);
}
Po spuštění kódu v interpretu PHP uvidíme na jednotlivých řádcích slova: kočka, leze, dírou, pes,oknem, nebude, li, pršet a nezmoknem. Všechna slova jsou zkonvertována do malých písmen pomocí funkce strtolower.
Co kdyby se v textu vyskytovalo třeba URL? Pokud přiřadíme do proměnné
$text řetězec http://www.insula.cz/dali/index.php?cnt=2, získáme postupně tokeny http, www, insula, cz, dali, index, php, cnt,
2. To nám vlastně nevadí, protože později uživateli postačí zadat některou část tohoto URL, aby našel dokumenty, kde se adresa vyskytuje. Problémy by nastaly, kdyby pilně zadal URL kompletní. Obecně proto platí, že dotaz uživatele bychom měli zpracovat stejným tokenizačním algoritmem jako indexované texty (a to včetně vyřazení stop slov).Kostra triviálního algoritmu pro generování rejstříku by v PHP mohla vypadat zhruba následovně:
function index_text($dbid, $idarticle, $text) {
// Seznam stop slov je třeba doplnit
static $stopwords = array('a' => true, 'i' => true, 'nebo' => true);
// Oddělovače
static $delimiters = " \r\n\t.:!?,;-_'\"*/+=@()[]{}<>";
// Slova, která už jsou jednou u článku zaznamenána, nadále ignorujeme
$wordsseen = array();
$token = strtok($text, $delimiters);
while ($token !== false) {
$token = strtolower($token);
if (!$stopwords[$token] && !$wordsseen[$token]) {
$wordsseen[$token] = true;
// Vyhledat slovo ve slovníku
$rsid = pg_query($dbid,
"SELECT IdWord FROM FT_Word WHERE Word = '$token'"
);
if ($rsid && pg_num_rows($rsid) > 0)
$idword = pg_fetch_result($rsid, 0, 0);
else {
// Když slovo ještě není ve slovníku, vlož záznam s id ze sekvence
$rsid = pg_query($dbid,
"SELECT nextval('FT_Word_IdWord_SEQ')"
);
// ... zde chybí ošetření chybového stavu
$idword = pg_fetch_result($rsid, 0, 0);
$rsid = pg_query($dbid,
"INSERT INTO FT_Word VALUES($idword, '$token')"
);
// ... zde chybí ošetření chybového stavu
}
// Zápis do indexu
$rsid = pg_query($dbid,
"INSERT INTO FT_Index VALUES($idword, $idarticle)"
);
// ... zde chybí ošetření chybového stavu
printf("%s\n", $token);
}
$token = strtok($delimiters);
}
}
Argumenty načrtnuté procedury jsou deskriptor spojení s databází, identifikátor indexovaného článku a jeho text. Před reálným nasazením by bylo nutné minimálně doplnit chybějící ošetření chybových stavů a vhodně zapouzdřit databázová volání do transakcí, abychom se vyhnuli nekonzistentnímu stavu dat po případné chybě (zaindexování poloviny článku apod.). Uvedený algoritmus rozhodně není optimalizován na výkon – cílem byla jeho snadná pochopitelnost. Připomeňme nicméně, že pro dávkové generování fulltextového indexu není rychlost tak důležitá jako v případě vlastního provádění dotazu.
Obsah invertovaného souboru je pochopitelně třeba aktualizovat vždy po změně v tabulce článků. Přidání článku lze vyřešit prostým voláním indexační procedury s příslušnými parametry. Smazání článku by mělo být provázeno smazáním záznamů v tabulce FT_Index, které se k němu vztahují:
DELETE FROM FT_Index WHERE IdArticle = 10;
Tento příkaz zruší index pro článek s primárním klíčem 10. Slovník můžeme ponechat beze změn. Nejsnazší cestou k promítnutí modifikace textu článku do fulltextového indexu je smazání záznamů v tabulceFT_Index následované voláním indexovací procedury.
Základní dotazy
S aktuálním rejstříkem se konečně můžeme pustit do vyhledávání. Nejzákladnějším požadavkem je zjistit všechny články obsahující dané slovo. Hledejme například slovo jahoda. Výstupem bude seznam identifikátorů článků, které se o jahodě zmiňují (nevýhodu tohoto způsobu pro češtinu je pokrytí pouze toho tvaru slova, který se vyskytuje v dotazu – později si ukážeme jeden způsob, jak toto omezení překonat):
SELECT I.IdArticle FROM FT_Word W, FT_Index I WHERE W.IdWord = I.IdWord AND W.Word = 'jahoda';
Pokud bychom chtěli hledat články, kde se vyskytuje aspoň nějaké lesní ovoce, mohli bychom postupovat takto (jahoda OR borůvka OR malina):
SELECT I.IdArticle, COUNT(*)
FROM FT_Word W, FT_Index I
WHERE W.IdWord = I.IdWord
AND W.Word IN ('jahoda', 'borůvka', 'malina')
GROUP BY I.IdArticle;
Kdybychom místo operátoru = pouze použili operátor IN, mohlo by se stát, že se ve výsledku objeví články víckrát, jestliže by obsahovaly více hledaných slov zároveň. Tuto situaci ošetříme pomocí klauzule GROUP BY a jako bonus získáme informaci o počtu hledaných slov, která jsou v daném článku zmíněna. Můžeme také chtít vyhledávat dokumenty se všemi jmenovanými plody najednou. To znamená, že počet hledaných slov, která prohledávaný text obsahuje, se rovná celkovému počtu slov v dotazu. Výsledek získáme jednoduchou úpravou předchozího SQL kódu (jahoda AND borůvka AND malina):
SELECT I.IdArticle, COUNT(*)
FROM FT_Word W, FT_Index I
WHERE W.IdWord = I.IdWord
AND W.Word IN ('jahoda', 'borůvka', 'malina')
GROUP BY I.IdArticle
HAVING COUNT(*) = 3;
Klauzule HAVING omezuje výsledek jen na ty články, které zmiňují všechny tři druhy ovoce. Tím jsme realizovali dva základní operátory fulltextového vyhledávání OR a AND. Dynamické generování SQL kódu by pokrylo i kombinaci obou operátorů v jednom dotazu, složitost takového řešení je ale již nad rámec tohoto článku. Podívejme se ještě na případ, kdy bychom měli chuť na jahody, ale ne na borůvky (jahoda AND NOT borůvka):
SELECT I.IdArticle FROM FT_Word W, FT_Index I WHERE W.IdWord = I.IdWord AND W.Word = 'jahoda' AND I.IdArticle NOT IN ( SELECT I.IdArticle FROM FT_Word W, FT_Index I WHERE W.IdWord = I.IdWord AND W.Word = 'borůvka' );
K základnímu dotazu, který hledá slovo jahoda, zde přibyl poddotaz, který hledá slovo borůvka, a články s borůvkami jsou vyloučeny z množiny článků s jahodami.
Nyní umíme zajistit vyhledávání s použitím základních operátorů. Příště si ukážeme, jak hledat slova v jiných tvarech, řadit výsledky podle relevance a vyhledávat fráze.
ČLÁNKY DO MAILU