کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657186 | 688083 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bit-parallel (δ,γ)-matching and suffix automata
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
(δ,γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P1â¦m and a text T1â¦n on an alphabet of integers, find the occurrences Pâ² of the pattern in the text such that (i) â1⩽i⩽m,|PiâPiâ²|⩽δ, and (ii) â1⩽i⩽m|PiâPiâ²|⩽γ. The problem makes sense for δ⩽γ⩽δm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mnlog(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mnlog(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 3, Issues 2â4, June 2005, Pages 198-214
Journal: Journal of Discrete Algorithms - Volume 3, Issues 2â4, June 2005, Pages 198-214
نویسندگان
Maxime Crochemore, Costas S. Iliopoulos, Gonzalo Navarro, Yoan J. Pinzon, Alejandro Salinger,