موضوع مقاله: درخت پسوندی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت پسوندی | مقدمه: ۶ مسیر از ریشه به برگ‌ها (که با مربع‌ها نمایش داده شده‌اند) متناظر با ۶ پسوند رشتهٔ BANANA می‌باشند. | ## بخش 1: درخت پسوندی | در علوم رایانه، یک درخت پسوندی (درخت PAT، که با نام قدیمی‌تر درخت موقعیت نیز شناخته شده است) یک ترای شامل پسوندهای یک رشته‌ی داده شده به عنوان کلید و مکان آنها در رشته به عنوان مقدار است. درخت‌های پسوندی پیاده‌سازی سریع شمار زیادی از عملیات‌های رشته‌ای مهم را ممکن می‌سازند. درخت پسوندی برای یک رشتهٔ ، درختی است که یال‌های آن با رشته‌هایی برچسب خورده‌اند، به طوری که هر پسوند ، متناظر با دقیقاً یک مسیر از ریشهٔ درخت به یک برگ است؛ بنابراین، این درخت، یک درخت مبنا برای پسوندهای خواهد بود. وقتی این درخت ساخته شود، عملیات رشته‌ای، مانند یافتن یک زیررشته در ، یافتن یک زیررشته با یک تعداد مجاز مشخص شده برای خطاها، یافتن تطابق‌ها برای یک الگوی عبارت باقاعده و غیره، می‌توانند به سرعت انجام شوند. درخت‌های پسوندی یکی از اولین راه حل‌های با زمان خطی برای مسئلهٔ بزرگترین زیررشته مشترک را نیز میسر ساخته‌اند. این افزایش سرعت‌ها هزینه‌ای دارند: ذخیره‌سازی یک درخت پسوندی برای یک رشته، معمولاً به فضای بیشتری نسبت به ذخیره‌سازی خود رشته نیاز دارد. تعریف درخت پسوندی برای رشتهٔ با طول درختی است که در شرایط زیر صدق کند: دقیقا دارای n برگ است که از 1 تا n شماره‌گذاری شده‌اند. هیچ دو یالی که از یک گره بیرون می‌آیند نمی‌توانند برچسب‌هایی داشته باشند که با یک کاراکتر شروع می‌شوند. رشته‌ی بدست آمده از الحاق زیررشته‌های مسیر از ریشه تا برگ iاُم، معرف پسوند [i..n] برای هر i از 1 تا n است. از آنجایی که یک اینچنین درختی برای همهٔ رشته‌ها وجود ندارد، به انتهای ، یک کاراکتر ترمینال (معمولاً با $ نشان می‌دهند) که در الفبای اصلی وجود ندارد الحاق می‌شود. از آنجایی که تمامی گره‌های داخلی به جز ریشه شاخه شاخه می‌شوند، تعداد این گره‌ها حداکثر خواهد بود و تعداد کل گره‌ها برابر خواهد بود با ( برگ، گره داخلی، و یک ریشه). کاربردها درخت پسوندی داده ساختاری است که با ساخت آن میتوان انواع مختلف پرسمان‌ها را پاسخ داد. | ## بخش 2: درخت پسوندی | در حوزهٔ بیوانفورماتیک یکی از مسائل معروف و اصلی پیدا کردن تعدادی الگوی‌ خوانده شده از ژنوم ( read ) در رشته طولانی‌تر( Text ) است. الگوریتم تطابق رشته با زمان خطی‌ برای یک الگو برای این مسئله مناسب نیستند و اگر روی تمام read ها به ترتیب اجرا کنیم بهینه نیست، چون تعداد آن‌ها بسیار زیاد است. ساختار درخت پسوندی طوری است که چون تمام پسوند‌های رشته در یک درخت پیشوندی ذخیره شده اند. به دلیل خواص خوبی که درخت‌های پسوندی دارند از آن‌ها برای ویرایش متن، جست‌وجوی متن آزاد، زیست‌شناسی محاسباتی و دیگر حوزه‌ها استفاده می‌شود. کاربردهای اولیه عبارتند از: جست‌وجوی رشته پیدا کردن بلندترین زیررشته‌ی تکراری پیدا کردن بلندترین زیررشته‌ی مشترک پیدا کردن زیر رشته‌های متمایز پیدا کردن بلندترین زیررشته‌ی پالیندروم در رشته درخت‌های پسوندی اغلب در حوزه‌ی بیوانفورماتیک استفاده می‌شوند، برای جست‌وجوی الگوها در دنباله‌های دی‌ان‌ای یا دنباله‌های پروتئینی (که می‌توان آنها را به عنوان رشته‌های بلندی از حروف در نظر گرفت). توانایی جست‌وجوی کارآمد با عدم تطابق ممکن است بزرگترین قدرت درخت‌های پسوندی باشد. این داده ساختارها همچنین در فشرده‌سازی داده‌ها استفاده می‌شوند؛ می‌توان برای پیدا کردن داده‌های تکراری و نیز در مرحله‌ی مرتب‌سازی تبدیل باروز-ویلر از آنها استفاده کرد. در خوشه‌بندی درخت پسوندی (یک الگوریتم خوشه‌بندی که در برخی از موتورهای جست‌وجو استفاده می‌شود) نیز از درخت‌های پسوندی استفاده می‌شود. پیاده‌سازی اگر هر گره و یال را بتوان در فضای حافظه‌ای از ذخیره کرد، می‌توان تمام درخت را در فضای حافظه‌ای از ذخیره نمود. جمع طول تمامی رشته‌های روی همه‌ی یال‌ها در درخت از است، اما هر یال می‌تواند با دو عدد به صورت مکان و طول زیررشته‌ای از ذخیره شود؛ که در کل ذخیره‌ی همه‌ی یال‌ها حافظه‌ای از اشغال می‌کند. در زمان به عنوان یک روش ساده برای حالتی که طول رشته کوتاه است می‌توانیم از آن استفاده کنیم. در فاز ام، برای اولین بار حرف ام رشته را در نظر میگیریم و بعد از تمام شدن آن انتظار داریم تمام پسوند‌های زیررشته در درخت درج شده باشند. | ## بخش 3: درخت پسوندی | رشته کامل پیدا می‌شود و مسیر وسط یک یال تمام می‌شود و حرف بعدی رشته روی یال برابر نیست یا مسیر روی یک راس درونی‌(غیر برگ) تمام می‌شود. اگر همه فاز‌ها و مراحل را به شکل جستجوی جامع انجام دهیم چون فاز مرحله‌ای داریم و جستجوی درخت هم است در نهایت الگوریتم از می‌شود. تعریف پیوند پسوندی: فرض کنید رشته در درخت وجود دارد و مسیر آن به راس ختم می‌شود. همان است پس ما یک پیوند پسوندی از راس انتهایی به داریم پس به جای جستجو از ریشه می‌توانیم از آن استفاده کنیم. برای اینکه پیچیدگی زمان شود حتما باید رشته‌های روی یال را به صورت زیر‌بازه‌ای از رشته اصلی ذخیره کنیم. یعنی اولین مراحل قانون ۱ عمل می‌کند،‌ بعد مدتی دومی و در آخر همیشه حالت سوم رخ خواهد داد. وقتی یک برگ جدید میسازیم، همیشه برگ باقی می‌ماند صرفا امکان دارد یال آن به پدرش طولانی شود.(در حالت ۱) همچنین برای تمام برگ‌ها یکسان می‌ماند. پس در هر فاز قانون یک در زمان ثابت با ذخیره با لیست همگانی از های برگ‌ها قابل انجام است. و اگر یکبار در مرحله اجرا شود، در تمامی فاز‌های بعدی این مرحله قانون اول رخ می‌دهد. یک انتخاب مهم هنگام پیاده‌سازی یک درخت پسوندی، رابطه‌ی پدر-فرزندی بین گره‌ها است. هر گره یک اشاره‌گر به فرزند اولش و یک اشاره‌گر به فرزند بعدی در لیست فرزندهایی که عضو آنها است، دارد. پیاده‌سازی‌های دیگر با زمان اجرای کارآمد از جداول درهم‌سازی، آرایه‌های مرتب یا نامرتب، (آرایه پویا)، یا درخت‌های جست‌وجوی دودویی خود-متوازن استفاده می‌کنند. | ## جمع‌بندی | فاکتورهای زیر در پیاده سازی مهم هستند: هزینه‌ی پیدا کردن یک فرزند با یک حرف داده شده هزینه‌ی درج یک فرزند هزینه‌ی پیدا کردن تمام فرزندان یک گره (تقسیم شده بر تعداد فرزندان در جدول زیر) اگر تعداد حروف الفبا باشد، هزینه‌ها به شرح زیر است: هزینه‌ی درج سرشکن است، و هزینه‌ی درهم‌سازی برای درهم‌سازی کامل داده شده است.