بخشی از مقاله
الگوریتمهای موثر برای رتبه بندی مکانی
چکیده
سریهای زمانی میتواند به عنوان یک توالی رتبهبندی ارائه شود که فراز و نشیبها با گذر زمان را نشان میدهد. در برخی از موارد کاربردی، یک نفر ممکن است بخواهد مسیر در دوره زمانی خاص را کشف یا آن را برای یک دوره زمانی جستجو کند. ما سه مشکل عمده را طبقهبندی کردیم: مشکل رتبهبندی مکانی، توالی رتبهبندی مکانی و تطبیق توالی رتبهبندی. دو مورد اول به بررسی رتبهبندیها در یک بخش از توالی زمان میپردازد و مورد آخر به جستجوی موقعیتهای تطبیق در سلسلهمراتب جستجو اشاره دارد. در تمام مشکلات فوقالذکر، ما الگوریتمهای گوناگون را با استفاده از ساختمان دادهای درختی شکل اصلاحشده ارائه میکنیم. ایجاد ساختمان بخشها زمان و فضا نیاز ندارد N .0(n log n) طول توالی رتبهبندی هدف است. زمان جستجو سه الگوریتم 0( log k)، 0(k) و 0( n log k) هستند. K اندازه توالی جستجو است.
واژههای کلیدی: ساختمان دادهها، رتبهبندی ترتیبی، بخش درختان، شیوه جزء به جزء، تطبیق رشته
-1 مقدمه
1
سریهای زمانی یک سری اندازهگیریها است که با نقاط زمانی که در فواصل ثابت و غیرثابت (متغیر) مطابقت دارد. اکثر دادههای سریهای زمانی با مقادیر اندازهگیری شده در فرم اعداد حقیقی پردازش میشوند. با توسعه تجهیزات کنترلی، تعداد مجموعه داده-ای سری زمانی و نقاط اندازهگیری به سرعت افزایش مییابند. بدین رو، اندازهگیریهای ترتیبی که تنها روابط منظم بین نقاط را توصیف میکنند، یک انتخاب خوب از نظر سادگی محسوب میشوند. به ویژه زمانی که آن یک سری طولانی و پیچیده میشود. یک سری از اندازهگیریها ترتیبی سری زمانی معمولی نامیده میشوند و اغلب به عنوان یک توالی رتبهبندی معمولی ارائه میشوند که یک شرح از روابط منظم بین نقاط است. برای مثال، یک سری از مقادیر اندازهگیری شده 24,3، 18,2، 27,5، 33,2 میتوانند به عنوان 2134 نشان داده شوند. آمارگیران سریها زمانی ترتیبی را با مشاهده پخش الگوهای معمولی 2]،[1 تحلیل میکنند. انتقال ترتیبی موجب کاهش سیستمهای پیچیده در ساختارهای داخلی اساسی میگردد. از طرف دیگر، دانشمندان کامپیوتر اندازهگیریهای ترتیبی برای تطبیق توالی ضبط معرفی میکنند به این خاطر که آن موثر است و درعینحال قوی و منحصربهفرد باقی میماند.[3] در انفورماتیک زیستی، اندازهگیریهای ترتیبی مجموعه داده خرد آرایههای سری زمانی به عنوان مسیر ژنها قلمداد میشوند و برای روابط موقت پیچیده به کار میروند.
گرچه، کاربردهای سریهای زمانی ترتیبی زیاد هستند ولی الگوریتمهای موثر و ساختمان دادهمخصوصاًبرای سری زمانی ترتیبی وجود ندارند. مشکل رتبهبندی جستجو آن است که به حداقل یک عنصر در یک طیف مشخص نیاز است8]،.[5 الگوریتم آن می-تواند به منظور کشف این عنصر با کمترین رتبهبندی در طیف استفاده گردد. اما آن نمیتواند کل سلسلهمراتب ترتیبی طیف را به طور موثر ارائه نماید. در این مقاله، ما بر یک عملکرد مهم با کمک موارد بالا که محاسبه رتبهبندی مکانی نامیده میشود متمرکز میشویم. ما با کمک یک توالی رتبهبندی طول n و یک طیف تعریفشده با موقعیت s و طول آن k رتبهبندی مکانی یک موقعیت خاص را به عنوان رتبه ترتیبی در میان مقادیر در طیف شرح میدهیم. برای مثال ، توالی رتبهبندی 13452 و طیف از شاخص 3 به 5 که 452 است، رتبهبندی مکانی شماره 5، 3 است. بدون پردازش درست، یک نفر نیاز به قیاس k-1 را دارد تا رتبهبندی مکانی برای یک عنصر مشخص تعیین گردد. برای انجام محاسبات سریعتر، ما الگوریتمی را معرفی میکنیم که در آن از ساختمان دادهای درختی شکل با نشانگرهای زیاد استفاده میشود. توجه داشته باشید که پیچیدگی زمان روند پیشپردازش که 0(log k) است، مانند انتقال اعداد حقیقی اندازهگیری شده در توالی رتبهبندی است. پیچیدگی فضا 0( n log n) هست.
برای کسب کل توالی رتبهبندی مکانی یک طیف، یک الگوریتم طبقهبندی زمان 0(k log k) نیاز است. با موجود بودن بخشهای اصلاحشده ما قادریم اعداد را در زمان 0(k) مجدد رتبهبندی نماییم که بهینه است چون به رتبهبندی مجدد اعداد k نیاز داریم. بیشتر، ما برای مشکل رتبهبندی مکانی از الگوریتم به منظور برطرف ساختن موارد ذیل استفاده میکنیم:
یک رویداد/ روند به عنوان توالی رتبهبندی و یک سری از اندازهگیریها تاریخی، قصد ما شناسایی دوره زمانی است که این رویداد در آن رخ داده است. این در واقع یک مشکل تطبیق است. برای حل این مشکل باید طیفی را پیدا کرد که توالی رتبهبندی مکانی دقاًیبا توالی رتبه بندی جستجو مطابقت داشته باشد. الگوریتمهای سنتی نمیتوانند مستقماًی به کار روند چون رتبهبندی مکانی در یک موقعیت خاص با تغییر طیف عوض میشود. با اتخاذ الگوریتم [9] kmp (اطلاعات بیشتر در بخش [10] (32 آن در زمان 0(n log k) اجرا میشود اگر زمان پردازش 0(n log n) در توالی رتبهبندی هدف از پیش انجام شده باشد. تعاریف رسمی مشکلات بالا به شرح ذیل است:
مشکل :1 رتبهبندی مکانی- LR(T,S,K,P) توالی رتبهبندی T با طول N، یک طیف از طول K با موقعیت اولیه S و یک موقعیت P در طیف، شماره رتبه در P در میان اعداد طیف قرار میگیرد.
مشکل:2 توالی رتبهبندی مکانی- LRS(T,S,K) یک توالی رتبهبندی T با طول N و یک طیف از طول K با موقعیت اولیه آن S، شناسایی LR(T,S,K,P) برای تمام موقعیتهای P در طیف.
مشکل:3 تطبیق توالی رتبهبندی- RSM(T.Q) یک توالی رتبهبندی هدف T با طول N و یک توالی رتبهبندی جستجو Q با طول K(K-N)، شناسایی تمام موقعیتهای S مثل LRS (T, S,K) دقاًیمانند Q است.
توجه داشته باشید که یک الگوریتم ساده وجود دارد که میتواند پاسخ LR(T,S,K,P) را سریع بدهد. گرچه زمان پیشپردازش 0(N2) است و آن نیاز برای ذخیره ساختمان به فضای 0(N2) نیاز دارد.
2
روند پیشپردازش به این ترتیب است: برای هر موقعیت I، از I تا 0 و از I تا N به ترتیب اسکن میشود. برای هر موقعیت اسکن شده J، تعداد موقعیتهای بین J و I ذخیره و محاسبه میشود که مقدار آنها بیشتر از مقدار I است.
به منظور اتمام روند پیشپردازش زمان و فضای 0(N2) نیاز است. سپس LR(T,S,K,P) باید S[P][S]+S[P][S+K-1]+1 باشد چون مقدار ترتیبی در میان یک طیف تعداد مقادیر بزرگتر از آن به علاوه 1 است.
در بخش 2، ما ساختمان دادهای درختی شکل پایه و ساختمان تابعه برای ذخیره اعداد را معرفی میکنیم. در بخش 3، مسئله نود-های پوششی استاندارد و اضافه شدن نشانگرهای اضافی برای شناسایی این نودها ارائه میشود. سپس از ساختارهای جدید برای حل مشکل توالی رتبهبندی محلی استفاده میشود. در بخش 4 ، ما از ایده فرکشنال کسکیدینگ برای حل مشکل رتبهبندی مکانی کمک میگیریم. در بخش 5، نوع دیگری از سریهای زمانی ترتیبی، توالی رتبهبندی پیشوندی برای حل مشکل تطبیق توالی رتبهبندی ارائه میشود. در انتها نتیجهگیری را خواهیم داشت
-2 نمودار درختی شکل بخش
در عوض ذخیره تمام طیفهای احتمالی برای تمام موقعیتهای احتمالی جستجو، ما از ساختمان دادهای درختی شکل اصلاحشده برای ذخیره رتبهبندیهای محلی استفاده میکنیم. نمودار درختی یک ساختمان دادهای درختی شکل است که در اصل به منظور ذخیره بخشها برای مشکل [11] مورد استفاده قرار میگیرد. (توضیحات بیشتر در مرجع .([12]12 ما از آن برای ذخیره اعداد ترتیبی در طیفها استفاده میکنیم. از نوع استاندارد آن برای ذخیره نودها و اعداد ترتیبی مربوطه استفاده میگردد. اعداد ترتیبی در نودها یک ساختار رتبهبندی نسبی از توالی رتبهبندی مکانی را تشکیل میدهند. رتبهبندی مجدد کل توالی رتبهبندی در طیف جستجو زحمت زیادی ندارد.
تعریف ساختمان دادهای درختی شکل در ذیل شرح داده میشود:
تعریف :1 مشخص کردن نمودار درختی در توالی رتبهبندی با طول n به عنوان نمودار درختی [1,n]، هر نود v با ریشه[s.t]
1. طیف [v.b,v.e]=[s,t] v طیفی است که v میپوشاند.
2. کلید [s+t]/2] v
3. نشانگر به اعداد ترتیبی .v مرتبط با طیف [s.t]
4. دو نشانگر: vچپ و vراست با ریشههای [s,v] و نمودار درختی(کلید1 + vو ( t به ترتیب
5. یک نشانگر v. Parent
شکل 1 مبین یک نمونه است.
شکل((1 درخت بخشی از توالی رتبه 17845263 گرههای سیاه و سفید هستند که پوشش متعارف از 7845
نظریه:1 نمودار درختی شکل n)،(1 میتواند در زمان 0 (n log n) ساخته شود و پیچیدگی فضا 0 (n log n) است.
اثبات: این نمودار در 0 (n log n) از نوع مرکب ایجاد میگردد. ارتباط یک نود با سایر نودها و اعداد ترتیبی مرتبط با هر نود نتایج ترکیب و ادغام زیرمجموعههای آن است.
در هر بخش از نمودار درختی،به منظور ذخیره اعداد ترتیبی به فضای 0 (n) نیاز است و سطوح 0 (log n) وجود دارد چون آن یک درخت جفتی متوازن هست. بدین رو، پیچیدگی فضا 0 (n log n) است.
3
-3 پوشش استاندارد
به منظور کسب رتبهبندی مکانی در یک طیف جستجو، ما نخست پوشش استاندارد آن در نمودار درختی را مییابیم. تعریف :2 پوشش استاندارد یک طیف [s,t] مجموعهای از نودهای v نمودار است:
1. U[v. b,v.E]= [s,t]
2. اگر V زیرمجموعه پوشش استاندارد باشد، سپس نود جفت آنَ V است جایی که Vو َ V تابع هم هستند.
برای مثال نودهای سیاه در شکل 1 نودهای پوشش استاندارد طیف هستند 2]، .[5
قابلذکر است که با طیف [s,t]، یک نود V sp که V sp. left.B ≤ S و Vsp.right.E ≥ t در نمودار درختی وجود دارد. در هر طرف Vsp،حداکثر یک نود وجود دارد که به پوشش استاندارد [s,t] تعلق دارد.
پیچیدگی زمان جستجوی سنتی برای پوشش استاندارد بسته به حجم نمودار 0 (log n) محدود میشود. برای کاهش پیچیدگی زمان 0 (log k)، ما نشانگرهای بیشتری اضافه میکنیم .R-Extent and l-Extent
تعریف :3
1. اگر V=Vparent.right باشد، آن حاکی از ALC (V) به عنوان زیرمجموعه اول v محسوب میشود که فرزند چپ والدینش
است. v.R -Extent= ALC (V)
2. اگر V=V. Parent. Left باشد، آن حاکی از ARC (V) به عنوان زیرمجموعه اول v است که فرزند سمت راست والدین
است. V.l-Extent=ARC (V).parent.left.
شکل 2 مبین نمونه است. ذکر این نکته مهم است که v.R-Extent.B= v.E+1، چون ALC(V).E=V.E و V.R-Extent، زیرمجموعه ALC(V) هست. به همین ترتیب،.V.L-Extent=v.b-1
ما R-Extent و L-Extent رافوراً پس از کشف نودهایی که موجب افزایش طیف از مرز چپ و راست میشوند را به ترتیب تعریف میکنیم.
شکل (2) تصویر از R_Extend و L_Extend اشاره گر
موضوع :2 اگر v یک نود با پوشش استاندارد [s,t] در سمت چپ نود Vsp آنگاه v.R-Extent.E ≤ t ، v.R-Extent همچنین یک نود با پوشش استاندارد از [s,t] است، v.L_Extend در سمت مخالف کار میکند اگر V در سمت راست Vsp باشد.
اثبات: واضح و مبرهن است که طیف v. R_Extend.range ⊂ [s, t] وجود دارد. اکنون ما اثبات میکنیم که علاوه بر v.r-Extent ،هیچ نود دیگری با پوشش استاندارد در طیف v.r-Extent وجود ندارد.
در سطوح بالاتر v.r-Extent، تنها زیرمجموعههای v.rExtent با طیف v.r-Extent همپوشانی دارند. آنها نودهایی با پوشش استاندارد نیستند چرا که آنها زیرمجموعههای v هستند. اگر یکی از این نودها دارای پوشش استاندارد باشد، v نمیتواند یک نود با پوشش استاندارد قلمداد گردد چون طیف v جزء زیرمجموعه نود v است.
در سطوح مشابه طیف نودها با یکدیگر هم پوشانی نمیکنند. هیچ نودی به جز v.r-Extentرا در این رنج را شامل گردد.
در سطوح پایینتر v.r-Extent، تنها توابع v.r-Extent با طیف v.r-Extent هم پوشانی میکنند. آنها نمیتوانند نودهایی با پوشش استاندارد باشند چون آنها شامل v.r-Extent هستند.
به منظور دستیابی به R-Extent و L-Extent ما طول توالی رتبهبندی n را به دو برابر n یا مساوی آن تغییر میدهیم. ما برگها را با اعداد فرد از چپ به راست و نودها داخلی را به وسیله شاخصهای زیرمجموعه آنها مشخص میکنیم.
4
