রাবিন-কার্প অ্যালগরিদম (Rabin-Karp Algorithm) একটি স্ট্রিং মেচিং অ্যালগরিদম যা প্যাটার্নের খোঁজ করার জন্য হ্যাশিং প্রযুক্তি ব্যবহার করে। এটি বিশেষ করে অনেকগুলো প্যাটার্নের জন্য একটি টেক্সটে খোঁজার ক্ষেত্রে কার্যকর।
অ্যালগরিদমের মূলনীতি
রাবিন-কার্প অ্যালগরিদম মূলত দুটি ধাপে কাজ করে:
হ্যাশিং: টেক্সট এবং প্যাটার্ন উভয়ের জন্য একটি হ্যাশ ফাংশন ব্যবহার করে একটি নির্দিষ্ট সংখ্যা (হ্যাশ ভ্যালু) তৈরি করে। এটি প্যাটার্নের দৈর্ঘ্যের উপর ভিত্তি করে টেক্সটের অংশগুলির জন্যও হ্যাশ ফাংশন তৈরি করে।
মেলানো: হ্যাশ ভ্যালুগুলি তুলনা করে, যদি দুইটি হ্যাশ ভ্যালু সমান হয় তবে স্ট্রিংগুলির সত্যিকার মিল যাচাই করতে হবে। কারণ হ্যাশিং এ সম্ভাব্য সংঘর্ষ ঘটতে পারে, তাই নিশ্চিতকরণের জন্য স্ট্রিংগুলি তুলনা করা হয়।
অ্যালগরিদমের প্রক্রিয়া
প্রাথমিককরণ:
- প্যাটার্নের এবং টেক্সটের প্রথম \( m \) (প্যাটার্নের দৈর্ঘ্য) চরিত্রের জন্য হ্যাশ ভ্যালু তৈরি করুন।
স্লাইডিং উইন্ডো:
- টেক্সটের উপর প্যাটার্নের হ্যাশ ভ্যালুর সাথে তুলনা করুন। যদি সমান হয়, তাহলে প্যাটার্নটি পাওয়া গেছে।
- যদি হ্যাশ ভ্যালুগুলি সমান হয়, তখন চরিত্রগুলি পরীক্ষা করুন (কারণ হ্যাশিং এ সংঘর্ষ হতে পারে)।
হ্যাশ আপডেট:
- পরবর্তী চরিত্রে স্লাইড করার জন্য হ্যাশ ভ্যালু আপডেট করুন। নতুন হ্যাশ ভ্যালু গণনা করতে পুরনো হ্যাশ ভ্যালু থেকে প্রথম চরিত্রটি বাদ দিন এবং নতুন চরিত্রটি যোগ করুন।
টাইম কমপ্লেক্সিটি
- গড় ক্ষেত্রে, সময় জটিলতা \( O(n + m) \) যেখানে \( n \) হল টেক্সটের দৈর্ঘ্য এবং \( m \) হল প্যাটার্নের দৈর্ঘ্য। তবে খারাপ ক্ষেত্রে \( O(nm) \) হতে পারে।
উদাহরণ
ধরি আমাদের টেক্সট "ABABDABACDABABCABAB" এবং প্যাটার্ন "ABABCABAB"।
- প্যাটার্নের জন্য হ্যাশ ভ্যালু গণনা করুন।
- টেক্সটের প্রথম 9টি চরিত্রের জন্য হ্যাশ ভ্যালু তৈরি করুন।
- এটি টেক্সটের মধ্যে স্লাইড করে যান এবং হ্যাশ ভ্যালুগুলি তুলনা করুন।
প্রয়োগ
রাবিন-কার্প অ্যালগরিদমের কিছু প্রধান প্রয়োগ হল:
স্ট্রিং অনুসন্ধান: বড় টেক্সটে একটি নির্দিষ্ট স্ট্রিং খুঁজতে ব্যবহৃত হয়, যেমন ডেটাবেস প্রশ্ন বা পাঠ্য সম্পাদক।
জেনারেটিভ এপ্লিকেশন: যেমন, ডেটা মাইনিং এ, যেখানে একই প্যাটার্ন পুনরাবৃত্তি খুঁজতে হয়।
প্যাটার্ন ম্যাচিং: অ্যালগরিদমের গতি এবং কার্যকারিতা নিশ্চিত করার জন্য বিগ ডেটা বিশ্লেষণে।
পাঠ্য এডিটিং টুলস: যেমন, টেক্সট এডিটর যেখানে ব্যবহারকারীরা দ্রুত স্ট্রিং খোঁজার জন্য অ্যালগরিদম ব্যবহার করে।
উপসংহার
রাবিন-কার্প অ্যালগরিদম একটি শক্তিশালী এবং কার্যকরী স্ট্রিং মেচিং অ্যালগরিদম যা বিশেষত হ্যাশিংয়ের সুবিধা ব্যবহার করে। এটি বিভিন্ন ক্ষেত্রে, বিশেষ করে যেখানে অনেক প্যাটার্নের সাথে কাজ করতে হয়, অত্যন্ত উপকারী।
Read more
