آرایه پسوندی (Suffix Array) – به زبان ساده

«آرایه پسوندی» (Suffix Array) یک آرایه مرتب شده از همه پیشوندهای یک رشته ورودی (رشته داده شده) است. تعریف آرایه پسوندی مشابه با «درخت پسوندی» (Suffix Tree) است. درخت پسوندی، یک درخت فشرده از همه پسوندهای یک متن داده شده محسوب می‌شود. هر الگوریتم مبتنی بر درخت پسوندی می‌تواند با یک الگوریتم جایگزین شود که از آرایه پسوندی بهبود یافته با اطلاعات اضافی استفاده می‌کند و مساله مشابهی را با پیچیدگی زمانی مشابهی حل می‌کند.

یک آرایه پسوندی را می‌توان از درخت پسوندی و در طول انجام پیمایش «جستجوی اول عمق» (Depth-First Search | DFS) از درخت پسوندی ساخت. در حقیقت، آرایه پسوندی و درخت پسوندی هر دو از روی یکدیگر با زمان خطی قابل ساخته شدن هستند. مزایای آرایه پسوندی نسبت به درخت پسوندی شامل استفاده بهینه‌تر از حافظه، الگوریتم‌های ساخت زمان خطی ساده‌تر (در مقایسه با الگوریتم Ukkonen’s Algorithm است) و میزان محلی‌گری کش بهبود یافته است.

مثال

Let the given string be "banana".

0 banana                          5 a
1 anana     Sort the Suffixes     3 ana
2 nana      ---------------->     1 anana  
3 ana        alphabetically       0 banana  
4 na                              4 na   
5 a                               2 nana

So the suffix array for "banana" is {5, 3, 1, 0, 4, 2}

روش ساده برای ساخت آرایه پسوندی

یک روش ساده برای ساخت آرایه پسوندی، ساخت آرایه همه پسوندها و سپس مرتب‌سازی آرایه است.

روش بیان شده، در ادامه پیاده‌سازی شده است.

خروجی قطعه کد بالا، به صورت زیر است.

Following is suffix array for banana
5 3 1 0 4 2

اگر فرض شود که از یک الگوریتم از درجه O(nLogn)‎ برای مرتب‌سازی استفاده شده است، پیچیدگی زمانی روش بالا برای ساخت آرایه پسوندی از درجه O(n₂Logn)‎ خواهد بود. مدت زمان صرف شده برای خود مرحله مرتب‌سازی از درجه O(n₂Log_n)‎ است، زیرا در هر مقایسه، مقایسه دو رشته انجام می‌شود و کار مقایسه، زمانی از درجه O(n)‎ را به خود تخصیص می‌دهد. الگوریتم‌های موثر متعددی برای ساخت آرایه پسوندی وجود دارند.

جستجوی الگو با استفاده از آرایه پسوندی

برای جستجوی الگو در متن، متن پیش‌پردازش می‌شود و یک آرایه پسوندی از متن ساخته می‌شود. با توجه به آنکه یک آرایه مرتب شده از همه پسوندها موجود است، می‌توان از «جستجوی دودویی» (Binary Search) برای جستجو استفاده کرد.

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

در ادامه، تابع جستجو ارائه شده است. توجه به این نکته لازم است که تابع همه وقوع‌های الگو را گزارش نمی‌دهد و تنها یکی از آن‌ها را اعلام می‌کند.

خروجی قطعه کد بالا، به صورت زیر است.

Pattern found at index 2

پیچیدگی زمانی تابع جستجوی بالا از درجه O(mLog_n)‎ است. الگوریتم‌های کاراتری نیز برای جستجوی الگو برای هنگامی که آرایه پسوندی ساخته شد، وجود دارند. در حقیقت، یک الگوریتم مبتنی بر آرایه پسوندی O(m)‎ برای جستجوی الگو وجود دارد.

کاربردهای آرایه پسوندی

آرایه پسوندی یک ساختار داده فوق‌العاده مفید است که در طیف وسیعی از مسائل قابل استفاده است. در ادامه، برخی از مسائل معروفی که آرایه پسوندی در آن‌ها قابل استفاده است بیان شده‌اند.

• جستجوی الگو
• پیدا کردن طولانی‌ترین زیررشته تکرار شده
• پیدا کردن طولانی‌ترین زیر رشته مشترک

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های برنامه‌نویسی پایتون
• آموزش تکمیلی برنامه‌نویسی پایتون
• مجموعه آموزش‌های داده‌کاوی و یادگیری ماشین
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
• آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس

^^