| کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
|---|---|---|---|---|
| 6875659 | 1441979 | 2018 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Period recovery of strings over the Hamming and edit distances
ترجمه فارسی عنوان
بازیابی دوره‌ای رشته‌ها در فاصله‌های همینگ و ویرایش
همین الان دانلود کنید
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بازیابی دوره‌ای، تناوب تقریبی، فاصله همینگ، فاصله ویرایش
فهرست مطالب مقاله
چکیده
کلمات کلیدی
1.مقدمه
1.1 کار مرتبط
1.2 تعاریف و نمادها
1.3 تعاریف مسئله
1.4. نتایج ما
2. جعبه ابزار الگوریتم ها
2.1 "روش نامگذاری KMR" [29]
2.2. الگوریتم رای اکثریت (10)
2.3 بررسی ابتدایی [32،6]
2.4 ساخت پسوند درخت (28،30،31،18،40)
2.5 پرسش‌های LCP [8,20]
2.6 " Kangaroo Jumps" [22]
2.7 پیدا کردن اجرا در یک رشته [6]
2.8 برنامه نویسی پویا Wraparound [41,21]
2.9 الگوریتم تطبیق تقریبی Landau-Vishkin
3. بازیابی دوره در فاصله همینگ
3.1 مرحله 1: پیدا کردن یک زیررشته کاندیدای طول p
3.2 مرحله 2: بررسی ابتدایی
3.3 مرحله 3: فاصله همینگ را کمتر از آستانه بررسی کنید
3.4 پیچیدگی زمان و مکان
4. بازیابی دوره در فاصله ویرایش
4.1 کاهش تعداد کاندیداها
4.2 طرح کلی الگوریتم
4.3 یافتن زیررشته‌های نامزد
4.4 تأیید نامزدهای کوتاه
4.5 تأیید نامزدهای طولانی
4.6 پیچیدگی زمان و مکان
5. حداقل فاصله ویرایش بین رشته‌های دوره ای
کلمات کلیدی
1.مقدمه
1.1 کار مرتبط
1.2 تعاریف و نمادها
1.3 تعاریف مسئله
1.4. نتایج ما
2. جعبه ابزار الگوریتم ها
2.1 "روش نامگذاری KMR" [29]
2.2. الگوریتم رای اکثریت (10)
2.3 بررسی ابتدایی [32،6]
2.4 ساخت پسوند درخت (28،30،31،18،40)
2.5 پرسش‌های LCP [8,20]
2.6 " Kangaroo Jumps" [22]
2.7 پیدا کردن اجرا در یک رشته [6]
2.8 برنامه نویسی پویا Wraparound [41,21]
2.9 الگوریتم تطبیق تقریبی Landau-Vishkin
3. بازیابی دوره در فاصله همینگ
3.1 مرحله 1: پیدا کردن یک زیررشته کاندیدای طول p
3.2 مرحله 2: بررسی ابتدایی
3.3 مرحله 3: فاصله همینگ را کمتر از آستانه بررسی کنید
3.4 پیچیدگی زمان و مکان
4. بازیابی دوره در فاصله ویرایش
4.1 کاهش تعداد کاندیداها
4.2 طرح کلی الگوریتم
4.3 یافتن زیررشته‌های نامزد
4.4 تأیید نامزدهای کوتاه
4.5 تأیید نامزدهای طولانی
4.6 پیچیدگی زمان و مکان
5. حداقل فاصله ویرایش بین رشته‌های دوره ای
ترجمه چکیده
اگر P یک زیررشته از T و T[i]=T[i+p] برای همه‌ی (فرمول) و (فرمول) باشد، آنگاه یک رشته‌ی T به طول m در P به طول p متناوب است. کوتاه‌ترین پیشوند، یعنی P، دوره‌ی T نامیده می‌شود (به عنوان مثال، P=T[0..p-1]). در این مقاله ما مشکل بازیابی دوره‌ای را بررسی می‌کنیم. با توجه به یک رشته S به طول n، دوره(های) ابتدایی P را پیدا می‌کنیم به طوری که فاصله بین S و یک رشته T که به صورت متناوب در P است، زیر آستانه باشد. ما مشکل بازیابی دوره‌ای را از دو فاصله همینگ و فاصله ویرایش در نظر می‌گیریم. برای مورد فاصله‌ی همینگ، یک الگوریتم ارائه می‌کنیم، که در آن به صورت برای ارائه می‌شود. برای مورد فاصله ویرایش، (فرمول)و (فرمول) ، ما یک الگوریتم ارائه می‌دهیم.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A string T of length m is periodic in P of length p if P is a substring of T and T[i]=T[i+p] for all 0â¤iâ¤mâpâ1 and mâ¥2p. The shortest such prefix, P, is called the period of T (i.e., P=T[0..pâ1]). In this paper we investigate the period recovery problem. Given a string S of length n, find the primitive period(s) P such that the distance between S and a string T that is periodic in P is below a threshold Ï. We consider the period recovery problem over both the Hamming distance and the edit distance. For the Hamming distance case, we present an O(nlogâ¡n)-time algorithm, where Ï is given as ân(2+ϵ)pâ, for ϵ>0. For the edit distance case, Ï=ân(3.75+ϵ)pâ and ϵ>0, we provide an O(n4/3)-time algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 710, 1 February 2018, Pages 2-18
Journal: Theoretical Computer Science - Volume 710, 1 February 2018, Pages 2-18
نویسندگان
Amihood Amir, Mika Amit, Gad M. Landau, Dina Sokol,