کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657008 | 687687 | 2005 | 30 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Transposition invariant string matching
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Transposition invariant string matching Transposition invariant string matching](/preview/png/9657008.png)
چکیده انگلیسی
Given strings A=a1a2â¦am and B=b1b2â¦bn over an alphabet ΣâU, where U is some numerical universe closed under addition and subtraction, and a distance function d(A,B) that gives the score of the best (partial) matching of A and B, the transposition invariant distance is mintâU{d(A+t,B)}, where A+t=(a1+t)(a2+t)â¦(am+t). We study the problem of computing the transposition invariant distance for various distance (and similarity) functions d, including Hamming distance, longest common subsequence (LCS), Levenshtein distance, and their versions where the exact matching condition is replaced by an approximate one. For all these problems we give algorithms whose time complexities are close to the known upper bounds without transposition invariance, and for some we achieve these upper bounds. In particular, we show how sparse dynamic programming can be used to solve transposition invariant problems, and its connection with multidimensional range-minimum search. As a byproduct, we give improved sparse dynamic programming algorithms to compute LCS and Levenshtein distance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 56, Issue 2, August 2005, Pages 124-153
Journal: Journal of Algorithms - Volume 56, Issue 2, August 2005, Pages 124-153
نویسندگان
Veli Mäkinen, Gonzalo Navarro, Esko Ukkonen,