درخت پسوندی

درخت پسوندی برای رشتهٔ BANANA. هر زیر رشته با یک کاراکتر خاص $ خاتمه یافته است. ۶ مسیر از ریشه به برگ‌ها (که با مربع‌ها نمایش داده شده‌اند) متناظر با ۶ پسوند رشتهٔ BANANA می‌باشند. اعداد موجود در مربع‌ها بیانگر مکان شروع پسوند متناظر هستند. پیوندهای پسوندی به صورت خط چین رسم شده‌اند.

در علوم رایانه، یک درخت پسوندی (درخت PAT، که با نام قدیمی‌تر درخت موقعیت نیز شناخته شده است) یک ترای شامل پسوندهای یک رشته‌ی داده شده به عنوان کلید و مکان آنها در رشته به عنوان مقدار است. درخت‌های پسوندی پیاده‌سازی سریع شمار زیادی از عملیات‌های رشته‌ای مهم را ممکن می‌سازند.

درخت پسوندی برای یک رشتهٔ $S$، درختی است که یال‌های آن با رشته‌هایی برچسب خورده‌اند، به طوری که هر پسوند $S$، متناظر با دقیقاً یک مسیر از ریشهٔ درخت به یک برگ است؛ بنابراین، این درخت، یک درخت مبنا برای پسوندهای $S$ خواهد بود.

ساخت چنین درختی برای رشتهٔ $S$ به زمان و فضای خطی بر حسب طول $S$ نیاز دارد. وقتی این درخت ساخته شود، عملیات رشته‌ای، مانند یافتن یک زیررشته در $S$، یافتن یک زیررشته با یک تعداد مجاز مشخص شده برای خطاها، یافتن تطابق‌ها برای یک الگوی عبارت باقاعده و غیره، می‌توانند به سرعت انجام شوند. درخت‌های پسوندی یکی از اولین راه حل‌های با زمان خطی برای مسئلهٔ بزرگترین زیررشته مشترک را نیز میسر ساخته‌اند. این افزایش سرعت‌ها هزینه‌ای دارند: ذخیره‌سازی یک درخت پسوندی برای یک رشته، معمولاً به فضای بیشتری نسبت به ذخیره‌سازی خود رشته نیاز دارد.

تعریف

درخت پسوندی برای رشتهٔ $S$ با طول $n$ درختی است که در شرایط زیر صدق کند:

• دقیقا دارای n برگ است که از 1 تا n شماره‌گذاری شده‌اند.
• تمامی گره‌های داخلی (در بعضی موارد، به جز ریشه) حداقل دو فرزند دارند.
• هر یال با یک زیررشته‌ی ناتهی از $S$ برچسب خورده است.
• هیچ دو یالی که از یک گره بیرون می‌آیند نمی‌توانند برچسب‌هایی داشته باشند که با یک کاراکتر شروع می‌شوند.
• رشته‌ی بدست آمده از الحاق زیررشته‌های مسیر از ریشه تا برگ iاُم، معرف پسوند [i..n]$S$ برای هر i از 1 تا n است.

از آنجایی که یک اینچنین درختی برای همهٔ رشته‌ها وجود ندارد، به انتهای $S$، یک کاراکتر ترمینال (معمولاً با $ نشان می‌دهند) که در الفبای اصلی وجود ندارد الحاق می‌شود. مثلا اگر سعی کنید برای رشته abab آن را بسازید متوجه این نکته می‌شوید چون پسوند ab پیشوند پسوند رشته کامل(abab) است. از آنجایی که تمامی گره‌های داخلی به جز ریشه شاخه شاخه می‌شوند، تعداد این گره‌ها حداکثر $n-1$ خواهد بود و تعداد کل گره‌ها برابر خواهد بود با $n+(n-1)+1=2n$ ($n$ برگ، $n-1$ گره داخلی، و یک ریشه).

کاربردها

درخت پسوندی داده ساختاری است که با ساخت آن میتوان انواع مختلف پرسمان‌ها را پاسخ داد. ساخت آن با شرایطی در $O(n)$ قابل انجام است. یکی از کاربرد‌های اصلی آن جستجوی رشته است.

در حوزهٔ بیوانفورماتیک یکی از مسائل معروف و اصلی پیدا کردن تعدادی الگوی‌ خوانده شده از ژنوم ( read ) در رشته طولانی‌تر( Text ) است. ابعاد read ها در حد چند صد حرف و ابعاد ژنوم در حد میلیارد هستند. الگوریتم تطابق رشته با زمان خطی‌ برای یک الگو برای این مسئله مناسب نیستند و اگر روی تمام read ها به ترتیب اجرا کنیم بهینه نیست، چون تعداد آن‌ها بسیار زیاد است. ساختار درخت پسوندی طوری است که چون تمام پسوند‌های رشته در یک درخت پیشوندی ذخیره شده اند. با جستجوی یک pattern خاص از ریشه، تمام پسوند‌های Text که با آن الگو شروع می‌شوند در زیردرخت راسی که در‌نهایت روی آن هستیم موجود اند. پس در پیچیدگی $O(|pattern|)$ روی هر الگو تکرار‌های آن پیدا می‌شوند. مقدار پیچیدگی زمانی کل هم $O(n+\sum \nolimits _{p_{i}\in patterns}|p_{i}|)$ می‌شود.

