Suffix Array


Suffix Array কি? 

suffix array হল এমন একটা array যেখানে কোন স্ট্রিং এর সবগুলা suffix string এর index Sorted আকারে থাকবে। আরও সোজা করে বললে, একটা স্ট্রিং এর সাইজ যদি N হয় তাহলে তার N টা suffix string পসিবল। এখন suffix string গুলাকে যদি lexicographical ভাবে সর্ট করি তাহলে suffix starting এর যে index গুলা array আকারে পাব তাকেই suffix array বলা হচ্ছে। যেমন একটা স্ট্রিংঃ mississippi এর সবগুলা suffix string হলঃsuffix এখন এই স্ট্রিং গুলাকে যদি lexicographical ভাবে সর্ট করি তাহলে পাবঃ SortedSuffix এখন 10 7 4 1 0 9 8 6 3 5 2 array টাই হল suffix array. এই suffix array ডাটা স্ট্রাকচার ব্যাপকভাবে data compression, bioinformatics, string related, string matching problem ইত্যাদি কাজে ব্যবহার করা হয়। তাই suffix array implementation এর ভাল উপায় শিখা খুবই জরুরি।

Naive Implementation: 

প্রথমেই একটা ভাল জিনিস শেখার আগে তার naive/সাদাসিধে/বাংলা নিয়মটা ভাল করে বুঝে নেওয়া জরুরী। Naive Approach এ প্রবলেম কি বা সমস্যা সমাধান করতে গেলে কি হবে এইগুলা জানা থাকলে তাহলে Efficient way তা ভাল করে শেখা ও বুঝা যায়।

#include<bits/stdc++.h>
using namespace std;
vector< pair<string,int> >v;
int main()
{
    string s="mississippi";
    for(int i=0;i<s.size();i++)
    {
        v.push_back({s.substr(i),i});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i].second<<" "<<v[i].first<<endl;
    }
    return 0;
}

এখনে স্ট্রিং এর প্রতিটা পজিশন থেকে শেষ পর্যন্ত সবগুলা sub-string নিয়ে তার সাথে পজিশন সহ pair করে একটা ভেক্টরে রাখা হয়েছে। তারপর স্ট্রিং গুলাকে sort() ফাংশন কল করে lexicographical ভাবে সর্ট করা হয়েছে। এখন এই কোডের যদি Complexity এর কথা চিন্তা করতে যাই তাহলে, sort() ফাংশনে complexity যাচ্ছে Nlog(N). আর প্রতিটা স্ট্রিং compare এর জন্য যাচ্ছে N. সুতরাং পুরো complexity হল N²log(N). যেটা আমার স্ট্রিং সাইজ 3000 কাছাকাছি হলেই 1 sec. এর ভিতর সর্ট করে দিতে পারবে না। যদিও এই implementation সহজ, আলাদা কোন বেশি memory space লাগছে না। কিন্তু time complexity কারনে এইটাকে খুব ভাল বলা যাচ্ছে না, সুতরাং আমাদের এর চেয়ে ভাল কোন পদ্ধতি লাগবে। পরের অংশে আমরা সেই ভাল পদ্ধতি শিখার চেষ্টা করব।

A Better Approach:

আগের পদ্ধতিতে আমরা প্রতিটা পজিশনে পুরো suffix string টা রেখেছিলাম, যার জন্য compare করতে N complexity ছিল। এখন আমরা প্রতি পজিশনে tuple নামে 2 size এর একটা array রাখব। tuple array string এর 2 এর power সমান length এর rank সেভ রাখবে। জিনিসটা যদি সহজ করে বলি, তাহলে আমরা প্রথম suffix string গুলাকে তাদের প্রথম দুই character দিয়ে সর্ট করব। তাহলে tuple[0] এ থাকবে প্রথম character এর rank, তারপর tuple[1] এ থাকবে দ্বিতীয় character এর rank. তারপর আমরা প্রথম চার character দিয়ে সর্ট করব, এর জন্য tuple[0] এ থাকবে প্রথম দুই character এর rank, tuple[1] এ থাকবে পরের দুই character এর rank. এইভাবে 2 এর power এর সমান length দিয়ে সবগুলা sufffix সর্ট করে যাব। তাহলে আমার পুরো সর্ট করতে compare এর complexity যাচ্ছে log(N) আর sort() ফাংশনে Nlog(N). তাহলে আমার N²log(N) complexity Nlog²(N) কনর্ভাট হচ্ছে।

