ট্রাই(প্রিফিক্স/রেডিক্স ট্রি)

ট্রাই(Trie) হল বহুল ব্যবহৃত একটা ডাটা স্ট্রাকচার।ট্রাই এর সবচেয়ে প্রচলিত প্রয়োগ হল ডিকশনারিতে শব্দ স্টোর করা, সার্চ করা, ডিলিট করা ইত্যাদি।ধরা যাক,ডাটাবেসে বাংলাদেশের সব মানুষের নাম আছে।এখন ডাটাবেস যতই বিশাল হোক না কেন,সেখান থেকে ABUL নামটা খুঁজে বের করতে ৪ টার বেশি অপারেশন লাগবে না(ক্যামনে?😮)।এবার আমরা একটা ওয়েব ব্রাউজারের কথা চিন্তা করি।আমরা যখন ব্রাউজারে সার্চ করার জন্য কিছু লিখি,তখন অনেক টেক্সট অটো কমপ্লিট হয়ে যায় বা যে টেক্সট লিখার পসিবিলিটি আছে তার অনেক গুলো অপশন দেখায়(ক্যামনে বুঝে,আমি কি চায়?😕)। হুম,এইসব ক্ষেত্রে ট্রাই ই হল নাটের গুরু 😉।

ট্রাই(Trie)  হল 'Retrieval' ওয়ার্ড টার একটা Infix।কারণ ট্রাই ডিকশনারি থেকে একটা ওয়ার্ড কে শুধুমাত্র ওয়ার্ডটার একটা প্রিফিক্স দিয়েই খুঁজে বের করতে সক্ষম। Edward Fredkin প্রথমে 'Retrieval' শব্দের এই  Infix নিয়ে এটাকে ট্রি(Tri) বলেন।কিন্তু গ্রাফ থিওরিতে ব্যাপকভাবে প্রচলিত 'ট্রি' থেকে আলাদা করার জন্যই এটাকে ট্রাই বলা হয়ে থাকে।


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

ধরা যাক,একটা ডিকশনারিতে কতগুলো শব্দ দেয়া থাকবে,সেখান কতগুলো শব্দ কুয়েরি করে দেখতে হবে শব্দগুলো ডিকশনারিতে আছে কি না।এর জন্য স্যাম্পল কোড টা হলঃ

	#include<bits/stdc++.h>
	using namespace std;
	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 *cur=root;
	for(int i=0;i<len;i++){
	int id=str[i]-'a';
	if(cur->next[id]==NULL)
	cur->next[id]=new node();
	cur=cur->next[id];
	}
	cur->endmark=true;
	}
	bool search(char* str,int len){
	node *cur=root;
	for(int i=0;i<len;i++){
	int id=str[i]-'a';
	if(cur->next[id]==NULL) return false;
	cur=cur->next[id];
	}
	return cur->endmark;
	}
	void del(node* cur)
	{
	for(int i= 0;i<26;i++)
	if (cur->next[i])
	del(cur->next[i]);
	delete(cur);
	}
	int main()
	{
	printf("Enter the number of words\n");
	root = new node();
	int num_word;
	scanf("%d",&num_word);
	for(int i=1;i<=num_word;i++){
	char str[50];
	scanf("%s",str);
	insert(str,strlen(str));
	}
	printf("Enter the number of queries\n");
	int query;
	scanf("%d",&query);
	for(int i=1;i<=query;i++){
	char str[50];
	scanf("%s",str);
	if(search(str,strlen(str))) printf("Found\n");
	else printf("Not Found\n");
	}
	del(root);
	return 0;
	}

view raw Trie.cpp hosted with ❤ by GitHub

Printing Trie Lexicographically: Sample code

	void lexicograpPrint(node *cur,char* prefix,vector<char>print_word)
	{
	if(cur->endmark and print_word.size()!=0)
	{
	for(auto x:print_word) printf("%c",x);
	printf("\n");
	}
	for(int i=0; i<26; i++)
	{
	if(cur->next[i]!=NULL)
	{
	print_word.push_back(i+'a'); //push converting integer int character
	lexicograpPrint(cur->next[i],prefix,print_word);
	print_word.pop_back();
	}
	}
	print_word.pop_back();
	}

view raw Printing Trie.cpp hosted with ❤ by GitHub

সতর্কতা(নিজের জন্য) ঃযে দুই টা ভুল প্রায়ই হয়!😑

১। প্রবলেমে টেস্টকেস থাকলে প্রতি টেস্টকেসেই নতুন ট্রাই ক্রিয়েট হচ্ছে কি না এবং আগের ট্রাই ধ্বংস হচ্ছে কি না ?দেখে নিতে হবে।

