Parallelization of the Levenshtein distance algorithm

Typ: Artykuł

Liczba pobrań: 2082

Pobierz zasób

PDF

Cytuj

BibTeX EndNote

Tytuł: Parallelization of the Levenshtein distance algorithm
Wariant tytułu: Zrównoleglenie algorytmu odległości edycyjnej Levenshteina
Autor: Niewiarowski, Artur

Stanuszek, Marek
Opublikowane w: Technical Transactions
Numeracja: Y. 111, iss. 3-NP
Strony: 109-122
Data wydania: 2014
Miejsce wydania: Kraków
Wydawca: Wydawnictwo PK
Język: angielski
Słowa kluczowe: Levenshtein distance, Levenshtein-Damerau distance, edit distance, very large strings, parallel computing, threads, high performance computing, Microsoft .NET Framework 4.0, mono-project

odległość edycyjna Levenshteina oraz Levenshteina-Damerau, odległość edycyjna, duże ciągi tekstowe, obliczenia równoległe, wątki, obliczenia wysokiej wydajności, Microsoft .NET Framework 4.0, mono-project
Abstrakt: This paper presents a method for the parallelization of the Levenshtein distance algorithm deployed on very large strings. The proposed approach was accomplished using .NET Framework 4.0 technology with a specific implementation of threads using the System. Threading.Task namespace library. The algorithms developed in this study were tested on a high performance machine using Xamarin Mono (for Linux RedHat/Fedora OS). The computational results demonstrate a high level of efficiency of the proposed parallelization procedure.

Artykuł przedstawia metodę zrównoleglenia algorytmu analizy odległości edycyjnej Levenshteina dedykowaną bardzo dużym ciągom tekstowym. Zaproponowane rozwiązanie zostało zaimplementowane na platformie .NET Framework 4.0 z uwzględnieniem metod dostępnych w przestrzeni nazw System.Threading.Task. Zastosowane algorytmy przetestowano na komputerze wysokiej wydajności, w oparciu o narzędzia Xamarin Mono (dla SO Linux RedHat/ Fedora). Otrzymane wyniki pokazują znacząco zwiększoną wydajność obliczeń dla przedstawionych w artykule rozwiązań.
Wydział: Wydział Fizyki, Matematyki i Informatyki
Licencja: Licencja PK
Prawa dostępu: Zasób dostępny dla wszystkich