Dokumentografické informační systémy

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
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, 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í.

Odkazy

Články

Rydval: Dokumentografické informační systémy

Vizualizace algoritmu

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