کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427737 | 686550 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Average complexity of backward q-gram string matching algorithms
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Many efficient string matching algorithms make use of q-grams and process the text in windows which are read backward. In this paper we provide a framework for analyzing the average case complexity of these algorithms taking into account the statistical dependencies between overlapping q-grams. We apply this to the q-gram Boyer–Moore–Horspool algorithm adapted to various string matching problems and show that the algorithm is optimal on average.
► We study the average case complexity of string matching algorithms that use q-grams.
► We take into account the statistical dependencies of overlapping q-grams.
► We show that q-gram Boyer–Moore–Horspool style algorithms are average optimal.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 11, 15 June 2012, Pages 433–437
Journal: Information Processing Letters - Volume 112, Issue 11, 15 June 2012, Pages 433–437
نویسندگان
Leena Salmela,