آرایه پسوندی
در علوم رایانه یک آرایهٔ پسوندی آرایه‌ای مرتب‌شده از همهٔ پسوندهای یک رشته است. این داده ساختار در الگوریتم‌های فشرده سازی و بیوانفورماتیک کاربرد دارد.
آرایهٔ پسوندی در سال ۱۹۹۰ توسط به‌عنوان جایگزینی ساده‌تر و همچنین از نظر حافظه بهینه تر برای درخت پسوندی معرفی شد. همچنین در سال ۱۹۸۷ به طور مستقل توسط Gaston Gonnet با نام PAT کشف شده بود. اگر رشتهٔ formula_1 را داشته باشیم، formula_2 را زیر رشتهٔ آن از حرف formula_3 ام تا حرف formula_4 ام تعریف می‌کنیم.
آرایهٔ پسوندی formula_5 برای رشتهٔ formula_6 یک آرایه از اعداد طبیعی است به طوری که خانه‌های آن نشان دهندهٔ نقاط شروع پسوندهای formula_6 به ترتیب الفبایی است، یعنی در خانهٔ formula_8 نقطهٔ شروع formula_3 امین کوچکترین پسوند رشتهٔ formula_6 قرار دارد. پس برای همهٔ formula_11 داریم:formula_12
اگر داشته باشیمcodice_1 formula_13 : در انتهای رشته یک حرف $ اضافه می‌کنیم که از نظر الفبایی کوچکترین حرف الفباست.
پسوندهای رشته به شرح زیر است:
پسوندها را به ترتیب الفبایی و به صورت نزولی مرتب می‌کنیم:
آرایهٔ پسوندی formula_5 شامل نقطهٔ شروع پسوندهای مرتب شده:
اگر در آرایهٔ پسوندی پسوندهای هر عدد را به صورت عمودی زیر آن بنویسیم بدین شکل خواهد بود: برای مثال،formula_15 برابر است با ۴ و نشان دهندهٔ ۴ امین پسوند در ترتیب الفبایی بین پسوندهای رشتهٔ formula_6 است که می‌شود codice_2 .
آرایهٔ پسوندی ارتباط نزدیکی با درخت پسوندی دارند:
و همچنین نشان داده شده است که هر الگوریتم درخت پسوندی را می‌توان با یک الگوریتم که از آرایهٔ پسوندی تغییر یافته (برای مثال با استفاده از آرایهٔ LCP) استفاده کند جایگزین کرد به طوری که همان مسئله را در همان پیچیدگی زمانی حل کند.
آرایهٔ پسوندی برای پیشرفت در بهینگی حافظه نسبت به درخت پسوندی معرفی شد: آرایه‌های پسوندی formula_17 عدد صحیح ذخیره می‌کنند و اگر فرض کنیم برای ذخیرهٔ هر عدد صحیح به formula_18 بایت نیاز داریم، یک آرایهٔ پسوندید در کل به formula_19 بایت حافظه نیاز خواهد داشت، که بسیار کمتر از formula_20ای است که برای ذخیرهٔ درخت پسوندی نیاز است.
با این حال در بعضی از کاربردها میزان حافظهٔ مورد نیاز برای آرایهٔ پسوندی می‌تواند هزینه بر باشد. درحالت کلی آرایهٔ پسوندی به formula_21 بیت حافظه نیاز دارد، در حالی که متن اصلی با الفبای formula_22 حرفی فقط به formula_23 بیت حافظه نیاز دارد. برای مثال در ژنوم انسان که formula_24 و formula_25 آرایهٔ پسوندی ژنوم به حافظه‌ای نزدیک به formula_26 برابر حافظهٔ مورد نیاز برای خود ژنوم نیاز دارد.
یک درخت پسوندی را می‌توان در formula_27 ساخت و با اجرای یک جستجو اول عمق در formula_27 به آرایهٔ پسوندی تبدیل کرد. پس الگوریتم‌هایی وجود دارند که می‌توانند آرایهٔ پسوندی را در زمان formula_27 بسازند.
راه حل سادهٔ ساخت آرایه‌های پسوندی استفاده از الگوریتم‌های مرتب‌سازی مقایسه‌ای است، این الگوریتم‌ها به formula_21 مقایسه نیاز دارد و با توجه به این که هر مقایسهٔ رشته‌ای به formula_27 زمان نیاز دارد، کل الگوریتم ساخت آرایهٔ پسوندی با این روش به formula_32 زمان نیاز خواهد داشت.
و الگوریتم‌های پیشرفته‌تر با استفاده از این موضوع که رشته‌هایی که باید مرتب شوند، رشته‌های دلخواهی نیستند و به هم ارتباط دارند روش‌هایی با زمان formula_33 معرفی می‌کنند.
از آرایهٔ پسوندی می‌توان برای پیدا کردن سریع همهٔ تکرارهای یک رشتهٔ formula_34 درون رشتهٔ formula_6 استفاده کرد. پیدا کردن همهٔ تکرارهای یک رشته formula_34 هم‌ارز است با پیدا کردن همهٔ پسوندهایی که با formula_34 شروع می‌شوند.
با توجه به ترتیب الفبایی پسوندها در آرایهٔ پسوندی این پسوندها پشت سر هم قرار گرفته‌اند و می‌توان آن‌ها را به راحتی با استفاده از ۲ بار اجرای جستجوی دودویی پیدا کرد. جستجوی اول نقطهٔ شروع بازه را پیدا می‌کند و جستجوی دوم نقطهٔ پایانی را مشخص می‌کند: با توجه به این که هر پسوند نیاز به مقایسهٔ formula_38 کارکتر دارد، پیدا کردن زیررشتهٔ formula_34 به طول formula_38 در رشتهٔ formula_6 به طول formula_17 در زمان formula_43 انجام می‌شود.
و این الگوریتم را می‌توان با استفاده از به formula_44 بهبود بخشید.