Fulltextové vyhledávání

Fulltextové vyhledávání (z ang. full – celý a text) je technika hledání textu (řetězce znaků) dle zadání uživatele v elektronických dokumentech a databázích. Název označuje prohledávání celých obsahů dokumentů (textových souborů), na rozdíl od jiných způsobů vyhledávání, kdy je prohledávání omezeno například jen na názvy a další metadata jednotlivých dokumentů. Za účelem rychlejšího vyhledávání se obsah dokumentů indexuje – na základě analýzy jejich obsahu se vytvoří pomocná datová struktura.

Při full-textovém vyhledávání vyhledávací algoritmus prozkoumává všechna slova v každém uloženém dokumentu a pokouší se je porovnat se slovy zadanými uživatelem. Full-textové vyhledávání přichází běžně s databázemi knihoven v sedmdesátých letech. Mnoho webových stránek a aplikací (například textové procesory) umožňují full-textové vyhledávání. Některé webové vyhledávače, jako AltaVista uplatňují full-textové techniky vyhledávání, zatímco jiné hledají pouze v hotovém indexu webových stránek. V praxi je těžké rozeznat, jak vyhledávací algoritmus pracuje. Vyhledávací algoritmy aktuálně využívané ve webových službách se málokdy zveřejňují, aby nebyly zneužity podnikavci pro zvýhodnění svých stránek při vyhledávání.

Indexování

Podrobnější informace naleznete v článku Index (databáze).

Při malém množství dokumentů je možné spustit full-textový algoritmus k přímému prohledávání obsahu dokumentů při každém dotazu, tzv. sériové vyhledávání. K tomu lze využít některé základní nástroje.

Pokud je ovšem množství dokumentů potenciálně větší než kapacita vyhledávacího algoritmu, je pro udržení rychlé odezvy hledání důležité rozdělit vyhledávání do dvou úkolů: indexování a vyhledávání. Indexovací fáze prochází text ve všech dokumentech a vytváří seznam klíčových termínů, často nazývaný index, korektnější termín je konkordance. Ve vyhledávací fázi, kdy se provádí specifický dotaz, je prohledáván pouze k tomu připravený index, namísto originálních dokumentů.

Indexer vytváří záznam v indexu pro každý výraz, nebo slovo, které najde v dokumentu a jeho relativní pozici v dokumentu. Obvykle indexer ignoruje tzv. stop-slova, jako jsou spojky a předložky, které jsou příliš obecné a významově bezvýznamné pro hledání. Některé indexery provádějí jazykově specifické úpravy, jako lemmatizaci (nalezení kmene slova) a derivaci (nalezení odvozených tvarů, tj. skloňování nebo časování).

Přesnost versus zanedbávání

Z důvodu nejednoznačnosti a dvojsmyslnosti přirozeného jazyka, full-textový index typicky produkuje seznam získaných slov s nízkou přesností – mnoho položek je irelevantních. Vyhledávání pomocí řízeného slovníku (např. tezaurus, a jiné) řeší tento problém tím, že označkuje nevhodná slova. Na druhou stranu vyhledávání řízeným slovníkem má nízkou výtěžnost – může vyřadit také dokumenty, které jsou relevantní k vyhledávanému dotazu. Navzdory existenci mnoha irelevantních dokumentů ve volném indexu, volné vyhledávání může být úspěšné při nalezení dokumentu, které řízené vyhledávaní vyřadilo.

Problém falešně pozitivních nálezů

Volné vyhledávání nalezne mnoho dokumentů, které nejsou odpovídající zamýšlenému dotazu. Takové dokumenty se nazývají falešně pozitivní nález. To je často způsobeno nepřesností přirozeného jazyka.

Některé shlukovací techniky založené na bayesovském algoritmu (podobný bayesovskému spamovému filtru například v Gmailu) mohou pomoct snižovat falešně pozitivní nálezy. Pokud tedy zadáme jako dotaz slovo „fotbal“, tato technika může zkategorizovat dokumenty pod názvy „Americký fotbal“, „kopaná“ atd. V závislosti na výskytech slov v dokumentu může spadnout do jedné nebo více kategorií. Tyto techniky byly rozsáhle testovány v e-discovery doméně.

Zlepšení výkonů full-textového vyhledávání

Nedostatky volného hledání je možné eliminovat dvojím způsobem: umožnit uživatelům s nástrojem vyjádřit jejich dotaz přesněji, a vyvinout nový vyhledávací algoritmus zlepšující vyhledávací přesnost.

Zlepšení dotazovacími nástroji

  • Klíčová slova – autoři dokumentů (nebo trénovaní indexeři) jsou vyzváni k seznamu slov které popisují subjekt textu, včetně synonym popisujících subjekt. Klíčová slova zlepšují odezvu, zejména pokud seznam klíčových slov není obsažen v samotném textu.
  • Hledání v polích – popis jsou vytříděny do specifických polí, např. pole „Autor“, nebo „Datum vložení“,... umožní vyhledávat text pouze ve vyhrazených polích.
  • Boolovské dotazy – používání operátorů (například „encyclopedia“ AND „online“ NOT „Encarta“) může podstatně zpřesnit vyhledávání, Například AND operátor říká „nepatří sem žádný z dokumentů který neobsahuje současně obě slova“. Operátor AND tedy zužuje výběr, zatímco OR rozšiřuje. Zlepšení přesnosti vyhledání je velmi často kontraproduktivní, a často vede k snížení vytěžitelnosti.[1]
  • Vyhledávání frází – nachází dokumenty, obsahující přesnou frázi (sled písmen), například „Wikipedie, otevřená encyklopedie“
  • Konkordance – vyhledávání produkuje abecední seznam všech nejdůležitějších slov nacházejících se v aktuálním kontextu.
  • Blízkostní vyhledávání – hledá se fráze z dvou či více slov, které jsou od sebe vzdálené o specifikovaný počet slov. Například hledání „Wikipedia“ WITHIN2 „otevřená“ najde pouze ty dokumenty, ve kterých je výskyt slova „Wikipedia“ maximálně dvě slova od „otevřená“.
  • Žolíkové znaky – hledání nahrazuje jeden nebo více znaků ve vyhledávacím dotazu, například v Microsoft Word, použití hvězdičky „*“ v dotazu „s*d“ nalezne „sud“, „sad“, atd. v textu.
  • Regulární výraz – nabízí sice komplikované, ale velice silné definování dotazu.

Zlepšení vyhledávacího algoritmu

Technologický pokrok významně zlepšuje výkon a přesnost volného vyhledávání textů. Například googlovský algoritmus PageRank dává vyšší důležitost dokumentům, na které odkazuje víc linků (odkazů). Tento algoritmus na základě údajů o popularitě dané uživateli internetu zvyšuje úspěšnost a přesnost vyhledání.

Reference

  1. Studie opakovaně ukazují, že mnoho uživatelů nerozumí formulaci negativních dotazů [1]