به دلیل خواص خوبی که درخت‌های پسوندی دارند از آن‌ها برای ویرایش متن، جست‌وجوی متن آزاد، زیست‌شناسی محاسباتی و دیگر حوزه‌ها استفاده می‌شود. کاربردهای اولیه عبارتند از:

• جست‌وجوی رشته
• پیدا کردن بلندترین زیررشته‌ی تکراری
• پیدا کردن بلندترین زیررشته‌ی مشترک
• پیدا کردن زیر رشته‌های متمایز
• پیدا کردن بلندترین زیررشته‌ی پالیندروم در رشته

درخت‌های پسوندی اغلب در حوزه‌ی بیوانفورماتیک استفاده می‌شوند، برای جست‌وجوی الگوها در دنباله‌های دی‌ان‌ای یا دنباله‌های پروتئینی (که می‌توان آنها را به عنوان رشته‌های بلندی از حروف در نظر گرفت). توانایی جست‌وجوی کارآمد با عدم تطابق ممکن است بزرگترین قدرت درخت‌های پسوندی باشد. این داده ساختارها همچنین در فشرده‌سازی داده‌ها استفاده می‌شوند؛ می‌توان برای پیدا کردن داده‌های تکراری و نیز در مرحله‌ی مرتب‌سازی تبدیل باروز-ویلر از آنها استفاده کرد. گونه‌هایی از طرح‌های فشرده‌سازی LZW از درخت‌های پسوندی استفاده می‌کنند (LZSS). در خوشه‌بندی درخت پسوندی (یک الگوریتم خوشه‌بندی که در برخی از موتورهای جست‌وجو استفاده می‌شود) نیز از درخت‌های پسوندی استفاده می‌شود.

پیاده‌سازی

اگر هر گره و یال را بتوان در فضای حافظه‌ای از $\Theta (1)$ ذخیره کرد، می‌توان تمام درخت را در فضای حافظه‌ای از $\Theta (n)$ ذخیره نمود. جمع طول تمامی رشته‌های روی همه‌ی یال‌ها در درخت از $O(n^{2})$ است، اما هر یال می‌تواند با دو عدد به صورت مکان و طول زیررشته‌ای از $S$ ذخیره شود؛ که در کل ذخیره‌ی همه‌ی یال‌ها حافظه‌ای از $\Theta (n)$ اشغال می‌کند.

در اینجا دو روش برای ساخت درخت پسوندی را بررسی می‌کنیم.

• در زمان $O(n^{2})$

به عنوان یک روش ساده برای حالتی که طول رشته کوتاه است می‌توانیم از آن استفاده کنیم. کافی است تمام پسوند‌ها را در یک درخت پیشوندی درج کنیم.

• در زمان $O(n)$، Ukkonen's algorithm

این الگوریتم ساخت درخت پسوندی را به تعداد فاز تقسیم می‌کند که هرکدام مراحلی دارند. در فاز $i$ ام، برای اولین بار حرف $i$ ام رشته را در نظر میگیریم و بعد از تمام شدن آن انتظار داریم تمام پسوند‌های زیررشته $S[1..i]$ در درخت درج شده باشند. در هر مرحله $j$ از این فاز، $S[j..i]$ درج می‌شود. قبل از فاز $i$ ام فاز $i-1$ تمام شده، پس رشته $S[j..i-1]$ را داخل درخت جستجو می‌کنیم. ۳ حالت امکان دارد رخ دهد که در هر حالت طبق قانون خاصی ادامه می‌دهیم.

1. رشته کامل پیدا می‌شود و مسیر در یک راس برگ تمام می‌شود. در این حالت حرف $i$ ام به آخرین یال اضافه می‌شود و راس جدیدی هم نمی‌سازیم.
2. رشته کامل پیدا می‌شود و مسیر وسط یک یال تمام می‌شود و حرف بعدی رشته روی یال برابر $S[i]$ نیست یا مسیر روی یک راس درونی‌(غیر برگ) تمام می‌شود. اگر مسیر روی راس درونی تمام شود، یک برگ جدید ایجاد می‌کنیم. در حالت اول یک راس میانی و یک برگ جدید ایجاد می‌کنیم.
3. پسوند $S[j..i-1]$ پیدا می‌شود و مسیر روی یال تمام می‌شود در حالی که حرف بعدی آن مساوی $S[i]$ است. در این حالت هیچ بروزرسانی‌ای انجام نمی‌شود.

اگر همه فاز‌ها و مراحل را به شکل جستجوی جامع انجام دهیم چون $n$ فاز $n$ مرحله‌ای داریم و جستجوی درخت هم $O(n)$ است در نهایت الگوریتم از $O(n^{3})$ می‌شود. برای کاهش آن از پیوند‌های پسوندی استفاده می‌کنیم.

