IMPLEMENTACIJA I TESTIRANJE ALGORITAMA ZA TAČNO PODUDARANJE STRINGOVA
Ključne reči:
Pretraga teksta, Knuth-Morris-Pratt algoritam, Boyer Moore algoritam, Rabin Karp algoritam
Apstrakt
U radu su opisani algoritmi koji su najčešće u upotrebi za tačno podudaranje stringova. Razmatrani su “Brute force” metoda, algoritam Rabin-Karp, Knuth-Morris-Pratt i Boyer Moore algoritam. Nabrojani algoritmi su implementirani u C# programskom jeziku i izvršena su testiranja njihovih performasi. Rad sadrži rezultate dobijene testiranjem nad dve vrste testnih podataka. Jedna vrsta podataka su veštački generisani primeri koji treba da istaknu dobre i loše strane algoritama, dok drugu vrstu podataka čine realni primeri: tekst knjige „Rat i mir“ i CIM/XML fajl sa 2GB podataka.
Reference
[1] Herbert S. Wilf, “Algorithms and Complexity”, Summer 1994.
[2] C. Charras, T. Lecroq, „Handbook of Exact String-Matching Algorithms“, 2004.
[3] http://staff.ustc.edu.cn/~csli/graduate/algorithms/
book6/chap34.htm (pristupljeno u septembru 2019.)
[4] D. Gusfield, “Algorithms on Strings, Trees and Sequences. Computer science and computational biology”, 1997.
[5] https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/ (pristupljeno u septembru 2019.)
[6] Ramshankar Choudhary, „Variation of Boyer-Moore String Matching Algorithm: A Comparative Analysis“, February 2012.
[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, „Introduction to algorithms“, 2001.
[2] C. Charras, T. Lecroq, „Handbook of Exact String-Matching Algorithms“, 2004.
[3] http://staff.ustc.edu.cn/~csli/graduate/algorithms/
book6/chap34.htm (pristupljeno u septembru 2019.)
[4] D. Gusfield, “Algorithms on Strings, Trees and Sequences. Computer science and computational biology”, 1997.
[5] https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/ (pristupljeno u septembru 2019.)
[6] Ramshankar Choudhary, „Variation of Boyer-Moore String Matching Algorithm: A Comparative Analysis“, February 2012.
[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, „Introduction to algorithms“, 2001.
Objavljeno
2020-03-04
Sekcija
Elektrotehničko i računarsko inženjerstvo
