Invertované soubory

Indexování je společné všem typům databází. Tvoří základní přístupový mechanismus k datům. Již v šestém pok...


Indexování je společné všem typům databází. Tvoří základní přístupový
mechanismus k datům. Již v šestém pokračování
Databázové abecedy jsme se zabývali indexovanými soubory. V architekturách
dokumentografických systémů (DIS) se jim říká invertované. V prostředí
vyhledávacích strojů, které pracují s rozsáhlými databázemi úplných textů, je
jejich role nezastupitelná. Jak v praxi, tak ve výzkumu se stále věnuje velké
úsilí tomu, jak invertované soubory implementovat efektivně.
Koncepce invertovaných souborů je založena na reprezentaci dokumentu pomocí
množiny termů. Invertovaný soubor je pak setříděný seznam (nazývaný též index)
těchto termů, přičemž každý term má vazbu na kolekci dokumentů. Představíme-li
si, že dokumenty jsou vlastně záznamy, pak se invertované soubory příliš neliší
od koncepce indexovaného souboru nebo indexované tabulky v relační databázi.
Zatímco u SŘBD slouží index ke zlepšení provozu databáze, index v DIS, který
samozřejmě má také tuto funkci, s sebou nese ještě další přídavná data: lodkaz
od klíče (termu) na dokument v souboru indexů může obsahovat např. frekvenci
klíče v daném dokumentu nebo pozici klíče v dokumentu,
lsoubor indexů může obsahovat data týkající se celé kolekce, např. maximální
frekvenci termu v kolekci textů.
Rozdíl mezi indexy v DIS a v relačních SŘBD je tedy v tom, že u DIS je potřeba
brát úvahu některé speciality textů, např. jejich strukturovanost na odstavce,
vě-ty apod., případně i to, že často
požadujeme udržovat index na všechny výskyty slov v dokumentu. Přídavné
informace jsou pak potřebné pro implementaci některých dalších modelů DIS.
Logická struktura invertovaného souboru se může skládat ze 2 částí: seznamu
dvojic (term, ukazatel), kde ukazatel ukazuje na počátek seznamu souřadnic.
Seznam souřadnic má prvky dvojice (číslo-dokumentu, ref), kde ukazatel ref
ukazuje na začátek dokumentu s daným číslem. Schematicky je tato struktura
ukázána na obrázku 1.
Seznamy souřadnic lze sdružit do jednoho seznamu. Pro každý term se udržuje
číslo určující počet dokumentů (P_hitů), ve kterých se term vyskytuje (obr. 2).
V (starších) komerčních systémech je obvykle jak seznam termů, tak seznam
souřadnic implementován staticky, tj. v podstatě stejně jako na obrázku 2. Oba
soubory jsou sekvenční soubory. Jako základní metoda vyhledávání se uplatní
půlení intervalu, tj. výsledek je získán v čase úměrném logaritmu počtu bloků v
jednotlivých souborech. Souřadnice se používají v různé jemnosti. Nejhrubší
přístup je k dokumentu jako takovému, jemnější přístup odhalí části jeho
vnitřní struktury. Tak lze souřadnicemi určit kapitolu, odstavec, či dokonce
větu, ve které se daný term vyskytuje. Výše uvedené struktury jsou vhodné pro
statické kolekce. Je patrné, že se změnami dokumentů by propagování změn do
struktury invertovaného souboru mohlo být dost náročné. Současné aplikace DIS
mohou obsahovat dynamické kolekce dokumentů, tj. dokumenty mohou být přidávány,
odstraňovány a modifikovány. Kompromisem může být aktualizace po dávkách. Jiným
kompromisem může být např. aktualizace dokumentu "po stránkách", kde odstraněný
text je nahrazován prázdnými znaky a přidávaný text může být realizován pomocí
stránek přetečení. V dynamickém prostředí se uplatňují datové struktury jako
B-stromy, dynamické hašování apod.
Konjunktivní dotaz pomocí invertovaného souboru
Nejčastějším typem dotazu je při použití DIS konjunktivní dotaz (AND-dotaz),
tj. dotaz vyjádřený jako Q: t1 AND t2 AND _AND tk, kl1. V základní verzi jde o
proces, který pro zadanou množinu termů vyhledá v invertovaném souboru
odpovídající soubory souřadnic a realizuje nad nimi jisté (množinové) operace.
Je obvyklé, že než DIS vydá vlastní dokumenty, oznámí uživateli, kolik jich
vyhovuje dotazu. To je rozumné, protože v opačném případě by díky neurčitosti,
která dotaz provází, DIS manipuloval s příliš rozsáhlou množinou dokumentů.
Materializace takové množiny je časově náročná a drahá (např. jde--li o tištěný
výstup). Teprve po souhlasu uživatele je tento krok proveden, v dalších
případech může docházet k upřesňování dotazu.
Zajímavé je, jak efektivně vyhodnotit konjunktivní dotaz. Intuitivně je patrné,
že množina hitů je dána průnikem souborů souřadnic pro jednotlivé termy z
dotazu. Efektivní vyhodnocení dotazu se tedy redukuje na implementaci
algoritmu, který konstruuje průnik množin. Tento algoritmus lze realizovat
např. tak, že se začne od termu s nejmenší množinou souřadnic. Množina se potom
redukuje na základě testování prvků z množin souřadnic dalších termů (ty se
berou v pořadí zvyšujících se mohutností). Pro realizaci tohoto algoritmu je
nutné ukládat hodnotu P_hitů.
Konstrukce invertovaného souboru
Získání invertovaného souboru lze např. provést pomocí následujících 3 kroků:
1.Rozpoznání slov při sekvenčním čtení textu, přičemž každé slovo je srovnáváno
se seznamem nevýznamových slov, a jejich uložení do souboru slov spolu s jejich
umístěním (číslo dokumentu).
2.Setřídění souboru slov. 3.Odstranění eventuálních duplicit, případně výpočet
frekvencí v dokumentu, vytvoření invertovaného souboru. Formálněji, v prvním
kroku získáme seznam trojic (Číslo_ dok, Ukazatel, Term). Tento seznam je třeba
setřídit podle atributů Term, Číslo_dok, Ukazatel. Tedy proces inverze je možné
chápat jako problém setřídění velkého množství jistých n-tic. V průběhu třídění
je možné odstraňovat duplicity (týž term se vyskytuje v dokumentu vícekrát).
Tento postup, jakkoliv se zdá jednoduchý, může v praxi činit potíže. Uvažujme
např. soubor obsahující 1 000 000 slov. Kdybychom kódovali pouze dvojice
(Číslo_termu, Číslo_dok), pak bychom při velikosti čísel 4Byte potřebovali pro
soubor těchto dvojic 8 Mbyte. Pro třídění takového souboru je třeba dalších 8
Mbyte. Celkově tedy musí být pro soubor, jehož invertovaný soubor nebude
nakonec činit více než 5-6 Mbyte, celkem 16 Mbyte pomocné paměti. Navíc externí
třídění je pomalá operace. Je-li inverze prováděna periodicky (rozšiřuje-li se
textová databáze), pak se musí s touto pamětí, která je srovnatelná s celou
databází, počítat v průběhu celého života databáze.
Zipfův zákon
Při návrhu invertovaného souboru, který obsahuje odkazy na jednotlivé
(opakující se) výskyty slov v textu, lze často využít Zipfova zákona.
Představme si, že seřadíme všechna slova uvažovaná v rámci nějakého textu podle
četnosti jejich výskytů, tj. každému slovu t přiřadíme jednoznačně číslo rt
dané tímto pořadím. Frekvence ft nechť označuje frekvenci výskytů daného slova
t v kolekci textů. Zipfův zákon je pak formulován následujícím vztahem
ft = k/rt,
kde k je konstanta. Tento zákon popsal Zipf (spolu s dalšími "hyperbolickými"
zákony) v r. 1949. Konstanta je různá pro různé kolekce. Je-li N počet všech
výskytů slov v textu, pak pro angličtinu se hodnota k blíží N/10. Označíme-li
pt = ft/N, pak lze Zipfův zákon také formulovat jako
rt*pt = A. Hodnota A se pro anglické texty blíží 0,1. Ze Zipfova zákona také
plyne, že slovo s frekvencí ft má
rt = AN/ ft.
Zipfův zákon též můžeme použít ke spočítání počtu termů s daným počtem výskytů.
Nechť k termů má stejnou frekvenci. Vezměme poslední ze skupiny s pořadím rf.
Tedy rf termů má alespoň f výskytů. Dále r(f+1) termů již má více než f + 1
výskytů. Z toho plyne, že rf rf+1 termů má f výskytů. Tuto veličinu Cf
vyjádříme jako AN/ f AN/(f+1), tj. Cf = AN/(f(f+1)).
Na základě Zipfova zákona je tedy možné spočítat relativní frekvence dalších
slov, je možné zodpovědět takové otázky, jako kolik výskytů má slovo s daným r,
kolik výskytů má prvních 10 nejfrekventovanějších slov. Např. pro každou
kolekci je rt, pro term, který se vyskytuje pouze jednou, roven AN/1, tj. AN.
To platí ovšem za předpokladu, že existuje alespoň 1 term s právě jedním
výskytem. Počet termů., které se vyskytují právě jednou, je AN/2. Počet těch,
které se vyskytují právě dvakrát, je AN/6, tj. 17. Praktickým důsledkem může
být zodpovězení otázek jako např. "Kolik slov musíme umístit do seznamu
nevýznamových slov, abychom zredukovali invertovaný soubor o 30 %".
Ukážeme závěrem část statistiky získané z kolekce 423 článků z časopisu TIME,
která obsahuje 245 412 slovních výskytů. Prvních 10 prvků seznamu použitých
slov uspořádaných podle r, tedy vlastně podle snižujících se hodnot ft, je
obsaženo v tabulce 1. Termy na 41.-50. místě jsou v tabulce 2.
Rozšíření invertovaných souborů
Základní struktura invertovaného souboru může být obohacena o další data, která
umožňují implementovat některé pokročilejší funkce, které se vyskytují v DIS.
Patří sem např. omezení na vzdálenost mezi termy, váhy termů, odkazy na
synonyma, či realizace zástupných znaků.
Omezení na vzdálenost mezi termy má vztah k vnitřní struktuře dokumentu.
Dokument je možné chápat např. ve struktuře odstavec, věta, pozice ve větě. V
dotazu pak můžeme vyjádřit distance, tj. aby "relační" a "databáze" následovaly
ve větě po sobě, nebo aby "databáze" a "architektura" se vyskytovaly v jednom
odstavci atd. Při realizaci invertovaného souboru to znamená, umístit do
záznamů seznamu souřadnic vedle čísla dokumentu také číslo odstavce v
dokumentu, číslo věty v odstavci, případně i pozici termu ve větě.
Z dalších údajů lze ke každé souřadnici ukládat např. hodnotu četnosti termu v
daném dokumentu. Lze tak dosáhnout implementace zahrnující v sobě vektorový
model. Výsledkem je dnes tolik požadovaný efekt (viz vyhledávací stroje jako
HOTBOT apod.) uspořádání hitů z odpovědi na dotaz v Boolském modelu.
8 1152 / or









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.