২। ট্রাই ডিলিট করার সময় next[] অ্যারের দিকে খেয়াল রাখা। 

ট্রাই রিলেটেড প্রবলেম এবং সল্যুশনঃ  

1. UVA-10226 (Hardwood Species)
            Solution Idea: খুবই সহজ প্রবলেম।একটা ডাটাসেটে কতগুলো Hardwood Tree এর নাম দেয়া থাকবে।সেখান দেখতে হবে কোন Tree এর নামটা শতকরা কত ভাগ আছে।ট্রাই কে Traverse করে সব গুলো ইউনিক ট্রি প্রিন্ট করছি,সাথে সাথে শতকরা কত ভাগ আছে সেটাও প্রিন্ট করছি।
             বিঃদ্রঃইনপুট নেয়ার ক্ষেত্রে সতর্ক থাকতে হবে।প্রতি ইনপুটের পূর্বেএকটা Blank Line হবে।
            Solution: https://ideone.com/DfIsgA (See at your own risk👎).

2. LightOj 1129 (Consistency Checker)

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

            Solution: https://ideone.com/ro93Rq (See at your own risk👎).

3. LightOj 1224 (DNA Prefix)
            Solution Idea: n সংখ্যক DNA samples এর একটা সেট দেয়া থাকেবে।সেখান থেকে কতগুলো sample নিয়ে একটা সাবসেট করতে হবে যেন তাদের মধ্যকার longest common prefix*number of samples in the subset ম্যাক্সিমাম হয়। DNA samples যেহুতু শুধুমাত্র A,C,G,T দ্বারা গঠিত তাই এই চারটা ক্যারেক্টারকে যথাক্রমে  0,1,2,3 দিয়ে ম্যাপিং করে রেখে দিব।তাহলে চার লেন্থের একটা next[] অ্যারে ইউজ করলেই কাজ হয়ে যাবে।
            Solution: https://ideone.com/5J1KcD (See at your own risk👎).

4. LightOj 1114 (Easily Readable)
            Solution Idea: ডিকশনারিতে কতগুলো ওয়ার্ড দেয়া থাকবে,এবং কুয়েরি করার জন্য একটা সেনটেন্স থাকবে।এক্ষেত্রে আমরা যখন ওয়ার্ড গুলোকে ট্রাই তে ইনসার্ট করব,তখন ফার্স্ট এবং লাস্ট লেটার ছাড়া বাকি গুলোকে সর্ট করে ইনসার্ট করছি।কুয়েরি করার সময়ও সেনটেন্সের প্রতিটা ওয়ার্ডের ফার্স্ট এবং লাস্ট লেটার ছাড়া মিডলের গুলোকে সর্ট করে কুয়েরি করছি।
            Solution: https://ideone.com/jXZqkh (See at your own risk👎).

5. Hackerrank-Contacts
            Solution Idea: ইনপুটে দুইটা কমান্ড আছে, কোন ওয়ার্ডের পূর্বে 'Add' কমান্ড থাকে সেই ওয়ার্ড টা ট্রাই তে ইনসার্ট করতে হবে আর 'Find' কমান্ড থাকলে খুঁজে বের করতে হবে ঐ প্রিফিক্স দিয়ে কয়টা ওয়ার্ড শুরু হয়েছে।

            Solution: https://ideone.com/sjKI2l (See at your own risk👎).

6.Hackerrank-No Prefix Set
            Solution Idea: এই প্রবলেমটা অনেকটা LightOj 1129 (Consistency Checker) এর মতই। কোন একটা সেট Consistent কি না চেক করতে হবে।
            Solution: https://ideone.com/7izhgR (See at your own risk👎).

7. SPOJ DICT - Search in the dictionary!
            Solution Idea: প্রতিটা কুয়েরি প্রিফিক্সের জন্য ট্রাই Traverse করছি।যদি প্রিফিক্সটা ট্রাই তে থাকে এবং তার চাইল্ড থাকে তাহলে ঐ প্রিফিক্স দিয়ে ট্রাই তে যত ওয়ার্ড আছে সেগুলো Lexicographically প্রিন্ট করছি,আর প্রিফিক্স ট্রাই তে না থাকলে বা আছে কিন্তু চাইল্ড নাই,সেক্ষেত্রে "No match."প্রিন্ট করছি।
            Solution: https://ideone.com/AkFgDI  (See at your own risk👎).

References:    

→http://www.shafaetsplanet.com/planetcoding/?p=1679

→https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/
→http://theoryofprogramming.com/2015/01/16/trie-tree-implementation/