درخت پسوندی
From Wikipedia, the free encyclopedia
در علوم رایانه، یک درخت پسوندی (درخت PAT، که با نام قدیمیتر درخت موقعیت نیز شناخته شده است) یک ترای شامل پسوندهای یک رشتهی داده شده به عنوان کلید و مکان آنها در رشته به عنوان مقدار است. درختهای پسوندی پیادهسازی سریع شمار زیادی از عملیاتهای رشتهای مهم را ممکن میسازند.
درخت پسوندی برای یک رشتهٔ ، درختی است که یالهای آن با رشتههایی برچسب خوردهاند، به طوری که هر پسوند ، متناظر با دقیقاً یک مسیر از ریشهٔ درخت به یک برگ است؛ بنابراین، این درخت، یک درخت مبنا برای پسوندهای خواهد بود.
ساخت چنین درختی برای رشتهٔ به زمان و فضای خطی بر حسب طول نیاز دارد. وقتی این درخت ساخته شود، عملیات رشتهای، مانند یافتن یک زیررشته در ، یافتن یک زیررشته با یک تعداد مجاز مشخص شده برای خطاها، یافتن تطابقها برای یک الگوی عبارت باقاعده و غیره، میتوانند به سرعت انجام شوند. درختهای پسوندی یکی از اولین راه حلهای با زمان خطی برای مسئلهٔ بزرگترین زیررشته مشترک را نیز میسر ساختهاند. این افزایش سرعتها هزینهای دارند: ذخیرهسازی یک درخت پسوندی برای یک رشته، معمولاً به فضای بیشتری نسبت به ذخیرهسازی خود رشته نیاز دارد.