Dokumentografické informační systémy
Z ωικι.matfyz.cz
Dokumentografické informační systémy | ||||
|
Dokumentografické informační systémy zahrnují:
- úvodní teorii o tom, jak je těžké hledat dokumenty
- algoritmy pro vyhledávání v textu
- Knuth-Morris-Pratt
- Boyer-Moore
- Aho-Corrasick
- Commentz-Walter
- konečné automaty (+dvojcestné se skokem)
- modely DIS
- boolský (proximitní omezení, tezaurus)
- vektorový
- různé míry
- indexování, dotazy nad tím, zpětná vazba
- ekvivalence a hierarchie termů
- shlukování dokumentů (Kohonenovy mapy, C3M, sférický k-mean algoritmus)
- další modely vycházející z vektorového (induktivní model, sémantické sítě)
- další modely vycházející z boolského (fuzzy model, MMM, paice, rozšířená boolská logika)
- odstranění závislosti na termech
- v boolském modelu – síť konceptů
- ve vektorovém modelu – signal value decomposition, latent semantic indexing
- signatury
- distribuované DIS
- horizontální, vertikální a kombinovaná fragmentace
- integrované DIS, optimální vyhledávání, různé metriky
- vyhledávání v HTML (využití hypertextu, PageRank, HITS)
- komprese v DIS (Fibonacciho kódování, Eliasovy kódy, Huffmanovo kódování, HuffWord [1]
- neurovové sítě a DIS
- prokletí dimenze (pyramidová technika, IGrid)
Zkouška je ústní s papírem. Dostanete dvě otázky, pak nad nimi dumáte a píšete. Když jste vytlačili vše, přisedne Kopecký k vám, pročte papír a u slabých míst se vás doplňujícími dotazy snaží navést k poznání. V případě potřeby nechá čas na další promyšlení.
Obsah
Odkazy[editovat | editovat zdroj]
- stránka předmětu (včetně 533 slidů prezentace)
- studentské poznámky
Články[editovat | editovat zdroj]
Rydval: Dokumentografické informační systémy[editovat | editovat zdroj]
- Úvod
- Modely
- případně oba v pdf (vysázený latex) http://www.rydval.cz/phprs/download.php?soubor=27
Vizualizace algoritmu[editovat | editovat zdroj]
Boyer-Moore algoritmus[editovat | editovat zdroj]
V skriptách k DIS je príliš veľa chýb, tak pre tých, ktorí majú problém pochopiť tento algoritmus (tak ako ja :-) prikladám snáď pochopiteľnejšie vysvetlenie ....
Mám text a hľadaný výraz. Hľadaný výraz prikladám zľava doprava k textu a znaky z výrazu porovnávam odzadu s textom.
Najprv vytvorím dvojrozmerné pole P[j,x] a potom podľa neho posúvam hľadaný výraz doprava.
j\znak | A | N | S | X |
---|---|---|---|---|
0. | 0 | 1 | 1 | 1 |
1. | 1 | 0 | 2 | 2 |
2. | 0 | 1 | 3 | 3 |
3. | 1 | 0 | 4 | 4 |
4. | 0 | 1 | 5 | 5 |
5. | 1 | 2 | 0 | 6 |
Príklad:
OVOCEM JE ANANAS ANANAS P[5,'M'] = 6 ... posuniem výraz o 6 znakov doprava ANANAS P[5,'N'] = 2 ANANAS P[5,'N'] = 2 ANANAS
Algoritmus na výpočet tabuľky P[j,x]:
enum Znak { A, N, S, X; // X zastupuje vsetky znaky rozne od A, N, S int last = 0; // posledna pozicia znaku vo vyraze, napriklad pre N bude postupne last = 2, last = 4 }
public void initBM(String vyraz, int[][] p) { // prejdi cely vyraz for ( int j = 0; j < vyraz.length(); j++) { // aktualizuj poslednu poziciu znak vo vyraze Znak.valueOf(vyraz[j]).last = j + 1; // vypln j-ty riadok tabulky for (Znak znak : Znak.values()) p[j][znak.ordinal()] = (j + 1) - znak.last; // najblizsia pozicia znaku "znak" smerom dolava od pozicie j vo vyraze } }