تعریف پیوند پسوندی: فرض کنید رشته $X$ در درخت وجود دارد و مسیر آن به راس $v$ ختم می‌شود. رشته $aX$ ‌( $a$ حرفی دلخواه از الفبا) هم موجود است و به راس $u$ ختم می‌شود. به پیوندی از راس $u$ به $v$ پیوند پسوندی گفته می‌شود. در شکل اول این پیوند‌ها با خط‌چین نشان داده شده‌اند.

وقتی در حال انجام مرحله $j$ فاز $i$ هستیم، باید انتهای مسیر $S[j..i-1]$ را بدانیم. همچنین در مرحله $j+1$ مسیر $S[j+1..i-1]$. قبل از انجام فاز $i$ فاز $i-1$ انجام شده یعنی دو رشته $S[j..i-1]$ و $S[j+1..i-1]$ در درخت هستند. $S[j..i-1]$ همان $S[j][j+1..i-1]$ است پس ما یک پیوند پسوندی از راس انتهایی $S[j..i-1]$ به $S[j+1..i-1]$ داریم پس به جای جستجو از ریشه می‌توانیم از آن استفاده کنیم. در این حالت صرفا زمان جستجو بهتر می‌شود تا به $O(n^{2})$ برسیم.

برای اینکه پیچیدگی زمان $O(n)$ شود حتما باید رشته‌های روی یال را به صورت زیر‌بازه‌ای از رشته اصلی ذخیره کنیم. $s[startIndex..endIndex]$ با ذخیره دو عدد شروع و پایان.

قوانینی که به آن اشاره شد، در یک فاز به ترتیب عمل می‌کنند. یعنی اولین مراحل قانون ۱ عمل می‌کند،‌ بعد مدتی دومی و در آخر همیشه حالت سوم رخ خواهد داد. پس مثلا وقتی به حالت ۳ برسیم دیگر انجام آن فاز عملا تمام شده. وقتی یک برگ جدید میسازیم، همیشه برگ باقی می‌ماند صرفا امکان دارد یال آن به پدرش طولانی شود.(در حالت ۱) همچنین برای تمام برگ‌ها $endIndex$ یکسان می‌ماند. پس در هر فاز قانون یک در زمان ثابت با ذخیره با لیست همگانی از $endIndex$ های برگ‌ها قابل انجام است.

وقتی قانون دوم اجرا می‌شود هم، برگ جدید ایجاد می‌شود. و اگر یکبار در مرحله $j$ اجرا شود، در تمامی فاز‌های بعدی این مرحله قانون اول رخ می‌دهد. پس در بدترین حالت $n$ بار اجرا می‌شود چون $n$ برگ داریم. پس طبق خاصیت‌های گفته شده مرتبه زمانی به $O(n)$ کاهش پیدا کرد.

یک نمونه از پیاده‌سازی آن به زبان $C++$ را در اینجا ببینید.

یک انتخاب مهم هنگام پیاده‌سازی یک درخت پسوندی، رابطه‌ی پدر-فرزندی بین گره‌ها است. استفاده از یک نوع لیست پیوندی به نام لیست خواهر و برادرها متداول‌ترین نوع است. هر گره یک اشاره‌گر به فرزند اولش و یک اشاره‌گر به فرزند بعدی در لیست فرزندهایی که عضو آنها است، دارد. پیاده‌سازی‌های دیگر با زمان اجرای کارآمد از جداول درهم‌سازی، آرایه‌های مرتب یا نامرتب، (آرایه پویا)، یا درخت‌های جست‌وجوی دودویی خود-متوازن استفاده می‌کنند.

فاکتورهای زیر در پیاده سازی مهم هستند:

• هزینه‌ی پیدا کردن یک فرزند با یک حرف داده شده
• هزینه‌ی درج یک فرزند
• هزینه‌ی پیدا کردن تمام فرزندان یک گره (تقسیم شده بر تعداد فرزندان در جدول زیر)

اگر $\sigma$ تعداد حروف الفبا باشد، هزینه‌ها به شرح زیر است:

${\begin{array}{r|lll}&{\text{Lookup}}&{\text{Insertion}}&{\text{Traversal}}\\\hline {\text{Sibling lists / unsorted arrays}}&O(\sigma )&\Theta (1)&\Theta (1)\\{\text{Bitwise sibling trees}}&O(\log \sigma )&\Theta (1)&\Theta (1)\\{\text{Hash maps}}&\Theta (1)&\Theta (1)&O(\sigma )\\{\text{Balanced search tree}}&O(\log \sigma )&O(\log \sigma )&O(1)\\{\text{Sorted arrays}}&O(\log \sigma )&O(\sigma )&O(1)\\{\text{Hash maps + sibling lists}}&O(1)&O(1)&O(1)\end{array}}$

هزینه‌ی درج سرشکن است، و هزینه‌ی درهم‌سازی برای درهم‌سازی کامل داده شده است.

جستار‌های وابسته

• درخت پیشوندی
• آرایه پسوندی
• الگوریتم تطابق رشته‌ها

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Suffix Tree». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۸ سپتامبر ۲۰۱۲.