স্ট্রিং হ্যাশিং, রোলিং হ্যাশ এবং রবিন-কার্প এলগোরিদম (Rabin-Karp algorithm)

মনে করুন আপনাকে একটা প্রবলেম সলভ করতে দেয়া হলো এরকম-

একটা স্ট্রিং S আর একটা প্যাটার্ণ (সাবস্ট্রিং) p দেয়া আছে। S এর মধ্যে p কতবার আছে সেটা খুঁজে বের করতে হবে। 

আমি ধরে নিচ্ছি আপনি কোনো এলগোরিদম জানেন না। আপনি শুধু প্রোগ্রামিংয়ের ব্যাসিক কিছু কাজ পারেন, যেমন, স্ট্রিং কি জিনিস, লুপ কিভাবে চালায়, কিভাবে if-else ব্যবহার করে এসব জিনিস। তারপরও খুব সহজেই এই প্রবলেমটা আপনি সলভ করতে পারবেন। নীচের অংশ পড়ার আগে ৫ মিনিট একটু চিন্তা করে দেখতে পারেন আপনি আসলেই কোনো সল্যুশন বের করতে পারেন কিনা।

আপনার মাথায় যে সলুশনটা আসার সম্ভাবনা সবচাইতে বেশি সেটা হচ্ছে S এর প্রত্যেকটা ক্যারেক্টারের সাথে p এর প্রত্যেকটা ক্যারেক্টার ম্যাচ করে কিনা সেটা দেখতে দেখতে এগিয়ে যাওয়া। নীচের ছবির মত করে-

naive string matching

 

কোডে সলুশনটা হতে পারে এরকম-


//Let n is the length of string S[] and m is the length of pattern p[]

for(i=0;i<n;i++)
{
    for(j=0;j<m && i+j<n;j++)
    {
        if(S[i+j]!=p[j]) //mismatch any of the character
            break;       //break the inner loop
    }

    if(j==m)//match found
        //rest of the code
}

এটা যদি সত্যি আপনার মাথায় এসে থাকে তাহলে আপনি নিজেকে ছোট্ট করে একটা বাহবা দিতে পারেন, কারণ সল্যুশনটা সম্পূর্ণ সঠিক (যদিও কথা এখানেই শেষ না)।

এবার আমরা সামান্য একটু হিসেব করে দেখি যে আমাদের এই সল্যুশনটা কি পরিমাণ সময় নিতে পারে অর্থাৎ এটার কমপ্লেক্সিটি কত। আমরা একেবারে worst condition চিন্তা করলে দেখবো যেহেতু বাইরের লুপটা সর্বোচ্চ n বার এবং ভেতরের লুপটা প্রতিবারে সর্বোচ্চ m বার ঘোরার সম্ভাবনা আছে সুতরাং আমাদের এই কোডের কমপ্লেক্সিটি হওয়ার কথা O(n*m)। আমরা যখন কোনো একটা নরমাল টেক্সটের উপর আমাদের এই সল্যুশন কাজে লাগাবো তখন যদিও খুব বেশী সম্ভাবনা আছে ম্যাক্সিমাম সময়েই আমাদের প্যাটার্ণের সাথে মূল স্ট্রিংয়ের সবগুলো ক্যারেক্টার মিলবে না, সুতরাং ভিতরের লুপটা খুব বেশীবার ঘোরার আগেই প্রতিবার ব্রেক হয়ে যাবে, তারপরো আমরা এরকম একটা কেসকে worst condition হিসেবে চিন্তা করতে পারি যখন আমাদের স্ট্রিং S আর প্যাটার্ণ p এরকম-
S = “aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab” (length = 50)
p = “aab” (length = 3)

এখানে কিন্তু আমাদের সল্যুশনে টোটাল 50*3 = 150 বার লুপ ঘুরবে।

