<math>P = #vybraných relevantních záznamů / #vybraných záznamů</math>
== Databáze textů: modely (boolský, vektorový) (🎓🎓🎓🎓🎓🎓🎓) ==
''+ Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace''
{{TODO| projít a ořezat}}
{Zkazky|
* '''DMJ - Booleovský a vektorový model (2012)''' - Slovy jsem popsal oba modely. U Booleovského jsem popsal, jak se indexuje, jak se vybírají termy a jak vypadají dotazy. Zmínil jsem se o složitosti počítání relevance. Dále jsem popsal vektorový model, jak vypadají dotazy apod. Zmínil jsem se, jak se počítá TF a ITF. Zkoušející se jen zeptal na pár otázek a byl spokojen.
* '''DMJ - Indexace v DIS (2009, Kopecky)''' - Boolske systemy - reprezentace matici - moc velke, signatury, zbytek ze mne musel pan Kopecky dost pacit (invertovany soubor, jak ho ziskame - setridim dvojice (term, dokument) vnejsim tridenim a pak k nim sestrojim ten invertovany index). Vektorove systemy - formulovat vsechny vzorecky na TF, ITF, NTF, normalizovany vektor pro dokument. Takze tam jsem uz dalsi otazku nedostal..
* '''DMJ - Vekt. a boolsky model (2009, Kopecky)''' - Zrejme oblubena otazka pana Kopeckeho. Uz som bol unaveny ale dal som boolsky model vcelku obstojne a pri vektorovom iba zaklad. Pan Kopecky ale skusa prijemnym sposobom a ak ste to nikedy vedeli tak to z vas dostane seriou lahkych otazok. Nepotrpi si na formalizmoch - staci mu to porozpravat po lopate a vediet princip :)
* '''DMJ - Indexace dokumentů (2009, Skopal)''' - mám invertovaný soubor, index obsahuje jednotlivé termy, které pak mají seznam dokumentů, ve kterých se vyskytují - co ze mě doc. Skopal doloval bylo říct, že tyhle dokumenty jsou v tom seznamu setřízené, aby bylo urychlené vyhodnocování (problém byl v tom, že obrázek, kterej jsem k tomu nakreslil nebyl úplně jednoznačnej a každej jsme ho pochopili jinak, takže jsem za vůbec nechápal, co po mě chce, ale moh jsem si za to sám
* '''DMJ - Vektorový model (2008, Pokorný)''' - chápal som to len intuitívne (vôbec som nevedel žiadne vzorce ITF a podobne), čo mu trochu vadilo, nakoniec to pochopil a netrápil ma
* '''IDS - Vektorovy a boolovsky model (2009, Kopecky)''' - princip, tvar dotazu a odpovede, implementacia
}}
[[File:pr.png|right|thumb|220px|Precission vs Recall]]
==== Přesnost a úplnost (Precission vs Recall) ====
* <math>P = \frac{\text{#vybraných relevantních záznamů}} {\text{#vybraných záznamů}}</math>
* <math>R = \frac{\text{#vybraných relevantních záznamů}} {\text{#relevantních záznamů v souboru}}</math>
* 💡 závislost R a P je v praxi na hyperbole (zvětšující se P snižuje R a obráceně)
==== Boolský model DIS ====
:Každý dokument je popsán množinou termů, které obsahuje. Termy jsou uloženy v indexovém souboru a odtud potom probíhá vyhledávání.
*určení termů:
**ručně - každý může určit jiné termy, dokonce i jeden člověk se může 2x rozhodnout jinak
**automaticky - jednoznačné, ale bez porozumnění textu
** při určování termů by se měla vynechávat nevýznamová slova (předložky, spojky...), ale také příliš specifická slova
*Indexy lze nad kolekcí dokumentů vytvářet dvojím způsobem. Buď je množina termů pevně daná a pro každý nový dokument se aktualizují jen indexy (řízená indexace), nebo se s každým novým dokumentem přidávají i nové termy (neřízená indexace).
*Vyhledávání:
** probíhá klasicky přes termy pomocí "AND", "OR", "NOT"
** lze také využít faktografické informace o dokumentu (autor, datum vytvoření...)
** lze použít zástupné znaly ?, *
*Proximitní omezení
** při vyhledávání lze také užít proximitních omezení, tedy informaci o tom, v jaké vztahu dva hledané termy jsou (o kolik slov jsou vzdáleny, zda jsou ve stejném odstavci, nebo větě.
** pro práci s omezeními je třeba buď mít přítomny dokomenty a informaci zjišťovat přímo v nich a nebo rozšířit index -> namísto <term_id, doc_id> musí existovat index <term_id, doc_id, par_nr, sent_nr, word_nr>
Nevýhody boolského DIS:
*při zadávání dotazu jsou všechny termy stejně důležité
*ve výsledku disjunktního dotazu jsou promíchány dokumenty které obsahují všechny požadované termy s těmi, které obsahují pouze jeden
*ve výsledku konjunktivního dotazu nejsou dokumenty, které obsahují neobsahují žádný z termů stejně tak jako ty které neobsahují pouze jeden
==== Vektorový model DIS ====
Vektorový model je mladší než boolský (asi o 20 let) a vznikl aby odstranil chyby boolského modelu - především díky možnosti ohodnotit termy jak v dotazu, tak v indexu.
*Každý dokument je v indexu definován váhami pro jednotlivé termy.
*dotaz se zadává vektorem vah pro požadované termy <w1, w2, .. , wn>, w in <0,1>
*protože dlouhé dokumenty by byly zvýhodněny (obsahují jistě více termů), provádí se normalizace vektorů, to lze provádět:
**během indexace, což nezvětšuje odezvu, je však zapotřebí občas vše znovu "přenormalizovat"
**během vyhledávání - zpomaluje odezvu, je v definici podobnostní funkce
*Oproti boolskému modelu lze omezit velikost výstupu - výstup je seřazen dle relevance a tedy lze omezit jak počtem výstupů tak minimální relevancí.
*Podobnost mezi dotazem a dokumentem se určuje pomocí podobnostní funkce. Taková funkce není jednoznačně daná, podobnost může být tedy při různých implementacích různá. Základní podobnostní funkce je skalární součin přes dotaz a dokument (sim(q,d) = q x d), jsou ale i složitější:
Kosinová míra: <math>sim(q,d) = \frac{q \times d}{\sqrt(\sum(q_i^2)) * \sqrt(\sum(d_i^2))}</math>
Jaccardova míra: <math>sim(q,d) = \frac{q \times d}{\sum(q_i) + \sum(d_i) - \sum(q_i * d_i)}</math> a další.
*Pokud je po vektorovém modelu požadován i dotaz s negací, lze váhu w uvažovat z <-1, 1> a stejně tak i zadávat dotaz.
*Indexace:
**frekvence termu v dokumentu TF = #výskytů termu / #všech termů v dokumentu
**je potřeba vyřadit nevýznamová slova (stop list = {the, a, an, on ... })
**ignorovat termy s velmi nízkým výskytem
**normalizovat frekvenci ostatních termů <math>NTF_i = \frac{1}{2} + \frac{1}{2} * \frac{TF_i}{max(TF_j)}</math>, j = index jednotlivých termů
* Inverzní frekvence termu v dokumentech
** Nasel jsem dvě definice. První je od [http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/disslide.ppt Kopeckého] druhá od [http://lisp.vse.cz/znal2001/pokorny.ppt Pokorného]. Definice jsou v podstatě matematicky ekvivalentní.
** ''n'' je počet všech dokumentů.
** ''k'' je počet dokumentů ve kterých se term vyskytuje.
# <math>ITF = -log\left(\frac{k}{n}\right)</math>
# <math>IDF = log\left(\frac{n}{k}\right) + 1</math>
Váha termu i v j-tém dokumentu se urči jako <math>w_{ij} = NTF_{ij} * ITF_j</math>
*Dotazování (dotaz má stejnou reprezentaci jako index):
**Zadáním vektoru dotazu
**odkazem na zaindexovaný dokument (tedy "najdi mi dokumenty podobné tomuto")
**odkazem na jiný dokument (není problém pro něj spočítat vektor termů)
**přímo vložený text (obdoba předchozího)
*Lze uplatnit i zpětnou vazbu, kdy uživatel označuje relevantní dotazy a DIS na to reaguje přehodnocením výpočtu.
=== Signatury, metody implementace signatur (vrstvené kódování) ===
{{TODO| projít a ořezat}}
pro konjunktivní dotazy nad boolským modelem
Dotazem je
mnozina termu, dokument odpovida dotazu, pokud obsahuje vsechny termy. Kazdemu
dokumentu se priradi signatura, dotazu taky. Signaturou je k-bitovy retezec
s_1s_2,...s_k.
Signatura
(dotazu) S vyhovuje signature (termu) T, pokud s_i <= t_i pro vsechna i
nebo-li S and T = S. Tohle se efektivneji pocita jako S and not T = 0.
Negativni vysledek zarucuje, ze tam nejsou (vsechny) hledane termy, pozitivni
rika, ze tam byt mohou. Je pak treba pouzit nejakou jinou metodu, treba presne
vyhledani.
'''prirazeni signatury termu''' - 1.
bitova mapa - signatury musi mit tolik bitu, kolik je termu.
2.hashovaci fce,
ktera priradi termu signaturu, jejiz bitovy zapis obsahuje prave jednu jednicku
(pro 128bitove signatury tedy mame 128 moznych ruznych signatur jednotlivych
termu). to se hodi pro vrstveni viz nize.
'''prirazeni signatury textu '''je
mozno 2 zpusoby (nebo jejich kombinaci):
'''Vrstveni signatur''' - metoda
prirazeni vice termu jednomu dokumentu. Na signatury reprezentujici jednotlive
termy se zavola OR a vysledna signatura se priradi dokumentu. Pri vrstveni
vetsiho poctu signatur to ztraci na efektivite - moc jednicek (same jednicky
vyhovuji kazdemu dotazu). Proto se dokumenty rozdeluji na bloky se samostatnymi
signaturami. Při vhodném dělení, např. na rozhraní kapitol nebo odstavců, není
ztráta informace příliš důležitá.
Slova nacházející se daleko od sebe spolu obvykle nesouvisí
Bloky se vytváří
dvěma metodami: FSB (fixed size block) pro úseky s přibližně stejným počtem
slov. FWB (fixed weight block) pro úseky s přibližně stejným počtem jedniček
optimálně k/2 (stejne jednicek a nul).
'''Retezeni signatur - '''vhodne pro
strukturovana data (autor, rok vydani,..) vysledna signatura vznikne zretezenim
signatur pro jednotlive polozky.
'''monotonni signatury''' - ma-li term
t signaturu x, tak term tu (zretezeni termu t a termu u) ma signaturu v kazdem
bitu >= signature x. Dobre pro nalezeni napr. sklonovanych slov pri zadani
korene apod. Monotónní signatury lze vytvářet vrstvením signatur tzv. n-gramů
(n po sobě jdoucích znaků) – např. pro trigramy by byla monotonni signatura
slova „kocka“ – sig(„koc“) | sig(„ock“) | sig(„cka“)
'''invertovany soubor''' - index
organizovan pomoci signatur. Pro jednotlivé pozice v signaturách se
udržují bitové sloupce. Pri porovnavani se signaturou dotazu se pak vezmou ty
bitové sloupce, kde je v dotazu 1 a spustí se na nich bitové AND a mám bitový
sloupec, kde tam, kde jsou jedničky, jsou potenciální hledané záznamy.
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny6 Slajdy pokorny]
*signatura bloku textu je d-bitový řetězec, který v sobě nese informaci o tom, které termy v bloku jsou
*'''vrstvéní signatur'''
**každý term má svou signaturu (vypočtenou pomocí hash funkce) dlouhou d bitů a signatura bloku = OR přes všechny signatury termů v bloku.
*'''řetězení signatur'''
**signatury se spojují do řetězce - vhodné pro strukturovaná data (autor, rok vydání, nakladatelství...)
*'''transponovaný soubor signatur'''
**namísto N řetězců délky d mám d řetězců délky N (pokud signatury bloků naskládám do matice, koukám se pak na ně místo jako na řádky jako na sloupce)
**protože počet 1 v dotazu délky d je o mnoho menší než d a můžu porovnávat jen řetězce kde má dotaz jedničku, porovnávám toho daleko méně
**složitější aktualizace
*'''soubor indexovaných deskriptorů'''
**stejně jako z termů vytvářím vrstvením signaturu bloku, můžu pro více bloků vytvořit společnou signaturu
*'''dvouúrovňové vrstvené kódování'''
**každý blok má dvě signatury - vnětší (délky ds) a vnitřní (délky dn) kde dn << ds, bloky jsou rozděleny do skupin a každá skupina má vrstvenou signaturu ds - podle ní se rozlišují skupiny a ve skupin se bloky rozlišují podle signatury dn (tedy najdu skupinu bloků a pak v ní blok)
*'''rozdělený soubor signatur'''
**signaturu bloku délky d rozdělím na dva kusy (prefix a zbytek) a pak seskupím "zbytky" se stejnými prefixy - pokud testuju, otestuju nejdřív prefix a pokud se neshoduje, do skupiny vůbec nemusím chodit, čímž ušetřím celkem dost času
Metody je možné různě kombinovat tak, aby výsledná struktura byla co nejefektivnější.
=== Uspořádání odpovědi ===
Jde o to, aby se odpovědi uspořádávaly dle relevance, ve vektorovém modelu je to ok, u booleovského modelu je možné rozložit dotaz do DNF (disjunktně normální formy a ohodnotit jednotlivé výstupy podle toho, kolik je ne negovaných termů ve splňované podformuli)
* př.: kocka AND pes => (kocka AND pes) OR (kocka AND NOT pes) OR (NOT kocka AND pes).
Rozšíření booleovského modelu – lze pokládat vážené dotazy – např kocka (0,9) AND pes (0,3), dokumenty mají také ohodnocený vektor termů. Různé metody, liší se podle toho, jak je vypočítáván AND a OR, např. ve Fuzzy logice je AND minimum a OR maximum vah.
== Vyhledávání vzorku v textech (sousmerné, protismerné) ==
{{TODO|minimalne pridat obrazky <s>pridat z wordu</s>}}
* algoritmy vyhledávání vzorku v textu se liší v závislosti na tom, zda je vzorek předzpracován či nikoliv
** trivialni algoritmus - na kazde pozici zkus porovnat cely vzorek (bez předzpracování vzorku)
** s předzpracováním vzorku – vhodné pro DIS
*** pracují jako určitý typ konečného automatu
*** dělí se dále dle počtu hledaných vzorků (1, N, nekonečno) a podle směru porovnávání (sousměrné/protisměrné)
<pre> sousměrné protisměrné
1 KMP BM
N AC CW
nekončeno KA 2CKAS</pre>
===KMP algoritmus===
*testování jednoho vzorku oproti textu
*má pomocné pole délky vzorku
*o(m + n) (délka textu + vzorku)
* Knuth-Morris-Prattuv alg (1 vzorek - optimalizace trivialniho algoritmu aby se nevracel porad zpet o celou jiz zkontrolovanou cast, pomocné pole P, které říká odkud ve vzorku je možné porovnávat, aby již porovnaná část textu odpovídala vzorku) – časová složitost O(m+n), kde m je délka textu, n délka vzorku
===Boyer-Moorův algoritmus===
*testování jednoho vzorku oproti textu
*testuje odzadu dopředu ve vzorku
*má dané dvourozměrné pole kam skočit, když text a vzorek různé (pro znaky, které vzorek neobsahuje skáče vždy o celý vzorek)
*průměrná složitost je o(m*n) ale v praxi o(m/n)
*na běžném textu je mnohem efektivnější než KMP
*lze vylepšit tak, že dvourozměrné pole je nahrazeno dvěma jednorozměrnými
**P1 - pro každé x z abecedy poslední pozice výskytu ve vzorku (pro znaky co nejsou ve vzoru délka celého vzorku)
**P2 - pro každou zkontrolovanou část (nějaká podčást odzadu vzorku) je dán skok na stejný podřetězec vyskytující se dříve ve vzorku.
**je vybrán větší skok z obou polí
* Boyer Moore (1 vzorek, proti směru, "tropickym ovocem je i ananas")
** přikládám vzorek k textu zleva doprava, ale porovnávám ho zprava doleva (když nesedí nějaká pozice, posunu vzorek doprava co nejméně tak, aby na sebe lícoval znak, který způsobil kolizi z textu a znak ve vzorku – posouvání se řeší pomocí jednoduché fce SHIFT[pozice_kolize_vzorku, kolizni_znak_textu)
** celý algoritmus lze dobře řešit konečným automatem (abeceda – znaky ve vzorku a speciální znak pro všechny ostatní znaky, stavy – pozice ve vzorku)
** časová složitost v průměrném případě O(m*n)
** v případě velkých abeced a vzorků s malým počtem různých znaků (např. přirozené jazyky je průměrná časová složitost O(m/n)
** na běžném textu mnohem efektivnější než KMP – při používání víceslovných vzorků: např. „matematicko-fyzikální fakulta“ se počet porovnání nemusí ani zvyšovat (dokonce by se mohl snížit)
** optimalizace – posun tak, aby se shodovala již kontrolovaná část (kombinace posunu BM a KMP)
===Aho-Corasick===
* Aho-Corasick (vice vzorku - alg. z uvodu do teoreticke inf.)
** konečný automat, stavy – všechny prefixy hledaných vzorků, dopředná funkce (parametr znak), zpětná funkce (pro znaky, pro které není def. dopředná funkce určuje zpětná funkce nejdelší vlastní prefix stavu, který se vyskytuje mezi stavy – když to nejde dopředu, vrátí se po zpětné funkci, když to nejde ani tady, vrátí se zase po zpětné funkci), při dojití do přijímacího stavu je třeba zkontrolovat jestli nebylo s tímto slovem přijato i jiné, které by bylo postfixem tohoto (buď pomocí zpětné funkce, anebo definováním množiny přijímaných slov v každém přijímacím stavu)
** časová složitost O(m+suma(n_i))
{{collapse|další algoritmy|
* Commentz-Walterová
** kombinace BM a AC, konečný automat jako u AC, ale místo stavů odpovídajících prefixům, stavy odpovídající postfixům. Při kolizi složitější posun (tři posouvací funkce, ze dvou se bere maximum a z výsledku a třetí se bere minimum)
** časová složitost O(m*min(n_i))
* Konečný automat
** umožňuje definovat přijímaná slova pomocí regulárních výrazů
** nedeterministický KA -> převede se na deterministický KA
* Dvoucestný konečný automat se skokem (2CKAS)
** konečný automat, přechází mezi stavy (pozice v hledaném vzorku) a zároveň posouvá (skáče) se vzorkem na prohledávaném textu
}}
