1. Tekstistä S etsitään merkkijonoa P. Esitä vaihe vaiheelta, miten merkkijono löydetään KMP-menetelmällä? Montako vertailua tarvitaan?
S = aababaabbabaabc
P = abaabc
2. Kuten tehtävä 1, mutta käytä BM-algoritmia.
3. Yleinen käsitys Unix-maailmassa lienee, että tiedonhausta selviää omien tiedostojen osalta monessa tapauksessa grep-komennolla (Linux-manuaalisivut; varsinkin jos et ole käyttänyt komentoa, kokeile!). Analysoi tämän käsityksen perusteita ja vertaile grep-haun ja 'oikean' tiedonhaun ominaisuuksia:
a) Millaisiin hakuihin grep sopii (ei sovi)?
b) Kuinka haun kohteen laajuus ja muoto vaikuttaa?
c) Entä tuloksen laajuus?
d) Fraasihaku, monen hakutermin käsittely?
e) Muut tekijät?
4. Tarkastellaan merkkijonohakuun liittyviä likimääräishakuja.
a) Kokeile likimääräishakua laitoksen kirjaston hakujärjestelmän (tai
jonkin muun järjestelmän) yhteydessä. Mitä voidaan sanoa likimääräishaun
käyttökelpoisuudesta ja ongelmista?
b) Glimpse-järjestelmässä likimääräisyys määritellään
editointietäisyyden kautta. Lisäksi eri virhetyyppejä voidaan painottaa
toisiinsa verrattuna epätasaisesti. Vastaavatko nämä ominaisuudet
käytännön
tarpeisiin? Olisiko muita likimääräisyyden määritys- tai ilmaisutapoja?
5. (***) Selvitä artikkelissa [1] esitellyn LSI-menetelmän pääperiaatteet.
Lähteet:
1. Deerwester, S., Dumais, S. T., Landauer, T. K., Furnas, G. W.
and Harshman, R. A. (1990): Indexing by Latent Semantic Analysis.
Journal of the American Society for Information Science, 41(6), 391 - 407.
http://citeseer.nj.nec.com/deerwester90indexing.html
Hannu.Erkio@cs.Helsinki.FI