{{Stub}}
{{TOC float}}
{{Sources|''Velkou část otázky pokrývá předmět [[Dokumentografické informační systémy]] [[Michala Kopeckého]] -- [[User:Rajjo|rajjo]] 17:37, 29 Aug 2010 (CEST)''
* slidy k předmětu [http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/ Dokumentografické informační systémy]
* [[wen:Information_retrieval]]
}}
== Informační systémy ==
* Faktografické vs. dokumentografické
* Zpřístupnění vs. dodání dokumentu
* Indexace nutná -- termy
** řízená, neřízená
** tezaury
* Kritérium predikce + maxima
* Precision, recall
== Vyhledávání v textu ==
* Triviální algoritmus
* Knuth-Morris-Pratt
* Aho-Corrasicková
== Boolské informační systémy ==
* Dokument reprezentován množinou termů, které ho vystihují
* Dotazy: AND, OR, NOT, wildcards, víceslovné, proximitní omezení, tezaurus, lemmatizace
* Invertovaný indexový soubor (org. po termech)
* Uspořádání výsledků (DNF, počet splněných konjunkcí)
* Zpětná vazba
== Vektorové informační systémy ==
* Každý z <math>n</math> dokument reprezentování <math>m</math>-složkovým vektorem vah důležitostí termů (<math>\in [0,1]</math>)
* Indexový soubor je matice vah <math>m\times n</math>
* Dotaz je taky vektor, vyhodnocení a řazení pomocí:
** základní <math>Sim(\vec{w}_i,\vec{q}) = \sum_{k=1}^n w_{i,k}q_k</math>
** vylepšení na délku vektorů (počet nenulových <math>w_k</math>) -- dělení <math>\sum w_i + \sum q</math>, <math>\sum w_i + \sum q - 2 \sum wq</math> nebo <math>\sqrt{\sum w_i^2 \cdot \sum q^2}</math>
** jiné -- normalizace na jednotkovou délku vektorů
* Nerozlišuje se disjunkce a konjunkce
* Negace = přidání záporných vah do dotazů
* Indexace podle ''term frequency'' -- <math>TF_{i,j} = \frac{t_j}{\sum_{i=1}^m t_i}</math> (podíl počtu výskytů daného termu v dokumentu z celk. počtu termů v něm)
** Normalizovaná <math>NTF = \frac{1}{2} + \frac{TF}{2 \max(TF)}</math> (do <math>\{0\} \cup [1/2,1]</math>).
** Inverzní <math>ITF_j = \log(n/k)</math>, pokud se term <math>j</math> vyskytuje v <math>k</math> dokumentech z <math>n</math>.
* Výpočet vah <math>w = \frac{NTF\cdot ITF}{Z}</math> (<math>Z</math> je normalizace)
* Matice podobnosti termů -- závislost a zastupitelnost termů
== Induktivní systémy ==
* Dvouvrstvá neuronová síť se zpětnou aplikací vah (1. vrstva - termy, 2. - dokumenty)
* Laterální inhibice -- zabránění nárůstu vah
== Signaturové systémy ==
* Uložení na pomalých médiích -- předstupeň k lepší metodě
* Každý dokument i search term má signaturu, která funguje jako maska (pokud je bitový and signatury dokumentu a termu nenulový, je dokument možná relevantní a použije se k detailnímu hledání)
* Přiřazení signatury -- každý term: jedna jednička na nějakém místě / hashovací funkce
** Zabránění příliš mnoha jedničkám v signaturách dokumentů -- rozdělení na bloky (pevné délky nebo pevného počtu jedniček v signatuře)
* Wildcardy obecně nejsou možné, jen s monotónními signaturami
== Rozšířená boolská logika ==
* Reprezentace stejná jako vektorový model
* Dotazy stejné jako s boolskou logikou, ale s váhami (pokud nejsou uvedeny, bere se 1)
* OR -- vzdálenost od nulového dokumentu <math>DF = (0,\dots,0)</math> jako <math>\sqrt[p]{\frac{q_a^p w_{i,a}^p + q_b^p w_{i,b}^p}{q_a + q_b}}</math> (kde <math>q_a,q_b</math> jsou váhy dotazu)
* AND -- vzdál. od jednotkového dokumentu jako <maht>1 - \sqrt[p]{\frac{q_a^p(1-w_{i,a})^p + q_b^p(1-w_{i,b})^p}{q_a + q_b}}</math>
* Pro <math>p = 1</math> je to vlastně vektorový model, pro <math>p\to\infty</math> se blíží k boolskému
== Rozlišovací hodnoty termů v indexu ==
* Informace o tom, jak dobře termy rozlišují dokumenty -- co se stane, když nějaký z nich vyhodíme
* Rozlišovací hodnota <math>DV_k = Q^{(k)} - Q</math>, kde <math>Q = \frac{\sum_{i=1}^n Sim(d_i,C)}{n}</math> je průměrná podobnost dokumentů s ''centroidem'' ("průměrným dokumentem" <math>C = \frac{\sum_{i=1}^n d_i}{n}</math>) a <math>Q^{(k)}</math> je totéž, odstraníme-li <math>k</math>-tý dokument.
* Je možné použít jako <math>IFT</math>, má lepší vlastnosti než ten logaritmus (viz výše)
== Přibližné hledání ==
* Detekce chyb, nalezení blízkých termů ve slovníku:
** Počet společných digramů
** [[wen:Hamming distance|Hammingova míra]] (počet operací replace při doplnění slova znakem <math>\lambda</math> na stejnou délku)
** [[wen:Levenshtein distance|Levenshteinova míra]] (počet operací replace, insert nebo delete)
* Lze použít konečné automaty
{{Statnice I3}}