Implementation:

একটা স্ট্রিং এর সাইজ যদি N হয় তাহলে log2(N)+1 বার কম্পেয়ার হবে। Implementation step গুলো এমন হবে,
1. Rank All suffix string according to their first character:
2. for i 1 to log2(N)+1:
           set tuple for 2^i length string; tuple[0] will be first (2^i)/2 length string Rank &                    tuple[1] next (2^i)/2 length string Rank. if suffix string length<(2^i) then tuple[1]                will be -1;
           now sort according to tuple[0] & tuple[1];
           Then again assign new rank for (2^i) length string.

এখন ith step এ jth position এর কোন string এর প্রথম (2^i)/2 length এর string এর rank হবে previous step এর jth position এর rank এবং পরের (2^i)/2 length এর string এর rank হবে previous step এর (j+(2^i))th position এর rank. কারন previous step এর rank এ আমার (2^i)/2 এর সবগুলা string sort করে rank করা আছে।

এখন “mississippi” এই স্ট্রিং এর যদি suffix array বানাতে চাই তাহলে আমাকে প্রথম প্রতিটা suffix string এর প্রথম character অনুযায়ী rank করতে হবে।0.0

step 1: এখন প্রথম 2 length string এর জন্য tuple assign করতে হবে,1.1


tuple অনুযায়ী সর্ট করার পর, 2 length string গুলাকে আবার rank করতে হবে
1.2

step 2: এখন 4 length string গুলার tuple assign করতে হবে,
2.1

4 length string tuple অনু্যায়ী সর্ট করার পর, এখন এইগুলার নতুন rank assign করতে হবে
2.2

step 3: এখন 8 length string এর tuple assign করতে হবে,
3.1


8 length string সর্ট করার পর, এখন এইগুলার নতুন rank assign করতে হবে,
3.2

step 4: এখন 16 length string গুলার tuple assign করতে হবে,
4.1

এখন সর্ট করলেই মূল sorted suffix array পেয়ে যাব,
Suffix array

const int MAX =400004;
struct info
{
    int tup[2], indx; ///tup[0] = prev rank, tup[1] = new rank
    bool operator<(const info &a)const
    {
        return tup[0] != a.tup[0]? tup[0] < a.tup[0] : tup[1] < a.tup[1];
    }
}arr[MAX];
int Rank[18][MAX], step;
string text;

void build_suffix_array(void)
{
    int n = text.size(), jump;
    for(int j = 0; j < n; j++)
    {
        Rank[0][j] = text[j]; ///rank suffixes according to 1st char
        memset(arr[j].tup, 0,sizeof(arr[j].tup));
    }
    for(step = 1, jump = 1; jump <= n; step++, jump <<= 1)
    {
        for(int j = 0; j <=n; j++)
        {
            arr[j].indx = j;
            arr[j].tup[0] = Rank[step - 1][j]; /// what i was in prev step
            arr[j].tup[1] = j + jump < n? Rank[step - 1][j + jump] : -1;
        }
        sort(arr, arr + n);
        Rank[step][arr[0].indx] = 0;
        for(int j = 1; j < n; j++)
            Rank[step][arr[j].indx] = arr[j].tup[0] == arr[j - 1].tup[0] &&
            arr[j].tup[1] == arr[j - 1].tup[1] ? Rank[step][arr[j - 1].indx] : j;
    }
}

1. line 16 to 20 assign rank according to suffix strings first character.
2.line 21 to 34 main part
3. line 23 to 28 assign tuple jump/or 2 power length string tuple
4. line 29 calling sort function and sorted them according to tuple
5. line 30 to 33 assign new rank of jump/ 2 power length rank

Build LCP Array:

LCP array (Longest Common Prefix) suffix array একটি auxiliary data structure. এই array পাশাপাশি suffix array গুলার longest common prefix সেভ করে রাখে।

