درخت پسوندی
در علوم رایانه، یک درخت پسوندی (درخت PAT، که با نام قدیمیتر درخت موقعیت نیز شناخته شده است) یک ترای شامل پسوندهای یک رشتهی داده شده به عنوان کلید و مکان آنها در رشته به عنوان مقدار است. درختهای پسوندی پیادهسازی سریع شمار زیادی از عملیاتهای رشتهای مهم را ممکن میسازند.
درخت پسوندی برای یک رشتهٔ
ساخت چنین درختی برای رشتهٔ
تعریف
درخت پسوندی برای رشتهٔ
- دقیقا دارای n برگ است که از 1 تا n شمارهگذاری شدهاند.
- تمامی گرههای داخلی (در بعضی موارد، به جز ریشه) حداقل دو فرزند دارند.
- هر یال با یک زیررشتهی ناتهی از برچسب خورده است.
- هیچ دو یالی که از یک گره بیرون میآیند نمیتوانند برچسبهایی داشته باشند که با یک کاراکتر شروع میشوند.
- رشتهی بدست آمده از الحاق زیررشتههای مسیر از ریشه تا برگ iاُم، معرف پسوند [i..n]برای هر i از 1 تا n است.
از آنجایی که یک اینچنین درختی برای همهٔ رشتهها وجود ندارد، به انتهای $
نشان میدهند) که در الفبای اصلی وجود ندارد الحاق میشود. مثلا اگر سعی کنید برای رشته abab
آن را بسازید متوجه این نکته میشوید چون پسوند ab
پیشوند پسوند رشته کامل(abab
) است. از آنجایی که تمامی گرههای داخلی به جز ریشه شاخه شاخه میشوند، تعداد این گرهها حداکثر
کاربردها
درخت پسوندی داده ساختاری است که با ساخت آن میتوان انواع مختلف پرسمانها را پاسخ داد. ساخت آن با شرایطی در
در حوضه بیوانفورماتیک یکی از مسائل معروف و اصلی پیدا کردن تعدادی الگوی خوانده شده از ژنوم ( read
) در رشته طولانیتر( Text
) است. ابعاد read
ها در حد چند صد حرف و ابعاد ژنوم در حد میلیارد هستند. الگوریتم تطابق رشته با زمان خطی برای یک الگو برای این مسئله مناسب نیستند و اگر روی تمام read
ها به ترتیب اجرا کنیم بهینه نیست، چون تعداد آنها بسیار زیاد است. ساختار درخت پسوندی طوری است که چون تمام پسوندهای رشته در یک درخت پیشوندی ذخیره شده اند. با جستجوی یک pattern
خاص از ریشه، تمام پسوندهای Text
که با آن الگو شروع میشوند در زیردرخت راسی که درنهایت روی آن هستیم موجود اند. پس در پیچیدگی
به دلیل خواص خوبی که درختهای پسوندی دارند از آنها برای ویرایش متن، جستوجوی متن آزاد، زیستشناسی محاسباتی و دیگر حوزهها استفاده میشود. کاربردهای اولیه عبارتند از:
- جستوجوی رشته
- پیدا کردن بلندترین زیررشتهی تکراری
- پیدا کردن بلندترین زیررشتهی مشترک
- پیدا کردن زیر رشتههای متمایز
- پیدا کردن بلندترین زیررشتهی پالیندروم در رشته
درختهای پسوندی اغلب در حوزهی بیوانفورماتیک استفاده میشوند، برای جستوجوی الگوها در دنبالههای دیانای یا دنبالههای پروتئینی (که میتوان آنها را به عنوان رشتههای بلندی از حروف در نظر گرفت). توانایی جستوجوی کارآمد با عدم تطابق ممکن است بزرگترین قدرت درختهای پسوندی باشد. این داده ساختارها همچنین در فشردهسازی دادهها استفاده میشوند؛ میتوان برای پیدا کردن دادههای تکراری و نیز در مرحلهی مرتبسازی تبدیل باروز-ویلر از آنها استفاده کرد. گونههایی از طرحهای فشردهسازی LZW از درختهای پسوندی استفاده میکنند (LZSS). در خوشهبندی درخت پسوندی (یک الگوریتم خوشهبندی که در برخی از موتورهای جستوجو استفاده میشود) نیز از درختهای پسوندی استفاده میشود.
پیادهسازی
اگر هر گره و یال را بتوان در فضای حافظهای از
در اینجا دو روش برای ساخت درخت پسوندی را بررسی میکنیم.
- در زمان
به عنوان یک روش ساده برای حالتی که طول رشته کوتاه است میتوانیم از آن استفاده کنیم. کافی است تمام پسوندها را در یک درخت پیشوندی درج کنیم.
- در زمان ، Ukkonen's algorithm
این الگوریتم ساخت درخت پسوندی را به تعداد فاز تقسیم میکند که هرکدام مراحلی دارند. در فاز
- رشته کامل پیدا میشود و مسیر در یک راس برگ تمام میشود. در این حالت حرف ام به آخرین یال اضافه میشود و راس جدیدی هم نمیسازیم.
- رشته کامل پیدا میشود و مسیر وسط یک یال تمام میشود و حرف بعدی رشته روی یال برابر نیست یا مسیر روی یک راس درونی(غیر برگ) تمام میشود. اگر مسیر روی راس درونی تمام شود، یک برگ جدید ایجاد میکنیم. در حالت اول یک راس میانی و یک برگ جدید ایجاد میکنیم.
- پسوند پیدا میشود و مسیر روی یال تمام میشود در حالی که حرف بعدی آن مساویاست. در این حالت هیچ بروزرسانیای انجام نمیشود.
اگر همه فازها و مراحل را به شکل جستجوی جامع انجام دهیم چون
تعریف پیوند پسوندی: فرض کنید رشته
وقتی در حال انجام مرحله
برای اینکه پیچیدگی زمان
قوانینی که به آن اشاره شد، در یک فاز به ترتیب عمل میکنند. یعنی اولین مراحل قانون ۱ عمل میکند، بعد مدتی دومی و در آخر همیشه حالت سوم رخ خواهد داد. پس مثلا وقتی به حالت ۳ برسیم دیگر انجام آن فاز عملا تمام شده. وقتی یک برگ جدید میسازیم، همیشه برگ باقی میماند صرفا امکان دارد یال آن به پدرش طولانی شود.(در حالت ۱) همچنین برای تمام برگها
وقتی قانون دوم اجرا میشود هم، برگ جدید ایجاد میشود. و اگر یکبار در مرحله
یک نمونه از پیادهسازی آن به زبان
یک انتخاب مهم هنگام پیادهسازی یک درخت پسوندی، رابطهی پدر-فرزندی بین گرهها است. استفاده از یک نوع لیست پیوندی به نام لیست خواهر و برادرها متداولترین نوع است. هر گره یک اشارهگر به فرزند اولش و یک اشارهگر به فرزند بعدی در لیست فرزندهایی که عضو آنها است، دارد. پیادهسازیهای دیگر با زمان اجرای کارآمد از جداول درهمسازی، آرایههای مرتب یا نامرتب، (آرایه پویا)، یا درختهای جستوجوی دودویی خود-متوازن استفاده میکنند.
فاکتورهای زیر در پیاده سازی مهم هستند:
- هزینهی پیدا کردن یک فرزند با یک حرف داده شده
- هزینهی درج یک فرزند
- هزینهی پیدا کردن تمام فرزندان یک گره (تقسیم شده بر تعداد فرزندان در جدول زیر)
اگر
هزینهی درج سرشکن است، و هزینهی درهمسازی برای درهمسازی کامل داده شده است.
جستارهای وابسته
منابع
- ↑ "Suffix Trees Tutorials & Notes | Data Structures". HackerEarth (به انگلیسی). Retrieved 2020-06-05.
- ↑ "Suffix tree. Ukkonen's algorithm". Codeforces (به انگلیسی). Retrieved 2020-06-05.
مشارکتکنندگان ویکیپدیا. «Suffix Tree». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۱۸ سپتامبر ۲۰۱۲.