20.500.12556/DKUM-82204 Primerjava algoritmov nenatančnega iskanja vzorcev v nizih magistrsko delo A comparison of approximate string matching algorithms na študijskem programu 2. stopnje Matematika V magistrskem delu predstavimo tri algoritme za reševanje problema $k$ razlik, in sicer rešitev z dinamičnim programiranjem, vključno z Ukkonenovo izboljšavo pričakovane časovne zahtevnosti, algoritem Galila in Parkova ter algoritem Tarhia in Ukkonena. Predstavljene algoritme implementiramo v programskem jeziku Python in izvedemo meritve časov izvajanja pri različnih testnih primerih, tako na angleškem kot slovenskem besedilu. Na koncu predstavimo rezultate meritev in na podlagi le-teh primerjamo algoritme. In this thesis, we present three approximate string matching algorithms for the $k$ differences problem, namely dynamic programming solution, including Ukkonen's improvement of expected time complexity (Ukkonen's cut-off method), Galil-Park algorithm and Tarhio-Ukkonen algorithm. We implement the algorithms in Python programming language and measure their execution times for various test cases, on texts both in English and Slovene. Finally, we present the test results and compare the algorithms based on them. nizi urejevalna razdalja nenatančno iskanje vzorcev v nizih problem $k$ razlik algoritmi analiza algoritmov strings edit distance approximate string matching $k$ differences problem algorithms analysis of algorithms true true false [K. Potočan] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2022-07-29 14:51:09 2022-10-28 11:06:41 2022-10-29 03:08:59 0000-00-00 00:00:00 2022 0 Maribor 0 Maribor VIII, 46 f. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51:004.42(043.2) 127463939 MAG_Potocan_Karmen_2022.pdf MAG_Potocan_Karmen_2022.pdf 1 9996B187B56C57C089E4FC20FA3646B7 7d0e755a471f82c297bbc2007362be7703930efbba14642c038f5f37e73d19e2 58ef97f5-0f45-11ed-ad0e-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=159648 Fakulteta za naravoslovje in matematiko 0 0 0