Princip jednoduchého fulltextu s příklady v SQL a PHP (2)

Pravostranné rozšíření

Řekněme, že část rejstříku obsahuje tato slova:

malina
malinkatá
malinkatý
malinká
malinký
malinová
malinový

Již víme, jak bychom vyhledali všechny dokumenty obsahující slovo malina. Co kdybychom ale chtěli články, kde se vyskytuje jakékoliv slovo začínající na malink? Obvyklou notací pro dotaz s pravostranným rozšířením je hvězdička: malink*. Záznamy odpovídající takovému dotazu dokážeme jednoduše najít ve slovníku:

SELECT *
FROM FT_Word
WHERE Word >= 'malink' AND Word < 'malinl';

vrátí

 idword |   word
--------+-----------
      7 | malinkatá
      8 | malinkatý
      9 | malinká
     10 | malinký
(4 rows)

Vycházíme přitom z faktu, že všechna slova začínající na malink jsou v lexikografickém uspořádání mezi samotným řetězcem malink a případným slovem začínajícím na malinl. Dolní hranici pro vyhledávání získáme prostým odtržením hvězdičky z konce řetězce. Pro získání horní hranice odtrhneme ještě jeden znak a nahradíme ho znakem v abecedě následujícím. Pokud uvažujeme jednobajtové kódování řetězců, postačí nám dokonce přičíst k ASCII hodnotě posledního znaku jedničku. I když se v případě češtiny může stát, že výsledkem je netisknutelný znak, databáze si s tím poradí.

Následuje příklad kódu v PHP, který zkonstruuje řetězec představující horní hranici vyhledávání (kód neobsahuje kontrolu chyb – selže například, když bude mít poslední znak ASCII hodnotu 255):

$dh = 'malink';
$hh = substr($dh, 0, -1) . chr(ord(substr($dh, -1)) + 1);

Celý SQL dotaz po získání dolní a horní hranice pak vypadá následovně (malink*):

SELECT I.IdArticle
FROM FT_Word W, FT_Index I
WHERE W.IdWord = I.IdWord
  AND W.Word >= 'malink' AND W.Word < 'malinl';

Dotazy bez diakritiky

Přidání dalších funkcí do vyhledávače je podmíněno rozšířením invertovaného souboru o potřebné informace. Představme si vyhledávání v komentářích článků, kde se střídají příspěvky s diakritikou a bez diakritiky. V takovém případě je prospěšné umožnit i zadávání dotazů bez háčků a čárek. Mohli bychom to vyřešit vygenerováním dalšího kompletního indexu bez diakritiky. Postačí však rozšíření stávajícího slovníku:

ALTER TABLE FT_Word ADD WordND VARCHAR(50) NULL;

UPDATE FT_Word SET WordND = to_ascii(Word, 'iso_8859_2');

ALTER TABLE FT_Word ALTER COLUMN WordND SET NOT NULL;

CREATE INDEX FT_Word_WordND_IX ON FT_Word (WordND);

Založili jsme ve slovníku nový sloupeček, ve kterém budeme uchovávat podobu slova bez diakritiky. Pokud již máme slovník naplněný, můžeme hodnoty sloupečku jednorázově nastavit pomocí funkcí, které máme k dispozici v použité databázi. Uvedený příklad je pro PostgreSQL. Příslušným způsobem je třeba upravit algoritmus generování rejstříku. Pro rychlé vyhledávání je nad sloupečkem definován index, ale již není unikátní, protože dvě různá slova s diakritikou mohou bez háčků a čárek vypadat stejně.

SELECT I.IdArticle
FROM FT_Word W, FT_Index I
WHERE W.IdWord = I.IdWord
  AND W.WordND = 'cep';

Tento SQL kód nyní vrátí identifikátory článků, kde se vyskytuje slovo cep, stejně jako těch, které obsahují termín čep.

Řazení výsledků podle relevance