নতুন কোনো সল্যুশন খোঁজার আগে আমরা দেখি যে আমাদের কোডটাকেই আমরা আরেকটু এফিসিয়েন্ট করতে পারি কিনা।

তার আগে একটা ব্যাপার একটু বলে নেই। আচ্ছা ‘দুইটা স্ট্রিং একই কিনা’ এটার সাথে ‘দুইটা ইন্টিজার নাম্বার একই কিনা’ এটার পার্থক্য কি?
পার্থক্যটা হলো, দুইটা ইন্টিজার নাম্বার সমান কিনা এটা শুধুমাত্র একটা ‘=’ অপারেটর দিয়ে চেক করা যায় এবং এটা একটা সিঙ্গেল ক্যালকুলেশন। কিন্তু দুইটা স্ট্রিং সমান কিনা এটা সিঙ্গেল ক্যালকুলেশনে চেক করা যায় না, স্ট্রিংয়ের প্রত্যেকটা ক্যারেকটার বাই ক্যারেক্টার চেক করতে হয় এবং স্ট্রিং দুটোর লেংথ যদি হয়  n তাহলে সেখানে মূলত n টা সিঙ্গেল ক্যালকুলেশন হয়। (বুদ্ধিমান পাঠক হয়তো ভাবছেন, C++,python সহ কিছু ল্যাংগুয়েজে তো আমরা দুইটা String টাইপ অবজেক্টকে ‘=’ অপারেটর দিয়ে চেক করতে পারি। হ্যাঁ, তা পারি। কিন্তু সেটাও সিঙ্গেল অপারেশন না। আন্ডার দ্য হুড সেখানেও কমবেশী স্ট্রিং লেংথের সমান ক্যালকুলেশন হয়)

এখন আমরা এই বুদ্ধিটাকেই একটু কাজে লাগানোর চেষ্টা করবো।

যেই সাবস্ট্রিংগুলোকে আমরা প্রত্যেকবার কম্পেয়ার করার চেষ্টা করছি সেগুলোকে যদি আমরা একটা করে ইন্টিজার নাম্বার দিয়ে রিপ্রেজেন্ট করতে পারি তাহলে আমাদের Inner loop টা আর লাগবে না। সেখানে আমরা দুইটা সাবস্ট্রিংকে রিপ্রেজেন্ট করা দুইটা ইন্টিজার নাম্বারকে সিঙ্গেল অপারেশনেই চেক করতে পারবো। তার মানে আমাদের এলগোরিদম কমপ্লেক্সিটি O(n*m) থেকে কমে মোটামুটি O(n) হয়ে যাবে।

পুরো প্রসেসটা আরেকটু সহজ বাংলায় ভেঙ্গে ভেঙ্গে বলি।

প্রথম কাজ হচ্ছে একটা স্ট্রিংকে একটা ইন্টিজারে প্রকাশ করা। এ কাজটা করার জন্য আমাদের একটা হ্যাশ ফাংশন লাগবে। হ্যাশ ফাংশন কিভাবে কাজ করে সেটা জানা না থাকলে এই পোস্টটা দেখে আসতে পারেন।

স্ট্রিংকে ইন্টিজারে কনভার্ট করার হ্যাশ ফাংশনটাকে আমরা ম্যাথমেটিক্যালি এভাবে লিখতে পারি-

hash-function1

এটাকে যদি আমরা আরেকটু ব্যাখ্যা করে বলতে চাই তাহলে ব্যাপারটা হবে এরকম,

H(s) = ( s[0]*p(len-1) + s[1]*p(len-2) + …….. + s[len-1]*p) % M

যেখানে s[i] হচ্ছে স্ট্রিং s এর i-তম ক্যারেক্টার আর p এবং M হচ্ছে আমাদের ইচ্ছামত দুটি নাম্বার (সাধারণত p এবং M প্রাইম নাম্বার নেয়া হয়)। এখানে আমরা M দিয়ে কেন মড করছি সেটা একটু বলে নেয়া ভালো। আমরা জানি যে, ইন্টিজার নাম্বারের একটা লিমিট আছে, আর আমরা যেহেতু হ্যাশ ভ্যালুটাকে একটা ইন্টিজার হিসেবে চাচ্ছি সুতরাং ঐ লিমিটের বড় ভ্যালু আমরা হ্যাশ হিসেবে নিতে পারবো না। এখন আমাদের স্ট্রিংয়ের লেংথ যদি একটু বড় হয় তাহলে অবশ্যই আমরা অনেক বড় একটা নাম্বার পাবো। এজন্যই আমরা এমন একটা ভ্যালু (M) দিয়ে পুরো নাম্বারটাকে মড করে নিবো যাতে করে সেটা ইন্টিজার লিমিটের চেয়ে বড় না হয়। সেইফলি কাজ করার জন্য M = 109 + 9 এবং p = 999983 (largest prime below 106) নেয়া যেতে পারে। আরেকটা ব্যাপার হলো মড করার আগেই ভ্যালুটা অনেক বড় হয়ে ওভারফ্লো করতে পারে। সমস্যা নেই সেটার জন্যও আমাদের সল্যুশন আছে। আমরা মডুলার এরিথমেটিক(modular arithmetic) থেকে জানি যে,

(A*B)%M = ((A%M)*(B%M))%M 

(A+B)%M = ((A%M)+(B%M))%M

সুতরাং আমরা উপরের ইকুয়েশনটাকে এভাবেও লিখতে পারি।

H(s) = ( ((s[0]%M)*(p(len-1) %M))%M + ((s[1]%M)*(p(len-2)%M))%M+ …….. + ((s[len-1]%M)*(p0 %M))%M) % M

অনেক অনেক  %M দেখে ভয় পাবার কিছু নেই। কোড করতে গেলে জিনিসটা অনেক সহজে হয়ে যাবে। 🙂

এবার আমরা একটা উদাহরণে পুরো প্রসেসটা কিরকম হবে সেটা দেখার চেষ্টা করি। (আমরা আরো অপটিমাইজ করবো কিন্তু আগে আইডিয়াটা মাথায় ঢোকাতে হবে, তারপরে এটাকে এফিসিয়েন্ট করাটা সহজ হয়ে যাবে)

উপরের প্রথম ছবিটার মত করে মনে করি আমাদের স্ট্রিং S = ‘ACAABC’ এবং যে প্যাটার্ণটা খুঁজতে হবে সেটা p= ‘AAB’. M = 1009 এবং p = 93 (উদাহরণের জন্য এরকম নেয়া, কাজ করার জন্য উপরে বলা ভ্যালুর মত নেয়া ভালো হবে)।

এখন তাহলে প্যাটার্ণের জন্য হ্যাশ ভ্যালু হবে,

H(p) = (A*932 + A*931+ B*930) % 1009 = 229

এখন একই ভাবে আমরা এই স্ট্রিংয়ের প্রতিটা সাবস্ট্রিংয়ের হ্যাশ ভ্যালু বের করে সেই হ্যাশ ভ্যালুর সাথে প্যাটার্ণের হ্যাশ ভ্যালু তুলনা করে বলতে পারবো পরস্পর সমান কিনা।

hashing

তারমানে দেখা যাচ্ছে, আমরা হ্যাশ ভ্যালু বের করতে পারলে আমাদের আর ক্যারেক্টার বাই ক্যারেক্টার ম্যাচ করার দরকার পড়ছে না। শুধু হ্যাশ ভ্যালুগুলোর মধ্যেই ইন্টিজার ইকুয়ালিটি চেক করলেই হয়ে যাচ্ছে। যেমন উপরের ছবিতে আমাদের ৪ টা সাবস্ট্রিংয়ের জন্য মূলত ৪ টা সিঙ্গেল অপারেশন চালানো লাগবে। যেটা আমাদের প্রথমে বের করা পদ্ধতি থেকে অনেক দ্রুত কাজ করবে।

কিন্তু এখানে একটা ব্যাপার হলো আমাদের যদি প্রতিবার একটা সাবস্ট্রিংয়ের হ্যাশভ্যালু বের করার জন্য পুরো সাবস্ট্রিংটুকুর উপর লুপ চালিয়ে কাজটা করতে হয় তাহলে কিন্তু কোনো লাভ হলো না। কারণ তখনও আগের মতই প্রতিটা সাবস্ট্রিংয়ের হ্যাশ বের করতে O(m) কমপ্লেক্সিটি আসবে এবং পুরো স্ট্রিংয়ের জন্য তখন O(n*m) কমপ্লেক্সিটিই পাবো। তাহলে আর এত কষ্ট করে লাভ কি হলো?

আমরা যদি প্রতিটা সাবস্ট্রিংয়ের হ্যাশ করার কাজটায় কমপ্লেক্সিটি কমাতে পারি তাহলে আমরা বলতে পারবো যে আমাদের এই পদ্ধতিটা আগের চেয়ে ভালো। দেখি সেটা করা যায় কিনা।

প্রথমেই আমরা একটা ম্যাথমেটিক্যাল অবজারভেশন দেখি-
আমাদের প্রথম সাবস্ট্রিংটার জন্য অপারেশন ছিলো এরকম (অনেকগুলো %M দেয়া ইকুয়েশনটা মূলত ইমপ্লিমেন্টেশনের জন্য, ম্যাথমেটিক্যালি ওভাবে লেখা হয় না)

A * p2 + C * p1+ A * p0        (মডের পার্টটুকু আপাতত উহ্য রাখলাম)

=> A * p2 + (C * p1+ A * p0)

ঠিক পরের সাবস্ট্রিংয়ের জন্য আমাদের অপারেশন হবে-

C * p2 + A * p1+ A * p0      

=> (C * p1 + A * p0) * p + A * p0  

বোল্ড করা অংশটুকু দুটো অপারেশনেই একই। অর্থাৎ আমরা একই কাজ বার বার করছি, যেটা কমানোর সুযোগ আছে।

তারমানে প্রত্যেকটা সাবস্ট্রিংয়ের সাথে তার ঠিক পরের সাবস্ট্রিংয়ের মধ্যে যেহেতু কেবলমাত্র একটা করে ক্যারেক্টার ভিন্ন সুতরাং খুব সহজেই আমরা প্রথম সাবস্ট্রিংয়ের হ্যাশভ্যালু থেকে তার পরের সাবস্ট্রিংয়ের হ্যাশভ্যালু সিঙ্গেল অপারেশনে বের করতে পারবো। কিভাবে? আরেকবার খেয়াল করে দেখি-

H(substr0) = A * p2 + (C * p1+ A * p0)

common partH(substr0) – A * p2

H(substr1) = common part * p + A * p0

=>(H(substr0) – A * p2) * p + A * p0

তারমানে আমরা একটা জেনারেল ইকুয়েশন লিখতে পারি এরকম-

H(si) = (H(si-1) – s[i-1]*p(len-1)) * p + s[i+len-1]

অর্থাৎ আমরা শুধুমাত্র প্রথম সাবস্ট্রিংটার হ্যাশভ্যালু পুরো সাবস্ট্রিং থেকে বের করবো। দ্বিতীয় সাবস্ট্রিংয়ের হ্যাশভ্যালু বের করবো প্রথমটার উপর সিঙ্গেল অপারেশন চালিয়ে, তৃতীয় সাবস্ট্রিংয়ের হ্যাশভ্যালু বের করবো দ্বিতীয়টার উপর সিঙ্গেল অপারেশন চালিয়ে এবং এভাবে করেই বাকি সবগুলোর। এ পদ্ধতিটাকেই বলা হয় রোলিং হ্যাশ (Rolling hash)। কমন পার্টটুকু ঠিক রেখে একঘর একঘর করে আমাদের হ্যাশটা গড়িয়ে (roll) সামনে যাচ্ছে, এজন্যই রোলিং হ্যাশ। এবং মজার ব্যাপার হচ্ছে যেহেতু আমরা প্রত্যেকবার সিঙ্গেল অপারেশনেই আমাদের নতুন ভ্যালু পেয়ে যাবো তাই মোটের উপর আমাদের এলগোরিদম কমপ্লেক্সিটি এখন হবে O(n+m) ( প্যাটার্ণের জন্য O(m) )। 😀

একটা ব্যাপার লক্ষ্যণীয়, যেহেতু (H(si-1) – s[i-1]*p(len-1)) এখানে ভ্যালু নেগেটিভ হতে পারে সুতরাং আমরা যোগের মত (A%m – B%m)%m না করে (A%m-B%m+m)%m এভাবে করবো।

আমরা রোলিং হ্যাশসহ ফাইনালি যেই অবস্থায় এসে পৌঁছেছি এ পুরো এলগোরিদমটা রবিন-কার্প এলগোরিদম (Rabin-karp algorithm) নামে পরিচিত। পুরো প্রসেসটা যদি আপনি বুঝে থাকেন তাহলে এখন এটা কোডে ইমপ্লিমেন্টেশন করা তেমন কঠিন কিছু না।

একটা ব্যাপার এখানে বলে নেয়া ভালো, মনে করি সাবস্ট্রিংয়ের সাথে প্যাটার্ণ ম্যাচ করার  সময় হ্যাশভ্যালু আমরা একই পেলাম। এটা দেখে কি আমরা সরাসরি বলে দিতে পারবো যে দুটো স্ট্রিং আসলেই এক? না, আমরা আসলে পারবো না। কারণ, আমরা যদি মডুলাস না করে এই কাজটা করতে পারতাম-

H(s) = s[0]*p(len-1) + s[1]*p(len-2) + …….. + s[len-1]*p

তাহলে প্রতিটা ভিন্ন স্ট্রিংয়ের জন্য অবশ্যই ইউনিক হ্যাশ আমরা পেতাম। কিন্তু যেহেতু সেভাবে আমরা স্টোর করতে পারছি না, ইন্টিজার লিমিটের কারণে আমাদের পুরো ভ্যালুটাকে M দিয়ে মডুলাস করা লাগছে, সেহেতু খুবই সম্ভব যে হ্যাশভ্যালু মিললেও স্ট্রিং দুটো এক না। তারমানে, দুটো স্ট্রিংয়ের হ্যাশ ভ্যালু ম্যাচ করা মানে তারা এক হওয়ার সম্ভাবনা আছে, কিন্তু নাও হতে পারে। আগের হ্যাশিংয়ের পোস্টে যেমন বলেছিলাম collision এর ঘটনাটা, সেটা এখানে ঘটবে। তাহলে লাভটা কি হলো? লাভটা হলো যে যদি হ্যাশভ্যালু না মেলে তাহলে আমরা নিশ্চিত যে স্ট্রিং দুটো এক না। আর যদি মিলে যায় তাহলে আমাদের আবার আগের মতো করে শুধু এই সাবস্ট্রিংয়ের জন্য প্রত্যেকটা ক্যারেক্টার ম্যাচ করে নিশ্চিত হতে হবে স্ট্রিং দুটো আসলেই এক কিনা।

