Milan Miščević

U sklopu predmeta strukture podataka i algoritmi na drugoj godini smijera za informacione tehnologije na Elektrotehničkom fakultetu u Banjaluci prije skoro tri godine sam imao (kao) zadatak da uradim seminarski rad na temu iz naslova. Ukratko, rad čitaoca uvodi u oblast pretrage sa greškom koja je specifična po tome što dozvoljava pretraživanje uz postojanje izvjesnog procenta greške odnosno razlike između uzorka pretrage i traženog. Dva algoritma iz ove oblasti, Levenštajnovo rastojanje (eng. Levenshtein distance) i saundeks (eng. soundex), su detaljno obrađeni.

Sadržaj

1. Uvod
   1. Funkcije sličnosti
   2. Fonetsko kodiranje i algoritmi
   3. Upotreba
2. Levenštajnovo rastojanje
   1. Algoritam
   2. Složenost
   3. Upotreba
3. Saundeks
   1. Algoritam
   2. Varijacije

Literatura

1. Allison, L., Dynamic Programming Algorithm (DPA) for Edit-Distance, http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/, posjećeno 11.02.2007. godine
2. Chapman, Sam, Sam’s String Metrics, http://www.dcs.shef.ac.uk/~sam/stringmetrics.html, posjećeno 12.02.2007. godine
3. Charras, Christian i Lecroq, Thierry, Levenshtein Distance, http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html, posjećeno 11.02.2007. godine
4. Gilleland, Michael, Levenshtein Distance, in Three Flavors, http://www.merriampark.com/ld.htm, posjećeno 05.02.2007. godine
5. Grmuša, Jelena, Dinamicko programiranje, http://www.matf.bg.ac.yu/~jelenagr/pr/v22.htm, posjećeno 11.02.2007. godine
6. Navarro, Gonzalo, A Guided Tour to Approximate String Matching, University of Chile, mart 2001.
7. Paul E. Black, string matching with errors, U.S. National Institute of Standards and Technology, http://www.nist.gov/dads/HTML/stringMatchwError.html, posjećeno 11.02.2007. godine
8. Repici, Dominic John, Understanding Classic SoundEx Algorithms, http://www.creativyst.com/Doc/Articles/SoundEx1/SoundEx1.htm, posjećeno 11.02.2007. godine
9. Wikipedia, Approximate string matching, http://en.wikipedia.org/wiki/Approximate_string_matching, posjećeno 07.02.2007. godine
10. Wikipedia, Daitch-Mokotoff Soundex, http://en.wikipedia.org/wiki/Daitch-Mokotoff_Soundex, posjećeno 12.02.2007. godine
11. Wikipedia, Damerau-Levenshtein distance, http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance, posjećeno 12.02.2007. godine
12. Wikipedia, Fuzzy string searching, http://en.wikipedia.org/wiki/Fuzzy_string_searching, posjećeno 07.02.2007. godine
13. Wikipedia, Hamming distance, http://en.wikipedia.org/wiki/Hamming_distance, posjećeno 12.02.2007. godine
14. Wikipedia, Levenshtein distance, http://en.wikipedia.org/wiki/Levenshtein_distance, posjećeno 05.02.2007. godine
15. Wikipedia, Metaphone, http://en.wikipedia.org/wiki/Metaphone, posjećeno 12.02.2007. godine
16. Wikipedia, New York State Identification and Intelligence System, http://en.wikipedia.org/wiki/New_York_State_Identification_and_Intelligence_System, posjećeno 07.02.2007. godine
17. Wikipedia, Phonetic algorithm, http://en.wikipedia.org/wiki/Phonetic_algorithm, posjećeno 11.02.2007. godine
18. Wikipedia, Soundex, http://en.wikipedia.org/wiki/Soundex, posjećeno 05.02.2007. godine

Download

Nonexact string (pattern) matching, seminarski rad