| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document Help

Title:Primerjava algoritmov nenatančnega iskanja vzorcev v nizih : magistrsko delo
Authors:ID Potočan, Karmen (Author)
ID Taranenko, Andrej (Mentor) More about this mentor... New window
Files:.pdf MAG_Potocan_Karmen_2022.pdf (723,33 KB)
MD5: 9996B187B56C57C089E4FC20FA3646B7
 
Language:Slovenian
Work type:Master's thesis/paper
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract: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.
Keywords:nizi, urejevalna razdalja, nenatančno iskanje vzorcev v nizih, problem $k$ razlik, algoritmi, analiza algoritmov
Place of publishing:Maribor
Place of performance:Maribor
Publisher:[K. Potočan]
Year of publishing:2022
Number of pages:VIII, 46 f.
PID:20.500.12556/DKUM-82204 New window
UDC:51:004.42(043.2)
COBISS.SI-ID:127463939 New window
Publication date in DKUM:28.10.2022
Views:437
Downloads:38
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:FNM
:
Copy citation
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:29.07.2022

Secondary language

Language:English
Title:A comparison of approximate string matching algorithms : na študijskem programu 2. stopnje Matematika
Abstract: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.
Keywords:strings, edit distance, approximate string matching, $k$ differences problem, algorithms, analysis of algorithms


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica