ট্রাই বা প্রিফিক্স ট্রি ব্যবহার করে ডাটাবেস থেকে খুব সহজে স্ট্রিং খুজে বের করা যায়। ধরো একটা ফোনবুকে একটা শহরের সব মানুষের ফোন নম্বর রাখা আছে। শহরে মানুষ আছে হয়তো কয়েক লক্ষ্য, কিন্তু প্রতিটা মানুষের নাম সর্বোচ্চ ২০টা অক্ষর ব্যবহার করে লেখা যায়। আমরা এমন একটা ডাটা স্ট্রাকচার ব্যবহার করে নাম খুজবো যে নির্ভর করে শুধু মাত্র নামটিতে কয়টি অক্ষর আছে তার উপর। যেমন “Alice” নামটি খুজতে মাত্র ৫টি অপারেশন করা লাগবে ডাটাবেস যত বড়ই হোক না কেন।
এই লেখা পড়ার আগে লিংকড লিস্ট এবং রিকার্সন সম্পর্কে ধারণা থাকতে হবে।
ধরো তোমাকে একটা ডিকশনারী দেয়া হলো যেখানে নিচের শব্দগুলো আছে:
algo
algea
also
tom
to
এখন আমরা এই ডিকশনারিটাকে এমনভাবে মেমরিতে রাখতে চেষ্টা করবো যেন খুব সহজে কোনো একটা শব্দ খুজে পাওয়া যায়। একটা উপায় হলো শব্দগুলোকে সর্ট করে রাখা যেটা কাগজের ডিকশনারি গুলোতে রাখা হয়, তাহলে বাইনারি সার্চ করেই আমরা কোনো একটা শব্দ খুজে বের করতে পারবো। আরেকটা উপায় হলো প্রিফিক্স ট্রি বা সংক্ষেপে ট্রাই(trie) ব্যবহার করা। trie শব্দটা এসেছে “retrieval” শব্দটা থেকে। সেই হিসাবে এটার উচ্চারণ “ট্রি” হওয়ার কথা কিন্তু গ্রাফ থিওরীতে ট্রি এর আরো ব্যপক ব্যবহার আছে তাই এটাকে বলা হয় “ট্রাই” । প্রিফিক্স মানে হলো একটা স্ট্রিং এর শুরু থেকে কয়েকটা ক্যারেকটার নিয়ে নতুন স্ট্রিং তৈরি করা। যেমন blog এর প্রিফিক্স হলো b,bl,blo এবং blog।
শুরুতে আমাদের একটা রুট নোড ছাড়া কিছুই নেই।
এখন আমরা algo শব্দটাকে যোগ করবো। নিচের ছবিতে দেখো কিভাবে শব্দটা যোগ করা হয়েছে। রুট নোড থেকে আমরা একটা এজ দিবো যেই এজ এর নাম হবে “a”। তারপর নতুন তৈরি হওয়া নোড থেকে “l” নামের একটা এজ তৈরি করবো। এভাবে “g” আর “o” এজ দুইটাও তৈরি করবো। লক্ষ্য করো নোডে আমরা কোনো তথ্য রাখছিনা, খালি নোড থেকে এজ বের করছি।
এখন আমরা algea শব্দটা যোগ করতে চাই। রুট থেকে “a” নামের এজ দরকার, সেটা অলরেডি আছে, নতুন করে যোগ করা দরকার নাই। ঠিক সেরকম a থেকে l এবং l থেকে g তেও এজ আছে। তারমানে “alg” অলরেডি ট্রাই তে আছে, আমরা শুধু e আর a যোগ করবো।
also শব্দটাকে যোগ করবো এবার। রুট থেকে “al” প্রিফিক্স এরইমধ্যে আছে, শুধু “so” যোগ করতে হবে।
এবার “tom” যোগ করি। এবার রুট থেকে নতুন এজ তৈরি করতে হবে কারণ tom এর কোনো প্রিফিক্স আগে যোগ করা হয়নি।
এখন “to” শব্দটা যোগ করবো কিভাবে? “to” পুরোপুরি tom এর প্রিফিক্স তাই নতুন কোনো এজ যোগ করা দরকার নাই। আমরা যে কাজটা করতে পারি সেটা বলে নোডগুলোতে কিছু এন্ড-মার্ক বসানো। যেসব নোডে এসে অন্তত একটা শব্দ কমপ্লিট হয়েছে সেসব নোডে আমরা এন্ডমার্ক বসিয়ে দেই, ছবিতে ধূসর রঙ দিয়ে এন্ডমার্ক বোঝানো হয়েছে। আগের সব শব্দের জন্য এবং সেই সাথে নতুন শব্দ “to” এর জন্য এন্ডমার্ক বসালে ট্রাইটা এরকম দেখাবে:
নিশ্চয়ই বুঝতে পারছো এন্ডমার্কগুলো কেন বসিয়েছি। মার্ক দেখে সহজেই বোঝা যাচ্ছে কোন কোন শব্দ ট্রাইতে আছে। কোন ক্যারেকটার নিচ্ছি সেই তথ্য থাকবে এজ এ, আর এন্ডমার্কগুলো থাকবে নোড এ।
এভাবে শব্দগুলো রাখার সুবিধা কি? ধরো তোমাকে বলা হলো “alice” শব্দটা ডিকশনারিতে আছে কিনা বলতে। তুমি শুরু থেকে ট্রাই ধরে আগাতে থাকো। প্রথমে দেখো রুট থেকে a নামের এজ আছে নাকি, তারপর চেক করো a থেকে l নামের এজ আছে নাকি। এরপরে l থেকে i নামের এজ খুজে পাওয়া যাচ্ছেনা, তাই বলতে পারো alice শব্দটা নেই।
“alg” শব্দটা খুজতে দিলে তুমি root->a, a->l এবং l->g এজগুলো সবই খুজে পাবে, কিন্তু শেষ পর্যন্ত কোনো ধূসর নোডে যেতে পারবেনা, তারমানে alg ও ডিকশনারিতে নেই। “tom” খুজতে গেলে তুমি একটা ধূসর নোডে গিয়ে শেষ করবে তাই শব্দটা ডিকশনারিতে আছে।
ট্রাই ইমপ্লিমেন্ট করার সহজ একটা উপায় হলো লিংকড লিস্ট ব্যবহার করা। লিংকড লিস্ট, পয়েন্টার এসব শুনে ভয়ের কিছুই নেই, তুমি যদি লিংকলিস্ট ব্যবহার করতে অভ্যস্ত নাও হও আশা করি এই ইমপ্লিমেন্টেশনটা দেখে শিখে ফেলতে পারবে।আমাদের প্রতিটা নোডে ২টি জিনিস থাকবে:
১. এন্ড-মার্ক রাখার জন্য একটা ভ্যারিয়েবল।
২. প্রতিটা নোড থেকে a,b,c,……..,x,y,z ইত্যাদি নামের এজ তৈরি হতে পারে। আমরা প্রতিটা ক্যারেক্টারের জন্য একটা পয়েন্টার রাখবো। পয়েন্টারের সাহায্যে একটা নোড আরেকটার সাথে যোগ হবে। a নামের পয়েন্টার দিয়ে যোগ হলে বুঝতে হবে কারেন্ট নোড থেকে a নামের একটা এজ আছে। শুরুতে সবগুলো পয়েন্টার “নাল” থাকবে।
আমরা প্রথমেই নোডটা তৈরি করে ফেলি:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
struct node { bool endmark; node* next[26 + 1]; node() { endmark = false; for (int i = 0; i < 26; i++) next[i] = NULL; } } * root; int main() { root = new node(); return 0; } |
$next[]$ অ্যারের প্রতিটা এলিমেন্ট আরেকটা নোডকে পয়েন্ট করে। $next[0]$ দিয়ে নতুন নোডকে পয়েন্ট করা হলে সেই এজ এর নাম “$a$”, $next[1]$ এর জন্য এজ এর নাম “$b$”, $next[25]$ এর জন্য “$z$”। শুরুতে সবগুলো পয়েন্টার নাল। লক্ষ্য করো নোডের ভিতর একটা কনস্ট্রাক্টর “node()” তৈরি করেছি। যখনই নতুন নোড তৈরির জন্য $new\ node()$ কল করবো তখনই ভ্যারিয়েবলগুলোকে শূন্য বা নাল বানিয়ে দিবে। এটা না দিলে গার্বেজ ভ্যালু থাকতো। $root$ ভ্যারিয়েবলটা হলো আমাদের রুট নোড, উপরের ছবিগুলোতে লাল রঙ এর নোড। আসলে রুট একটা পয়েন্টার, যখন $root=new\ node();$ লাইনটা এক্সিকিউট হবে তখনই একটা নতুন নোড তৈরি করে $root$ যে মেমরি অ্যাড্রেসকে পয়েন্ট করে সেখানে অ্যাসাইন করে দেয়া হবে। এটাকে একটু গালভরা ভাষায় বলে $\text{instance}$ তৈরি করা। এবার আমাদের একটা ফাংশন লাগবে নতুন শব্দ ট্রাইতে যোগ করার জন্য:
1 2 3 4 5 6 7 8 9 10 11 |
void insert(char* str, int len) { node* curr = root; for (int i = 0; i < len; i++) { int id = str[i] - 'a'; if (curr->next[id] == NULL) curr->next[id] = new node(); curr = curr->next[id]; } curr->endmark = 1; } |
রুট ভ্যারিয়েবলটা আমাদের সবসময় দরকার হবে তাই “curr” এর মধ্যে সেটার কপি তৈরি করে কাজ করি। যেহেতু পয়েন্টার নিয়ে কাজ করছি তাই রুট থেকে নতুন এজ তৈরি করা আর “curr” থেকে নতুন এজ তৈরি করা একই কথা। আমরা এখন শুধু a-z নিয়ে কাজ করছি, তাই অ্যাসকি ভ্যালুগুলোকে 0-25 এ কনভার্ট করে নিবো ‘a’ এর অ্যাসকি ভ্যালু বিয়োগ করে। insert করা খুব সহজ, আমরা শুধু চেক করবো কারেন্ট নোড (curr) থেকে বর্তমানে যে ক্যারেকটারে আছি সেই নামের কোনো এজ আছে নাকি, না থাকলে নতুন নোড তৈরি করতে হবে। এরপরে সেই এজ ধরে আমরা পরের নোডে যাবো। সবার শেষ নোডটায় এন্ড-মার্ক true করে দিবো।
ইনসার্ট করার পর এখন সার্চ করবো। এটা আসলে ঠিক ইনসার্ট এর মতোই। পার্থক্য হলো যে এজটা দরকার সেটা না থাকলে তৈরি করে নিচ্ছিলাম, এখন এজ না থাকলে false রিটার্ণ করে দিবো।
1 2 3 4 5 6 7 8 9 10 11 |
bool search(char* str, int len) { node* curr = root; for (int i = 0; i < len; i++) { int id = str[i] - 'a'; if (curr->next[id] == NULL) return false; curr = curr->next[id]; } return curr->endmark; } |
লক্ষ্য করো সবকাজ ইনসার্ট এর মতোই করেছি। সবার শেষে লাস্ট নোডটার এন্ডমার্ক রিটার্ণ করে দিয়েছি। এন্ডমার্ক true হলে শব্দটা আছে, false হলে নাই।
আমাদের মূল কোড শেষ। আমরা এখন যেকোনো শব্দ ট্রাইতে যোগ করতে পারবো, আবার ট্রাই থেকে কোনো শব্দ খুজতে পারবো। অনেক সময় প্রতিটা টেস্টকেস এর জন্য ট্রাই তৈরি করতে গেলে মেমরি লিমিট নিয়ে সমস্যা হয়। তাই নিরাপদ উপায় হলো প্রতি কেস এর পর ব্যবহৃত মেমরি-সেল গুলোকে ডিলিট করে দেয়া। শুধু root ডিলিট করলে হবেনা, প্রতিটা নোড করতে হবে। আমরা সে জন্য একটা রিকার্সিভ ফাংশন লিখতে পারি:
1 2 3 4 5 6 7 |
void del(node* cur) { for (int i = 0; i < 26; i++) if (cur->next[i]) del(cur->next[i]); delete (cur); } |
এই ফাংশনটা প্রতিটা নোডে গিয়ে আগে চাইল্ডগুলোকে ডিলিট করে এসে তারপর নোডটাকে ডিলিট করে দিবে।
সম্পূর্ণ কোডটা এরকম:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
struct node { bool endmark; node* next[26 + 1]; node() { endmark = false; for (int i = 0; i < 26; i++) next[i] = NULL; } } * root; void insert(char* str, int len) { node* curr = root; for (int i = 0; i < len; i++) { int id = str[i] - 'a'; if (curr->next[id] == NULL) curr->next[id] = new node(); curr = curr->next[id]; } curr->endmark = true; } bool search(char* str, int len) { node* curr = root; for (int i = 0; i < len; i++) { int id = str[i] - 'a'; if (curr->next[id] == NULL) return false; curr = curr->next[id]; } return curr->endmark; } void del(node* cur) { for (int i = 0; i < 26; i++) if (cur->next[i]) del(cur->next[i]); delete (cur); } int main() { puts("ENTER NUMBER OF WORDS"); root = new node(); int num_word; cin >> num_word; for (int i = 1; i <= num_word; i++) { char str[50]; scanf("%s", str); insert(str, strlen(str)); } puts("ENTER NUMBER OF QUERY";); int query; cin >> query; for (int i = 1; i <= query; i++) { char str[50]; scanf("%s", str); if (search(str, strlen(str))) puts("FOUND"); else puts("NOT FOUND"); } del(root); //ট্রাইটা ধ্বংস করে দিলাম return 0; } |
কমপ্লেক্সিটি: প্রতিটা শব্দ খুজতে লুপ চালাতে হচ্ছে শব্দটার লেংথ পর্যন্ত, সার্চিং এর কমপ্লেক্সিটি O(length)। প্রতিটা শব্দ ইনসার্ট করার কমপ্লেক্সিটিও একই। মেমরি কতখানি লাগবে সেটা ডিপেন্ড করে ইমপ্লিমেন্টেশন এবং শব্দগুলোর প্রিফিক্স কতখানি ম্যাচ করে তার উপর। উপরের ইমপ্লিমেন্টেশন দিয়ে প্রায় 10^6 টা ক্যারেকটার ট্রাইতে ইনসার্ট করা যাবে (10^6 টা ওয়ার্ড নয়, ক্যারেকটার বা লেটার)।
তুমি চাইলে ট্রাই লিংকলিস্ট ছাড়া সাধারণ অ্যারে ব্যবহার করে ইমপ্লিমেন্ট করতে পারো, নিজে চেষ্টা করো!
ট্রাই এর কিছু ব্যবহার:
১. একটা ডিকশনারিতে অনেকগুলো শব্দ আছে, কোনো একটা শব্দ আছে নাকি নাই খুজে বের করতে হবে। এই প্রবলেমটা আমরা উপরের কোডেই সলভ করেছি।
২. ধরো তোমার ৩ বন্ধুর টেলিফোন নম্বর হলো “৫৬৭৮”, “৪৩২২”, “৫৬৭”। তুমি যখন প্রথম বন্ধুকে ডায়াল করবে তখন ৫৬৭ চাপার সাথে সাথে ৩য় বন্ধুর কাছে ফোন চলে যাবে কারণ ৩য় বন্ধুর নাম্বার প্রথম জনের প্রিফিক্স! অনেকগুলো ফোন নম্বর দেয়া আছে, বলতে হবে এরকম কোনো নম্বর আছে নাকি যেটা অন্য নম্বরের প্রিফিক্স। (UVA 11362)।
৩. একটা ডিকশনারিতে অনেকগুলো শব্দ আছে। এখন কোনো একটা শব্দ কয়বার “prefix” হিসাবে এসেছে সেটা বের করতে হবে। যেমন “al” শব্দটা উপরের ডিকশনারিতে ৩বার প্রিফিক্স হিসাবে এসেছে (algo, algea, also এই সবগুলো শব্দের প্রিফিক্স “al”)। এটা বের করার জন্য প্রতিটা নোডে একটা কাউন্টার ভ্যারিয়েবল রাখতে হবে, কোনো নোডে যতবার যাবে ততবার কাউন্টারের মান বাড়িয়ে দিবে। সার্চ করার সময় প্রিফিক্সটা খুজে বের করে কাউন্টারের মান দেখবে।
৪. মোবাইলের ফোনবুকে সার্চ করার সময় তুমি যখন কয়েকটা লেটার লিখো তখন সেই প্রিফিক্স দিয়ে কি কি নাম শুরু হয়েছে সেগুলো সাজেশন বক্সে দেখায়। এটা তুমি ট্রাই দিয়ে ইমপ্লিমেন্ট করতে পারবে?
৪. দু্টি স্ট্রিং এর “longest common substring” বের করতে হবে। (subsequence হলে ডিপি দিয়ে সহজে করা যায়, এখানে substring চেয়েছি)।
(হিন্টস: একটা স্ট্রিং এর শেষ থেকে এক বা একাধিক ক্যারেকটার নেয়া হলে সেটাকে স্ট্রিংটার সাফিক্স বলে, যেমন blog এর সাফিক্স g,og,log,blog। আর প্রতিটা substring ই কিন্তু কোনো না কোনো সাফিক্স এর প্রিফিক্স!! তাই সবগুলো সাফিক্সকে ট্রাইতে ইনসার্ট করলে কাজটা সহজ হয়ে যায়!)
৫. (অ্যাডভান্সড) সম্ভবত ২০১১তে ডেফোডিল ইউনিভার্সিটির ন্যাশনাল কনটেস্টে এসেছিলো প্রবলেমটা। একটা ডিকশনারি ইনপুট দেয়া থাকবে। প্রতিবার ডিকশনারির ২টা শব্দ কুয়েরি দিবে, বলতে হবে তাদের মধ্যে common prefix এর দৈর্ঘ্য কত। যেমন algo আর algea এর কমন প্রিফিক্স alg, দৈর্ঘ্য ৩। ট্রাইতে ডিকশনারিতে ইনসার্ট করে প্রতি কুয়েরিতে শব্দদুটি এন্ড-মার্ক থেকে LCA(lowest common ancestor) বের করে প্রবলেমটা সলভ করা যায়।
কিছু প্রবলেম:
https://leetcode.com/problems/search-suggestions-system/
UVA 10226
(UVA 11362 Phonebook)
UVA 11488 Hyper prefix sets
POJ 2001 Shortest Prefix
POJ 1056
হ্যাপি কোডিং!
ফেসবুকে মন্তব্য
Powered by Facebook Comments
Uva 11488 এর প্রবলেম নামটা ভুল আসছে ।
ধন্যবাদ, ঠিক করে দিয়েছি :-/ ।
ভাইয়া , সব শেষের পিকচার এ tom এর o এর কালার মনে হয় হলুদ হবে(বর্ণনা অনুযায়ী ) ।
না সবুজই হবে। “যেসব নোডে এসে অন্তত একটা শব্দ কমপ্লিট হয়েছে সেসব নোডে আমরা এন্ডমার্ক বসিয়ে দেই, ছবিতে সবুজ রঙ হলো এন্ডমার্ক।” শেষে আমরা “to” যোগ করসি তাই o এজ এর নিচের নোড সবুজ হবে। কোন লাইনে তোমার কনফিউশন হচ্ছে জানাও।
দুঃখিত ভাইয়া , আমার বুঝার ভুল ছিল ।
ধন্যবাদ ভাইয়া , এত সহজে বুঝানোর জন্য ।
ভাইয়া, ট্রাইই ইমপ্লিমেন্ট করলে সেটা কি মেমরি লিমিটের মধ্যে রান করবে নাকি এটা হিসাব করবো কিভাবে?
vaia, There’s a mistake in your main() function. As far as I know puts() should not contain any ‘;’ . Or there’s something exceptional?
ওটা একটা ভুল ছিলো 🙂
ভাইয়া………যদি C তে এই কোডটি করতে যাই তাহলে তো Constractor Use করতে পারব না, সেক্ষেত্রে *next[26+1] এর value NULL কিভাবে করব যদি একটউ বলে দেন… ধন্যবাদ।
আচ্ছা ভাইয়া , কোডের ৪৩ নম্বর লাইনে delete(cur) কি টাইপো ?
মাল্টিপল টেস্টকেস এর ক্ষেত্রে এটাকে del(cur) দিলে ইনফাইনেট লুপে পড়ে যায় প্রোগ্রাম 🙁
স্টোর করা সব ভ্যালু গুলোকে প্রিন্ট দেয়া যায় কিভাবে ?
ট্রাই এর কনসেপ্ট একদম ক্লিয়ার হয়ে গেল , ধন্যবাদ আপনাকে
Can you share any article regarding trie implemantation using array?