পাঠ্য অনুসন্ধান অ্যালগরিদম পাঠ্য প্রক্রিয়াকরণ এবং তথ্য পুনরুদ্ধারের একটি মৌলিক পদ্ধতি। এই অ্যালগরিদমটি আমাদের পাঠ্যের একটি বড় অংশের মধ্যে একটি সাবস্ট্রিং(বা প্যাটার্ন) এর ঘটনাগুলি সনাক্ত করতে এবং সনাক্ত করতে দেয়।
কিভাবে এটা কাজ করে
- একটি বৃহত্তর টেক্সট(বা নথি) এবং অনুসন্ধান করার জন্য একটি সাবস্ট্রিং দিয়ে শুরু করুন।
- পাঠ্যের প্রতিটি অক্ষরের মাধ্যমে ক্রমানুসারে পুনরাবৃত্তি করুন।
- পাঠ্যের একটি অংশের সাথে সাবস্ট্রিংটির তুলনা করুন যার দৈর্ঘ্য সাবস্ট্রিংয়ের সমান। যদি একটি মিল পাওয়া যায়, বর্তমান অবস্থান রেকর্ড করুন।
- পরবর্তী অবস্থানে যান এবং তুলনা চালিয়ে যান।
উদাহরণ
পাঠ্যটি বিবেচনা করুন: "আসুন এই পাঠ্যের মধ্যে একটি সাবস্ট্রিং অনুসন্ধান করা যাক কিভাবে অ্যালগরিদম কাজ করে।"
এবং অনুসন্ধান করার জন্য সাবস্ট্রিং: "সাবস্ট্রিং"
- অবস্থান 0 থেকে শুরু করুন।
Let'
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 1 এ যান।
et's
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 2 এ যান।
t's
"সাবস্ট্রিং" এর সাথে তুলনা করুন। কোন মিল নেই। - অবস্থান 3 এ যান।
's s
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 4 এ যান।
se
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 5 এ যান।
sea
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 6 এ যান।
earc
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 7 এ যান।
arch
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 8 এ যান।
rch
"সাবস্ট্রিং" এর সাথে তুলনা করুন। কোন মিল নেই। - অবস্থান 9 এ যান।
ch w
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 10 এ যান।
h wi
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 11 এ যান।
wit
"সাবস্ট্রিং" এর সাথে তুলনা করুন। কোন মিল নেই। - অবস্থান 12 এ যান।
with
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 13 এ যান।
ithi
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 14 এ যান।
thin
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - পজিশন 15 এ যান।
hinn
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 16 এ যান।
in t
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - 17 পজিশনে যান।
n th
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - 18 পজিশনে যান।
thi
"সাবস্ট্রিং" এর সাথে তুলনা করুন। কোন মিল নেই। - অবস্থান 19 এ যান।
this
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - 20 পজিশনে যান।
his
"সাবস্ট্রিং" এর সাথে তুলনা করুন। কোন মিল নেই। - অবস্থান 21 এ যান।
is t
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 22 এ যান।
s te
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 23 এ যান।
ubst
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 24 এ যান।
bstr
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - পজিশন 25 এ যান।
stre
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - 26 অবস্থানে যান।
trin
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল নেই. - অবস্থান 27 এ যান।
ring
"সাবস্ট্রিং" এর সাথে তুলনা করুন। মিল পাওয়া গেছে, রেকর্ড পজিশন 27।
সাবস্ট্রিং "সাবস্ট্রিং" পাঠ্যের মধ্যে 27 অবস্থানে পাওয়া যায়।
C++ এ উদাহরণ কোড
এই উদাহরণে, textSearch
ফাংশনটি পাঠ্যের মধ্যে সাবস্ট্রিং "সাবস্ট্রিং" এর অবস্থানগুলি খুঁজে পেতে ব্যবহৃত হয়। ফলাফলটি ম্যাচের শুরুর অবস্থান ধারণকারী একটি ভেক্টর হবে।