আরেকটা বুদ্ধি অবশ্য আছে, সেটা হলো double hash করা। তারমানে হলো আমরা যেমন একটা স্ট্রিংয়ের জন্য একটা M এবং p নিয়ে হ্যাশ বের করছিলাম এখন সেখানে দুইটা ভিন্ন M এবং p এরজন্য দুইটা হ্যাশভ্যালু বের করবো। আগের একই পদ্ধতিতেই হ্যাশভ্যালু বের করবো সুতরাং এলগোরিদমিক কমপ্লেক্সিটি তেমন একটা বাড়বে না। শুধু একটার পরিবর্তে দুইটা হ্যাশভ্যালুর জন্য কম্পেয়ার করতে হবে। দুইটা ভিন্ন স্ট্রিংয়ের জন্য দুইটা হ্যাশভ্যালুও মিলে যাওয়া একেবারেই অসম্ভব না, কিন্তু সেই সম্ভাবনা খুবই কম। সুতরাং ধরে নেয়া যায় যে মিলবে না। তারমানে double hash করলে আমাদের আর একেবারেই ক্যারেক্টার বাই ক্যারেক্টার ম্যাচ না করলেও চলবে।

শেষের আগে আরেকটা ছোট্টো বিষয় বলে নেই। যদি এরকম হয় যে আমাদের দুটো বেশ বড় স্ট্রিং দিয়ে বলা হলো দুটো স্ট্রিং একই কিনা দেখতে হবে। সেক্ষেত্রে কি আমরা হ্যাশিং ব্যবহার করবো?? না, একটু চিন্তা করলেই বোঝা যাবে এ ক্ষেত্রে হ্যাশিং করলে আমাদের মূলত কমপ্লেক্সিটি বাড়বে। কারণ দুটো স্ট্রিং একই কিনা এটা একেবারে স্বাভাবিকভাবে ক্যারেক্টার বাই ক্যারেক্টার চেক করলে O(n) কমপ্লেক্সিটি লাগবে। আর আমরা স্ট্রিং দুটোকে হ্যাশ করতে গেলে অনর্থক আরো কিছু অতিরিক্ত ক্যালকুলেশন করবো, যেটার কোনো দরকারই পড়বে না।

যদিও বিভিন্ন রকম স্ট্রিং ম্যাচিং এলগোরিদম আছে এবং প্রবলেমের ধরণের উপর ভিত্তি করে যেটা সবচাইতে এফিসিয়েন্ট সেটা ব্যবহার করা যায়। তবে এখানকার  rolling hash এর আইডিয়াটা বেশ চমৎকার এবং এটা আরো বিভিন্ন জায়গায়ও কাজে লাগে।

এটা নিয়ে ঘাঁটাঘাঁটি চলতে থাকুক, সামনে স্ট্রিং প্রসেসিংয়ের আরো কিছু এলগোরিদম নিয়ে পোস্ট দেয়ার ইচ্ছে আছে। 🙂

যাই হোক, এই পোস্ট শেষ করছি সলভ করার মত কিছু প্রবলেম লিস্ট দিয়ে। (সবগুলো প্রবলেম হয়তো রবিন-কার্প দিয়ে সলভ করা যাবে না, তবে অনেকগুলোই যাবে। কমেন্টে আরো কোনো প্রবলেম কেউ সাজেস্ট করলে এখানে যোগ করে দিবো।)

SPOJ

A2OJ

A story with strings

Timus OJ

 

Want to like or share?:
0

10 comments

  1. (modular arithmetic) থেকে জানি যে,
    (A*B)%M = ((A%M)+(B%M))%M
    এইটা (A*B)%M = ((A%M)*(B%M))%M হওয়ার কথা 🙂

  2. ভাইয়া , “সুতরাং আমরা যোগের মত (A%m – B%m)% না করে (A%m-B%m+m)%m এভাবে করবো। ” – লাইন টার এই টার্ম টা (A%m – B%m)% কি (A%m – B%m)%m হবে না ??

    1. p এবং M দুটোই প্রাইম নাম্বার নেয়াটা বেটার।

  3. আপনার লেখায় অনেক কঠিন বিষয় ও অনেক সহজে মাথায় ঢুকে যায়। “KMP-Algorithm” এর উপর একটা পোস্ট আশা করছি।

Leave a Reply

Your email address will not be published. Required fields are marked *