Dosud vytvořené řešení má jeden zásadní nedostatek: neumožňuje nalezené výsledky seřadit podle relevance. Chceme-li toho dosáhnout, zajímá nás především, jak moc dané slovo charakterizuje obsah daného textu. Empiricky lze stanovit dvě jednoduchá vodítka. Slovo charakterizuje obsah textu tím více,

• čím vícekrát se v textu objeví a
• čím dříve se v textu objeví.

Oba dva tyto údaje můžeme uložit v invertovaném souboru jednoduchou úpravou tabulky FT_Index. Přidáme sloupeček, do kterého uložíme pozici daného slova v článku a zahrneme ho do primárního klíče. Tím pádem budeme mít uložen i počet slov v článku, protože pro každou pozici stejného slova bude v tabulce jeden záznam. Tato změna současně vyžaduje úpravu tokenizátoru, který musí nový sloupeček plnit.

CREATE TABLE FT_Index (
  IdWord INTEGER NOT NULL,
  IdArticle INTEGER NOT NULL,
  WordPosition INTEGER NOT NULL,
  PRIMARY KEY (IdWord, IdArticle, WordPosition)
);

ALTER TABLE FT_Index ADD FOREIGN KEY (IdWord) REFERENCES FT_Word (IdWord);
ALTER TABLE FT_Index ADD FOREIGN KEY (IdArticle) REFERENCES Article (IdArticle);

Nově získaná data můžeme pro nejjednodušší jednoslovný dotaz využít třeba takto:

SELECT I.IdArticle, COUNT(*), MIN(WordPosition)
FROM FT_Word W, FT_Index I
WHERE W.IdWord = I.IdWord
  AND W.Word = 'jahoda'
GROUP BY I.IdArticle
ORDER BY COUNT(*) DESC, MIN(WordPosition);

Jako kritérium relevance byl zvolen v první řadě počet výskytů hledaného slova v článku a sekundárním kritériem je pořadí prvního výskytu slova. Vyhledávání více slov bude poněkud složitější. Takhle vypadá dotaz na alespoň jedno lesní ovoce (jahoda OR borůvka OR malina):

SELECT IdArticle, COUNT(IdWord), SUM(WordCount), AVG(WordPos)
FROM (
  SELECT I.IdArticle, I.IdWord,
         COUNT(*) AS WordCount, MIN(WordPosition) AS WordPos
  FROM FT_Word W, FT_Index I
  WHERE W.IdWord = I.IdWord
    AND W.Word IN ('jahoda', 'borůvka', 'malina')
  GROUP BY I.IdArticle, I.IdWord
) ArtWord
GROUP BY IdArticle
ORDER BY COUNT(IdWord) DESC, SUM(WordCount) DESC, AVG(WordPos);

Vypomohli jsme si vnořeným dotazem. Kód vnitřního dotazu vypadá podobně jako SQL pro vyhledávání jednoho slova. Přibylo však třídění podle sloupečku IdWord, abychom rozlišili počty a první pozice pro každou kombinaci článku a slova. Vnější dotaz provádí další agregaci a nalezené články řadí primárně podle počtu unikátních slov z dotazu, která obsahují, pak podle celkového počtu slov z dotazu a nakonec podle průměru pozice prvního výskytu. Toto řazení je pouze příklad. Na základě dostupných informací lze vytvořit jakákoliv jiná pravidla řazení podle potřeby (obecně funkci, která vrací hodnotu představující relevanci na základě argumentů, kterými jsou jednotlivé údaje zjistitelné z invertovaného souboru).

SQL kód pro dotaz na dokumenty zmiňující všechny druhy ovoce získáme opět přidáním klauzule HAVING (jahoda AND borůvka AND malina).

