{{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, 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 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

*stránka předmětu (včetně 533 slidů prezentace) *studentské poznámky

Články

Rydval: Dokumentografické informační systémy

  • Úvod

  • Modely

    • případně oba v pdf (vysázený latex) http://www.rydval.cz/phprs/download.php?soubor=27

Vizualizace algoritmu

*KMP *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

*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.

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