{{predmet|Dokumentografické informační systémy|Michal Kopecký|DBI010}}
'''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, C<sup>3</sup>M, 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 [http://uncyclopedia.org/wiki/Kitten_huffing]
* 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í.
== Odkazy ==
*[http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/ stránka předmětu] (včetně 533 slidů prezentace)
*[http://forum.matfyz.info/viewtopic.php?f=466&t=9682 studentské poznámky]
=== Články ===
==== Rydval: Dokumentografické informační systémy ====
* [http://www.rydval.cz/phprs/view.php?cisloclanku=1980010101 Úvod]
* [http://www.rydval.cz/phprs/view.php?cisloclanku=1980010102 Modely]
** případně oba v pdf (vysázený latex) http://www.rydval.cz/phprs/download.php?soubor=27
=== Vizualizace algoritmu ===
*[http://downloads.academy.telerik.com/svn/algo-academy/2013-04-Training-for-NOI/Knuth-Morris-Pratt.pptx KMP]
*[http://www-sr.informatik.uni-tuebingen.de/~buehler/BM/BM.html Boyer-Moore]
** http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm
** http://www2.inf.fh-rhein-sieg.de/~pbecke2m/BM/html/Help.html
** http://downloads.academy.telerik.com/svn/algo-academy/2013-04-Training-for-NOI/Boyer-Moore.pptx
*[http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html Aho-Corrasick]
== Boyer-Moore algoritmus ==
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.
{| border="1" cellspacing="0" cellpadding="5" class="wikitable" style="text-align:center"
|+'''Pole P[j,x] pre ANANAS'''
|-
! 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
}
}
[[Category:Informatika]]
