Hlavní navigace

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

Dalibor Šrámek 8. 2. 2005

Jak jsme viděli minule, i s velmi jednoduchým fulltextovým indexem dokážeme provést dotazy obsahující většinu používaných operátorů. Tento index umožňuje dokonce implementovat i jednu pokročilejší vlastnost - takzvané pravostranné rozšíření.

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 malinakalina)?
  • 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

Našli jste v článku chybu?

8. 2. 2005 2:05

Jejda...kdyby to tak fungovalo i nad takovymi 50-100 GB dat, to bych to mohl pouzit taky :)

Ad levostranne doplneni: Muzu pouzit SQL wildcards: "LIKE '%lina'". Problem je s indexy, ze...pokud bych potreboval urychlit hledani indexem s zolikem na zacatku, musel bych si ukladat i rotovane slovo. Nicmene pokud rezie zpracovani tabulky slov je dostatecne mala oproti zpracovani tabulky vyskytu, nebude to tak kriticke. (Jeste ze muzeme pracovat ve vazebni tabulce slova<->clank…

14. 2. 2005 8:33

Fulltext s převáděním českých slov na základní tvar podle slovníku a podporou synonym poskytuje například modul tsearch2 do PostgreSQL - viz tady na Rootu http://www.root.cz/clanky/fulltextovani-v-postgresql-modul-tsearch2/
S tou implementací bych to tak složitě neviděl. Když jsem kód ukázkový kód pro článek testoval, vytvořil jsem indexátor dopsáním méně než 10 řádků v PHP. Konstrukce dotazů pro nejjednodušší případy všechna slova v dotazu OR nebo všechna AND nejspíš nezabere o moc větší počet.
Lupa.cz: E-shopy: jen sleva už nestačí

E-shopy: jen sleva už nestačí

Vitalia.cz: Žloutenka v Brně: Nakaženo bylo 400 lidí

Žloutenka v Brně: Nakaženo bylo 400 lidí

Vitalia.cz: Jak koupit Mikuláše a nenaletět

Jak koupit Mikuláše a nenaletět

Podnikatel.cz: Platební brány a EET? Stále s otazníkem

Platební brány a EET? Stále s otazníkem

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Podnikatel.cz: Dárky v podnikání. Jak je uplatnit v daních?

Dárky v podnikání. Jak je uplatnit v daních?

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

DigiZone.cz: Další dva kanály nabídnou HbbTV

Další dva kanály nabídnou HbbTV