درخت پسوندی
در علوم رایانه، یک درخت پسوندی (درخت PAT، که با نام قدیمی‌تر درخت موقعیت نیز شناخته شده است) یک ترای شامل پسوندهای یک رشته‌ی داده شده به عنوان کلید و مکان آنها در رشته به عنوان مقدار است. درخت‌های پسوندی پیاده‌سازی سریع شمار زیادی از عملیات‌های رشته‌ای مهم را ممکن می‌سازند.
درخت پسوندی برای یک رشتهٔ formula_1، درختی است که یال‌های آن با رشته‌هایی برچسب خورده‌اند، به طوری که هر پسوند formula_1، متناظر با دقیقاً یک مسیر از ریشهٔ درخت به یک برگ است؛ بنابراین، این درخت، یک درخت مبنا برای پسوندهای formula_1 خواهد بود.
ساخت چنین درختی برای رشتهٔ formula_1 به زمان و فضای خطی بر حسب طول formula_1 نیاز دارد. وقتی این درخت ساخته شود، عملیات رشته‌ای، مانند یافتن یک زیررشته در formula_1، یافتن یک زیررشته با یک تعداد مجاز مشخص شده برای خطاها، یافتن تطابق‌ها برای یک الگوی عبارت باقاعده و غیره، می‌توانند به سرعت انجام شوند. درخت‌های پسوندی یکی از اولین راه حل‌های با زمان خطی برای مسئلهٔ بزرگترین زیررشته مشترک را نیز میسر ساخته‌اند. این افزایش سرعت‌ها هزینه‌ای دارند: ذخیره‌سازی یک درخت پسوندی برای یک رشته، معمولاً به فضای بیشتری نسبت به ذخیره‌سازی خود رشته نیاز دارد.
درخت پسوندی برای رشتهٔ formula_1 با طول formula_8 درختی است که در شرایط زیر صدق کند: از آنجایی که یک اینچنین درختی برای همهٔ رشته‌ها وجود ندارد، به انتهای formula_1، یک کاراکتر ترمینال (معمولاً با codice_1 نشان می‌دهند) که در الفبای اصلی وجود ندارد الحاق می‌شود. مثلا اگر سعی کنید برای رشته codice_2 آن را بسازید متوجه این نکته می‌شوید چون پسوند codice_3 پیشوند پسوند رشته کامل(codice_2) است. از آنجایی که تمامی گره‌های داخلی به جز ریشه شاخه شاخه می‌شوند، تعداد این گره‌ها حداکثر formula_12 خواهد بود و تعداد کل گره‌ها برابر خواهد بود با formula_13 (formula_8 برگ، formula_12 گره داخلی، و یک ریشه).
درخت پسوندی داده ساختاری است که با ساخت آن میتوان انواع مختلف پرسمان‌ها را پاسخ داد. ساخت آن با شرایطی در formula_16 قابل انجام است. یکی از کاربرد‌های اصلی آن جستجوی رشته است.
در حوضه بیوانفورماتیک یکی از مسائل معروف و اصلی پیدا کردن تعدادی الگوی‌ خوانده شده از ژنوم ( codice_5 ) در رشته طولانی‌تر( codice_6 ) است. ابعاد codice_5 ها در حد چند صد حرف و ابعاد ژنوم در حد میلیارد هستند. الگوریتم تطابق رشته با زمان خطی‌ برای یک الگو برای این مسئله مناسب نیستند و اگر روی تمام codice_5 ها به ترتیب اجرا کنیم بهینه نیست، چون تعداد آن‌ها بسیار زیاد است. ساختار درخت پسوندی طوری است که چون تمام پسوند‌های رشته در یک درخت پیشوندی ذخیره شده اند. با جستجوی یک codice_9 خاص از ریشه، تمام پسوند‌های codice_6 که با آن الگو شروع می‌شوند در زیردرخت راسی که در‌نهایت روی آن هستیم موجود اند. پس در پیچیدگی formula_17 روی هر الگو تکرار‌های آن پیدا می‌شوند. مقدار پیچیدگی زمانی کل هم formula_18 می‌شود.
به دلیل خواص خوبی که درخت‌های پسوندی دارند از آن‌ها برای ویرایش متن، جست‌وجوی متن آزاد، زیست‌شناسی محاسباتی و دیگر حوزه‌ها استفاده می‌شود. کاربردهای اولیه عبارتند از:درخت‌های پسوندی اغلب در حوزه‌ی بیوانفورماتیک استفاده می‌شوند، برای جست‌وجوی الگوها در دنباله‌های دی‌ان‌ای یا دنباله‌های پروتئینی (که می‌توان آنها را به عنوان رشته‌های بلندی از حروف در نظر گرفت). توانایی جست‌وجوی کارآمد با عدم تطابق ممکن است بزرگترین قدرت درخت‌های پسوندی باشد. این داده ساختارها همچنین در فشرده‌سازی داده‌ها استفاده می‌شوند؛ می‌توان برای پیدا کردن داده‌های تکراری و نیز در مرحله‌ی مرتب‌سازی تبدیل باروز-ویلر از آنها استفاده کرد. گونه‌هایی از طرح‌های فشرده‌سازی LZW از درخت‌های پسوندی استفاده می‌کنند (LZSS). در خوشه‌بندی درخت پسوندی (یک الگوریتم خوشه‌بندی که در برخی از موتورهای جست‌وجو استفاده می‌شود) نیز از درخت‌های پسوندی استفاده می‌شود.
اگر هر گره و یال را بتوان در فضای حافظه‌ای از formula_19 ذخیره کرد، می‌توان تمام درخت را در فضای حافظه‌ای از formula_20 ذخیره نمود. جمع طول تمامی رشته‌های روی همه‌ی یال‌ها در درخت از formula_21 است، اما هر یال می‌تواند با دو عدد به صورت مکان و طول زیررشته‌ای از formula_1 ذخیره شود؛ که در کل ذخیره‌ی همه‌ی یال‌ها حافظه‌ای از formula_20 اشغال می‌کند.
در اینجا دو روش برای ساخت درخت پسوندی را بررسی می‌کنیم.به عنوان یک روش ساده برای حالتی که طول رشته کوتاه است می‌توانیم از آن استفاده کنیم. کافی است تمام پسوند‌ها را در یک درخت پیشوندی درج کنیم.این الگوریتم ساخت درخت پسوندی را به تعداد فاز تقسیم می‌کند که هرکدام مراحلی دارند. در فاز formula_26 ام، برای اولین بار حرف formula_26 ام رشته را در نظر میگیریم و بعد از تمام شدن آن انتظار داریم تمام پسوند‌های زیررشته formula_28 در درخت درج شده باشند. در هر مرحله formula_29 از این فاز، formula_30 درج می‌شود. قبل از فاز formula_26 ام فاز formula_32 تمام شده، پس رشته formula_33 را داخل درخت جستجو می‌کنیم. ۳ حالت امکان دارد رخ دهد که در هر حالت طبق قانون خاصی ادامه می‌دهیم.
اگر همه فاز‌ها و مراحل را به شکل جستجوی جامع انجام دهیم چون formula_8 فاز formula_8 مرحله‌ای داریم و جستجوی درخت هم formula_16 است در نهایت الگوریتم از formula_41 می‌شود. برای کاهش آن از پیوند‌های پسوندی استفاده می‌کنیم.
تعریف پیوند پسوندی: فرض کنید رشته formula_42 در درخت وجود دارد و مسیر آن به راس formula_43 ختم می‌شود. رشته formula_44 ‌( formula_45 حرفی دلخواه از الفبا) هم موجود است و به راس formula_46 ختم می‌شود. به پیوندی از راس formula_46 به formula_43 پیوند پسوندی گفته می‌شود. در شکل اول این پیوند‌ها با خط‌چین نشان داده شده‌اند.
وقتی در حال انجام مرحله formula_29 فاز formula_26 هستیم، باید انتهای مسیر formula_33 را بدانیم. همچنین در مرحله formula_52 مسیر formula_53. قبل از انجام فاز formula_26 فاز formula_55 انجام شده یعنی دو رشته formula_33 و formula_53 در درخت هستند. formula_33 همان formula_59 است پس ما یک پیوند پسوندی از راس انتهایی formula_33 به formula_53 داریم پس به جای جستجو از ریشه می‌توانیم از آن استفاده کنیم. در این حالت صرفا زمان جستجو بهتر می‌شود تا به formula_21 برسیم.
برای اینکه پیچیدگی زمان formula_16 شود حتما باید رشته‌های روی یال را به صورت زیر‌بازه‌ای از رشته اصلی ذخیره کنیم. formula_64 با ذخیره دو عدد شروع و پایان.
قوانینی که به آن اشاره شد، در یک فاز به ترتیب عمل می‌کنند. یعنی اولین مراحل قانون ۱ عمل می‌کند،‌ بعد مدتی دومی و در آخر همیشه حالت سوم رخ خواهد داد. پس مثلا وقتی به حالت ۳ برسیم دیگر انجام آن فاز عملا تمام شده. وقتی یک برگ جدید میسازیم، همیشه برگ باقی می‌ماند صرفا امکان دارد یال آن به پدرش طولانی شود.(در حالت ۱) همچنین برای تمام برگ‌ها formula_65 یکسان می‌ماند. پس در هر فاز قانون یک در زمان ثابت با ذخیره با لیست همگانی از formula_65 های برگ‌ها قابل انجام است.
وقتی قانون دوم اجرا می‌شود هم، برگ جدید ایجاد می‌شود. و اگر یکبار در مرحله formula_29 اجرا شود، در تمامی فاز‌های بعدی این مرحله قانون اول رخ می‌دهد. پس در بدترین حالت formula_8 بار اجرا می‌شود چون formula_8 برگ داریم. پس طبق خاصیت‌های گفته شده مرتبه زمانی به formula_16 کاهش پیدا کرد.
یک نمونه از پیاده‌سازی آن به زبان formula_71 را در اینجا ببینید.
یک انتخاب مهم هنگام پیاده‌سازی یک درخت پسوندی، رابطه‌ی پدر-فرزندی بین گره‌ها است. استفاده از یک نوع لیست پیوندی به نام لیست خواهر و برادرها متداول‌ترین نوع است. هر گره یک اشاره‌گر به فرزند اولش و یک اشاره‌گر به فرزند بعدی در لیست فرزندهایی که عضو آنها است، دارد. پیاده‌سازی‌های دیگر با زمان اجرای کارآمد از جداول درهم‌سازی، آرایه‌های مرتب یا نامرتب، (آرایه پویا)، یا درخت‌های جست‌وجوی دودویی خود-متوازن استفاده می‌کنند.
فاکتورهای زیر در پیاده سازی مهم هستند:اگر formula_72 تعداد حروف الفبا باشد، هزینه‌ها به شرح زیر است:
formula_73
هزینه‌ی درج سرشکن است، و هزینه‌ی درهم‌سازی برای درهم‌سازی کامل داده شده است.