SELECT IdArticle, COUNT(IdWord), SUM(WordCount), AVG(WordPos)
FROM (
  SELECT I.IdArticle, I.IdWord,
         COUNT(*) AS WordCount, MIN(WordPosition) AS WordPos
  FROM FT_Word W, FT_Index I
  WHERE W.IdWord = I.IdWord
    AND W.Word IN ('jahoda', 'borůvka', 'malina')
  GROUP BY I.IdArticle, I.IdWord
) ArtWord
GROUP BY IdArticle
HAVING COUNT(IdWord) = 3
ORDER BY COUNT(IdWord) DESC, SUM(WordCount) DESC, AVG(WordPos);

Nakonec si ukažme ještě letmý nástin, jak využít informace o pozici slova v článku k vyhledávání frází. Následující SQL kód vyhledává články, v nichž slovo banán následuje přímo za slovem jahoda („jahoda banán“):

SELECT Word1.IdArticle
FROM (
  SELECT I.IdArticle, WordPosition
  FROM FT_Word W, FT_Index I
  WHERE W.IdWord = I.IdWord
    AND W.Word = 'jahoda'
) Word1, (
  SELECT I.IdArticle, WordPosition
  FROM FT_Word W, FT_Index I
  WHERE W.IdWord = I.IdWord
    AND W.Word = 'banán'
) Word2
WHERE Word1.IdArticle = Word2.IdArticle
  AND Word2.WordPosition = Word1.WordPosition + 1;

Podobným způsobem bychom mohli realizovat fulltextový operátor NEAR.

Závěr

Reálná implementace popisovaného způsobu fulltextového vyhledávání rozhodně nemůže konkurovat komerčním vyhledávacím strojům. Praktické zkušenosti však ukazují, že poskytne relativně slušné vyhledávání v řádově tisícovkách dokumentů o celkovém objemu až desítek megabytů textu (pro ilustraci slovník po zaindexování 5000 článků obsahoval cca 130000 slov a v indexu byly necelé 2000000 záznamů). Výhodou vlastního řešení je kromě poučení a zábavy jednoznačně možnost přizpůsobení dané oblasti. Podle skutečných požadavků lze upravit obsah invertovaného souboru a také použitelné dotazovací operátory. Nevýhodou je malý výkon oproti specializovaným vyhledávačům.

Kromě zvyšování výkonu by bylo možné dále zlepšovat kvalitu vyhledávání. Jednou z cest je využití algoritmu pro nalézání základních tvarů slov (první pád, infinitiv). Slova v invertovaném souboru by byla uložena v základním tvaru a do toho by byly převedeny i termíny z dotazu. Získanou nezávislost na tvaru slova v popsaném řešení částečně supluje pravostranné rozšíření.

V rozsáhlých databázích dokumentů nabývá velmi na důležitosti určování relevance a přednostní zobrazení dokumentů nejvíce relevantních k dotazu. Za tímto účelem se provádí statistická analýza textu a automaticky se identifikují klíčová slova. Používají se také různé matematické metody, kterými se vyhodnocuje podobnost dotazu a dokumentu.

Protože tento článek má být spíše inspirací než návodem, uveďme na závěr pár námětů k dalšímu přemýšlení.

• Jak zefektivnit navržený algoritmus generování invertovaného souboru?
• Jak by se dal sestavit dotaz, který po vytvoření fulltextového indexu automaticky objeví potenciální stop slova?
• Na čem závisí objem dat v invertovaném souboru? Jak tento objem zmenšit bez újmy na kvalitě vyhledávání?
• Jak byste realizovali levostranné rozšíření (*lina najde malina i kalina)?
• Jak byste implementovali dotazovací operátor NOT v kombinaci s řazením výsledků podle relevance?
• Lze na základě ukázkového SQL kódu odhadnout vliv různých dotazů na spotřebu systémových zdrojů při vykonání dotazu (například dotazy, které obsahují často se vyskytující slova versus dotazy s výjimečnými termíny)?

Odkazy

SQL skript s příklady použitými v článku
Dokumentace PostgreSQL
Dokumentace PHP