Dokumentografické informační systémy

Dokumentografické informační systémy

Kód předmětu: NDBI010 Přednáší: Michal Kopecký

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³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 [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í.

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.

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
   }
}