20.500.12556/RUL-160507 Vzporedni algoritmi za problem Levenshteinove razdalje in najdaljše skupno podzaporedje Parallel algorithms for the Levenshtein distance and the longest common subsequence problems Algoritmi za iskanje podobnosti med nizi so pomemben gradnik raznovrstnih aplikacij, ki so dandanes v vsakodnevni uporabi, od črkovalnikov do orodij za vodenje izvedb izvorne kode (npr. Git). Diplomsko delo opiše različne pristope optimizacije dveh tovrstnih algoritmov: Levenshteinove razdalje in najdaljšega skupnega podzaporedja, z uporabo koncepta večnitnosti in dveh temeljnih pristopov vzporejanja -- diagonalni in naprej-nazaj. Glavni cilj je časovna pohitritev algoritmov, ki jo ustrezno izmerimo in primerjamo nove implementacije z obstoječimi. Tako za diagonalni pristop kot za pristop naprej-nazaj razvijemo tudi prostorsko optimizirano metodo, ki je smiselna za uporabo pri velikih količinah vhodnih podatkov. Algorithms for finding similarity between strings are a building block of a large variety of modern applications, from spell checkers to version control tools (e.g. Git). This BSc thesis describes various approaches for optimizing two such algorithms: Levenshtein distance and Longest Common Subsequence, utilizing the concept of multithreading and two fundamental parallelization approaches -- diagonal and forward-backward. Main objective is improved execution time of said algorithms, which we measure and compare our results with existing implementations. For both diagonal and forward-backward approaches we develop an additional space optimization, which is useful for extremely large amounts of input data. vzporedni algoritmi večnitnost Levenshteinova razdalja najdaljše skupno podzaporedje dinamično programiranje parallel algorithms multithreading Levenshtein distance longest common subsequence dynamic programming true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2024-08-29 10:45:08 2024-08-29 10:45:10 2024-09-23 09:41:11 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37337 208457219 Bajic_Luka_-_Vzporedni_algoritmi_za_problem_Levenshteinove_razdalje_in_najdaljse_skupno_podzapor.pdf Bajic_Luka_-_Vzporedni_algoritmi_za_problem_Levenshteinove_razdalje_in_najdaljse_skupno_podzapor.pdf 1 D1FCC9B6252CB1CE39ED574EC5A28144 063776e8d880db79cbb6e5fcc31c22018a0cc7d46d419b3e96891aad4b9c50f2 c4b668a0-65e2-11ef-8f74-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=189212 Fakulteta za računalništvo in informatiko 0 0 0