درخت پسوندی

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

در علوم رایانه، یک درخت پسوندی (درخت PAT، که با نام قدیمی تر درخت موقعیت نیز شناخته شده است) یک ساختمان داده است که بیانگر پسوندهای یک رشته ی داده شده است به طوری که پیاده سازی سریع شمار زیادی از عملیات رشته ای مهم را ممکن می سازد. درخت پسوندی برای یک رشته ی S، درختی است که یال های آن با رشته هایی برچسب خورده اند، به طوری که هر پسوند S، متناظر با دقیقاً یک مسیر از ریشه ی درخت به یک برگ است. بنابراین، این درخت، یک درخت مبنا برای پسوندهای S خواهد بود. ساخت چنین درختی برای رشته ی S به زمان و فضای خطی بر حسب طول S نیاز دارد. وقتی این درخت ساخته شود، عملیات رشته ای مانند، یافتن یک زیررشته در S، یافتن یک زیررشته با یک تعداد مجاز مشخص شده برای خطاها، یافتن تطابق ها برای یک الگوی عبارت باقاعده و غیره، می توانند به سرعت انجام داده شوند. درخت های پسوندی یکی از اولین راه حل های با زمان خطی برای مساله ی بزرگترین زیررشته مشترک را نیز میسر ساخته اند. این افزایش سرعت ها هزینه ای دارند: ذخیره سازی یک درخت پسوندی برای یک رشته، معمولاً به فضای بیشتری نسبت به ذخیره سازی خود رشته نیاز دارد.

تعریف[ویرایش]

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

  • مسیرهای از ریشه به برگ ها با پسوندهای S در تناظر یک به یک باشند.
  • یال ها، رشته های غیرتهی را می سازند.
  • تمامی گره های داخلی (در بعضی موارد، به جز ریشه) حداقل دو فرزند دارند.

از آنجایی که یک اینچنین درختی برای همه ی رشته ها وجود ندارد، به انتهای S، یک کاراکتر ترمینال (معمولاً با $ نشان می دهند) که در رشته وجود ندارد الحاق می شود. این کار ما را مطمئن می سازد که هیچ پسوندی، پیشوند دیگری نیست و n گره ی برگ خواهیم داشت، برای هر پسوند S یک برگ. از آنجایی که تمامی گره های داخلی به جز ریشه شاخه شاخه می شوند، تعداد این گره ها حداکثر n - 1 خواهد بود و تعداد کل گره ها برابر خواهد بود با n + (n - 1) + 1 = 2n (n برگ، n - 1 گره داخلی، و یک ریشه). پیوندهای پسوندی یک ویژگی کلیدی برای الگوریتم های قدیمی خطی-زمانی که این گونه درخت ها را می سازند هستند، اگرچه بیسشتر الگوریتم های جدیدتر، که بر اساس الگوریتم Farach هستند، از پیوندهای پسوندی استفاده نمی‌کنند. در یک درخت پسوندی کامل، تمامی گره های داخلی غیر ریشه دارای یک پیوند پسوندی به یک گره ی داخلی دیگر هستند. اگر یک مسیر از ریشه به یک گره، رشته ی \chi\alpha را پیمایش کند، که \chi یک کاراکتر و \alpha یک رشته (که می تواند تهی هم باشد) باشد، آنگاه یک پیوند پسوندی از این گره به گره داخلی که بیانگر \alpha می باشد خواهیم داشت. برای مثال، پیوند پسوندی از گره ی ANA به گره ی NA در شکل بالا را در نظر بگیرید. پیوندهای پسوندی نیز در بعضی از الگوریتم هایی که بر روی این درخت ها اجرا می شوند مورد استفاده قرار می گیرند.

منابع[ویرایش]

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