کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657187 | 688083 | 2005 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bit-parallel approximate string matching algorithms with transposition
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Bit-parallel approximate string matching algorithms with transposition Bit-parallel approximate string matching algorithms with transposition](/preview/png/9657187.png)
چکیده انگلیسی
Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(kâm/wân) algorithm of Wu and Manber, the O(â(k+2)(mâk)/wân) algorithm of Baeza-Yates and Navarro, and the O(âm/wân) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 3, Issues 2â4, June 2005, Pages 215-229
Journal: Journal of Discrete Algorithms - Volume 3, Issues 2â4, June 2005, Pages 215-229
نویسندگان
Heikki Hyyrö,