void build_LCP_array(void)
{
    LCP[0] = 0;
    int n = text.size(), i, j, id1, id2;
    for(i = 1; i < n; i++)
    {
        id1 = arr[i - 1].indx;
        id2 = arr[i].indx;
        LCP[i] = 0;
        for(j = step - 1; j >= 0; j--)
            if(Rank[j][id1] == Rank[j][id2] && Rank[j][id2])
            {
                LCP[i] += (1 << j);
                id1 += (1 << j);
                id2 += (1 << j);
            }
    }
}

উপরের suffix array এর কোড ভাল করে বুঝে থাকলে আশা করি এইটাও বুঝা যাবে, তাই আর এইটা নিয়ে বেশি কিছু লিখলাম না।
LCP array build এর complexity Nlog(N)

এই Nlog²(N) complexity algorithm কে NlogN এ কনর্ভাট করা যায়। যদি sort() function এর জায়গায় আমরা bucket sort/counting sort ব্যবহার করি তাহলে NlogN হয়ে যাবে। কারন bucket sort/counting sort এর complexity O(N)। পরবর্তিতে এইটার implementation এর একটা পোষ্ট দেয়ার চেষ্টা করব।

Download. এখান থেকে পুরো কোড ও আরও suffix array এর কিছু source পাওয়া যাবে।
source:
1.CodeChef
2.TopCoder

Practice Problem:

  1. Freedom of Choice
  2. Bacon’s Cipher
  3. Glass Beads
  4. Life Forms
  5. GATTACA
  6. DNA Sequencing

Special Thanks to Evan Hossain

কোন প্রকার ভুল থাকলে বা কোথায়ও বুঝতে সমস্যা হলে কমেন্টে জানানোর জন্য অনুরোধ করা হল।

Advertisements

About Tanvir Hasan Anick

I can read and write code, :)
This entry was posted in Data structure, Programming and tagged . Bookmark the permalink.

10 Responses to Suffix Array

  1. KN Roy says:

    ভাইয়া, ভালো হইছে। (y)

    Like

  2. faiem says:

    Nice post…Thanks

    Like

  3. কালো পাখি says:

    ভালো হইছে অনেক। যেটা শিখতে হয়তো অনেক সময় লাগতো সেটা খুব কম সময়েই সেখা গেল।
    আচ্ছা ভাই, if(Rank[j][id1]==Rank[j][id2] && Rank[j][id2]) এটার বদলে if(Rank[j][id1]==Rank[j][id2]) এটা দিলেই তো হওয়ার কথা। KMP নিয়ে লিখবেন আশা করি।

    Like

    • if(Rank[j][id1]==Rank[j][id2] && Rank[j][id2]) এর মানে হল যদি ম্যাচ থাকে তাহলে যোগ হবে ও পরবর্তি স্টেপে যাবে, else break হয়ে যাবে।
      হুম্ম KMP নিয়ে লেখার চেষ্টা করব।

      Like

  4. Anonymous says:

    related kichu problem link dile valo hoto

    Like

  5. nazmul sarker says:

    tuple assign er rank & position kivabe mark korlen clear bujlam na

    Like

  6. nazmul says:

    vai apnake onk gula thnx,ei blog na thakle suffix array shikha hoito na.
    vaia LCP ber korar part ta nie problem ace maybe.
    text=”abcabc” ei string er suffix array build korar por suffix array er 0 number index e thake text string er 3 number position mane “abc” and 1 number index e thake text string er 0 number position.LCP[1] er value show kre 1 but hoar kotha 3.”abc” and “abcabc” er longest prefix mathcing 3.

    for(j = step -1; j >= 0&&text[id1]&&text[id2]; j–){
    // if(i==1)cout<<id1<<" "<<id2<<" "<<j<<endl;
    while(Rank[j][id1] == Rank[j][id2] && Rank[j][id2]&&text[id1]&&text[id2]){
    LCP[i] += (1 << j);
    id1 += (1 << j);
    id2 += (1 << j);
    }
    }
    ei vabe submit kray amr code light oj te accept hoice.
    jodi vul bole thaki then sorry.

    Like

  7. nazmul says:

    thank u bro

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s