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 হলঃ

  

এখন এই স্ট্রিং গুলাকে যদি lexicographical ভাবে সর্ট করি তাহলে পাবঃ

   

এখন 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 তা ভাল করে শেখা ও বুঝা যায়।

এখনে স্ট্রিং এর প্রতিটা পজিশন থেকে শেষ পর্যন্ত সবগুলা 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 strings 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 করতে হবে।

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

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

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

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

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

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

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

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

Code:

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 সেভ করে রাখে।

Code:

উপরের 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

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