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

۲۷۳ بازدید
آخرین به‌روزرسانی: ۲۰ تیر ۱۴۰۲
زمان مطالعه: ۴ دقیقه
آرایه پسوندی (Suffix Array) — به زبان ساده

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

997696

یک آرایه پسوندی را می‌توان از درخت پسوندی و در طول انجام پیمایش «جستجوی اول عمق» (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}

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

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

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

1// Naive algorithm for building suffix array of a given text 
2#include <iostream> 
3#include <cstring> 
4#include <algorithm> 
5using namespace std; 
6  
7// Structure to store information of a suffix 
8struct suffix 
9{ 
10    int index; 
11    char *suff; 
12}; 
13  
14// A comparison function used by sort() to compare two suffixes 
15int cmp(struct suffix a, struct suffix b) 
16{ 
17    return strcmp(a.suff, b.suff) < 0? 1 : 0; 
18} 
19  
20// This is the main function that takes a string 'txt' of size n as an 
21// argument, builds and return the suffix array for the given string 
22int *buildSuffixArray(char *txt, int n) 
23{ 
24    // A structure to store suffixes and their indexes 
25    struct suffix suffixes[n]; 
26  
27    // Store suffixes and their indexes in an array of structures. 
28    // The structure is needed to sort the suffixes alphabatically 
29    // and maintain their old indexes while sorting 
30    for (int i = 0; i < n; i++) 
31    { 
32        suffixes[i].index = i; 
33        suffixes[i].suff = (txt+i); 
34    } 
35  
36    // Sort the suffixes using the comparison function 
37    // defined above. 
38    sort(suffixes, suffixes+n, cmp); 
39  
40    // Store indexes of all sorted suffixes in the suffix array 
41    int *suffixArr = new int[n]; 
42    for (int i = 0; i < n; i++) 
43        suffixArr[i] = suffixes[i].index; 
44  
45    // Return the suffix array 
46    return  suffixArr; 
47} 
48  
49// A utility function to print an array of given size 
50void printArr(int arr[], int n) 
51{ 
52    for(int i = 0; i < n; i++) 
53        cout << arr[i] << " "; 
54    cout << endl; 
55} 
56  
57// Driver program to test above functions 
58int main() 
59{ 
60    char txt[] = "banana"; 
61    int n = strlen(txt); 
62    int *suffixArr = buildSuffixArray(txt,  n); 
63    cout << "Following is suffix array for " << txt << endl; 
64    printArr(suffixArr, n); 
65    return 0; 
66}

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

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

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

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

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

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

1// This code only contains search() and main. To make it a complete running 
2// above code or see https://ide.geeksforgeeks.org/oY7OkD 
3  
4// A suffix array based search function to search a given pattern 
5// 'pat' in given text 'txt' using suffix array suffArr[] 
6void search(char *pat, char *txt, int *suffArr, int n) 
7{ 
8    int m = strlen(pat);  // get length of pattern, needed for strncmp() 
9  
10    // Do simple binary search for the pat in txt using the 
11    // built suffix array 
12    int l = 0, r = n-1;  // Initilize left and right indexes 
13    while (l <= r) 
14    { 
15        // See if 'pat' is prefix of middle suffix in suffix array 
16        int mid = l + (r - l)/2; 
17        int res = strncmp(pat, txt+suffArr[mid], m); 
18  
19        // If match found at the middle, print it and return 
20        if (res == 0) 
21        { 
22            cout << "Pattern found at index " << suffArr[mid]; 
23            return; 
24        } 
25  
26        // Move to left half if pattern is alphabtically less than 
27        // the mid suffix 
28        if (res < 0) r = mid - 1; 
29  
30        // Otherwise move to right half 
31        else l = mid + 1; 
32    } 
33  
34    // We reach here if return statement in loop is not executed 
35    cout << "Pattern not found"; 
36} 
37  
38// Driver program to test above function 
39int main() 
40{ 
41    char txt[] = "banana";  // text 
42    char pat[] = "nan";   // pattern to be searched in text 
43  
44    // Build suffix array 
45    int n = strlen(txt); 
46    int *suffArr = buildSuffixArray(txt, n); 
47  
48    // search pat in txt using the built suffix array 
49    search(pat, txt, suffArr, n); 
50  
51    return 0; 
52}

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

Pattern found at index 2

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

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

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

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

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

^^

بر اساس رای ۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *