کشف تناوبی داده های سری زمانی به عنوان مسئله مهمی در بسیاری از برنامه های کاربردی می باشد. اکثر تحقیقات پیشین تمرکز خود را بر روی بررسی الگوهای تناوبی اسنکرون قرار داده و حضور الگوهای ناهمتراز را به دلیل مداخله پارازیت های تصادفی مد نظر قرار نمی دهد. در این مقاله، مدل انعطاف پذیرتری را در ارتباط با الگوهای تناوبی اسنکرون مطرح می کنیم که تنها درون توالی مد نظر قرار گرفته و وقوع آن ها به دلیل وجود این اختلالات تغییر می یابد. دو پارامتر min-rep و max-dis ،به کار گرفته می شوند تا به تعیین حداقل تعداد تکرارها بپردازیم که در هر بخش از ظهور الگوها غیرمختل و حداکثر اختلال بین دو بخش معتبرمتوالی، مورد نیاز می باشد. بعد از برطرف شدن این دو شرایط، بلندترین توالی معتبر الگو، برگشت داده می شود. یک الگوریتم دو مرحله ای طراحی می گردد تا در ابتدا به ایجاد دوره های بلقوه از طریق برش مبتنی بر مسافت به دنبال روش تکرار برای دسترسی و ایجاد اعتبار برای الگوهاو مکان یابی طولانی ترین توالی معتبر بپردازد. ما همچنین نشان می دهیم که این الگوریتم نه تنها پیچیدگی های زمانی طولی را با توجه به طول توالی ها ایجاد می کند بلکه دسترسی به بهره وری فضا دارد.

کلیدواژه: الگوهای تناوبی اسنکرون، روش مبتنی بر بخش، تناوب نسبی

ص 2

1. مقدمه 

تشخیص تناوبی در ارتباط با اطلاعات سری زمانی به عنوان یک مسئله چالش انگیز می باشد که دارای اهمیت مهمی در بسیاری از کاربردها می باشد.بیشتر تحقیقات گذشته در این دوره بر این مبنا می باشد که اختلالات در یک سری از تکرار الگوها، منجر به عدم همزمان سازی وقوع متوالی الگوها با توجه به رویدادهای گذشته نمی گردد. برای نمونه، "جو اسمیت هر روز روزنامه می خواند" به عنوان یک الگوی تناوبی می باشد. حتی اگر او هر از گاهی در صبحگاه روزنامه نخواند، چنین اختلالی این حقیقت را تحت تاثیر قرار نمی دهد که او در صبح چند روز متوالی روزنامه می خواند. به عبارت دیگر، این اختلالات تنها در ارتباط با وقوع مشکلات پیش می آید اما این موارد معمول تر از ورود پارازیت های تصادفی نمی باشد. به هر حال چنین فرضیاتی اغلب محدود کننده بوده از این رو ما ممکن است نتوانیم به تشخیص بعضی از الگوها بپردازیم اگر بعضی از این توالی ها به دلیل وجود پارازیت ها، دچار اختلال گردند. کاربردهای مربوط به پر کردن موجودی ها را مد نظر قرار دهید. پیشینه مربوط به سفارشات صورت های موجود به عنوان یک توالی مد نظر قرار می گیرد. تصور کنید، که فاصله زمانی بین اشباع داروها به طور نرمال، ماهانه باشد. شیوه های مربوط به اشباع سازی در شروع هر ماه قبل از شروع آنفولانزا مد نظر قرار می گیرد که در نهایت منتهی به فرایند اشباع سازی در هفته سوم می گردد. به این ترتیب اگر چه این بسامد اشباع سازی, در هر ماه تکرار می گردد، این زمان به سه هفته در ماه منتهی می گردد. از این رو، این مورد زمانی مد نظر قرار می گیرد که این الگوها قابل تشخیص بوده و این اختلالات در یک حد مطلوبی باشد.