একটি প্রিফিক্স ট্রি (যাকেও ট্রাই বলা হয়) হলো একটি ডেটা স্ট্রাকচার যা আপনাকে একটি শব্দের তালিকা সংগঠিত করতে সাহায্য করে এবং নির্দিষ্ট প্রিফিক্স দিয়ে শুরু হওয়া শব্দগুলো দ্রুত খুঁজে বের করতে।
উদাহরণস্বরূপ, আপনি আপনার ডিকশনারি থেকে সব শব্দ খুঁজে বের করতে পারেন যা "ca" অক্ষরদ্বয় দিয়ে শুরু হয়, যেমন "cat" বা "cape"।
এই ছবিটি দেখুন:
এটি একটি প্রিফিক্স ট্রি।
আপনি রুট (*) থেকে একটি মার্কড নোড (যেমন e এবং t) পর্যন্ত ফলো করতে পারেন শব্দ খুঁজে বের করতে।
এই আর্টিকেলে আপনি শিখবেন কীভাবে আপনার নিজের প্রিফিক্স ট্রি রুবিতে ইমপ্লিমেন্ট করবেন এবং কীভাবে এটি ব্যবহার করে সমস্যা সমাধান করবেন!
প্রিফিক্স ট্রি ইমপ্লিমেন্টেশন
রুবিতে এটি ইমপ্লিমেন্ট করতে আমি সিদ্ধান্ত নিয়েছিলাম একটি Node ক্লাস ব্যবহার করে কয়েকটি অ্যাট্রিবিউটসহ:
- ভ্যালু (একটি ক্যারেক্টার)
- "word" ভেরিয়েবল। একটি true/false ভ্যালু যা বলে এটি একটি বৈধ শব্দ কিনা
- "next" অ্যারে। এটি সকল ক্যারেক্টার সংরক্ষণ করে (যা
Nodeঅবজেক্ট হিসেবে) যা এই ক্যারেক্টারের পর ট্রিতে আসে
এখানে কোড:
class Node
attr_reader :value, :next
attr_accessor :word
def initialize(value)
@value = value
@word = false
@next = []
end
end
এখন আমাদের একটি ক্লাস দরকার যা রুট নোড ধারণ করবে এবং এই নোডগুলো নিয়ে কাজ করার মেথডগুলো।
আসুন Trie ক্লাসটি দেখি:
class Trie
def initialize
@root = Node.new("*")
end
end
এই ক্লাসের ভেতরে আমাদের নিচের মেথডগুলো আছে:
def add_word(word)
letters = word.chars
base = @root
letters.each { |letter| base = add_character(letter, base.next) }
base.word = true
end
def find_word(word)
letters = word.chars
base = @root
word_found = letters.all? { |letter| base = find_character(letter, base.next) }
yield word_found, base if block_given?
base
end
দুই মেথডই একটি দেওয়া শব্দকে ক্যারেক্টারদের একটি অ্যারেতে ভাঙে ( chars মেথড ব্যবহার করে)।
তারপর আমরা ট্রি নেভিগেট করি রুট থেকে শুরু করে এবং ক্যারেক্টার খুঁজি বা যোগ করি।
এখানে সাপোর্টিং মেথডগুলো (একই Trie ক্লাসের ভেতরে):
def add_character(character, trie)
trie.find { |n| n.value == character } || add_node(character, trie)
end
def find_character(character, trie)
trie.find { |n| n.value == character }
end
def add_node(character, trie)
Node.new(character).tap { |new_node| trie << new_node }
end
একটি ক্যারেক্টার যোগ করতে আমরা চেক করি সেটি ইতিমধ্যে আছে কিনা (find মেথড ব্যবহার করে)। যদি থাকে তবে আমরা নোডটি ফেরত দেই।
অন্যথায় আমরা সেটি তৈরি করি এবং নতুন নোডটি ফেরত দেই।
তারপর আমাদের include? মেথডও আছে:
def include?(word)
find_word(word) { |found, base| return found && base.word }
end
এখন আমরা আমাদের নতুন ডেটা স্ট্রাকচার ব্যবহার শুরু করতে প্রস্তুত এবং দেখতে পাব কী করা যায় এটি দিয়ে 🙂
Trie ব্যবহার এবং উদাহরণ
আমাদের ট্রিতে কিছু শব্দ যোগ করি:
trie = Trie.new
trie.add_word("cat")
trie.add_word("cap")
trie.add_word("cape")
trie.add_word("camp")
আপনি চেক করতে পারেন একটি শব্দ ট্রিতে আছে কিনা এভাবে:
p trie.include?("cape") # true
p trie.include?("ca") # false
এই ডেটা স্ট্রাকচারের কিছু ব্যবহার কী?
- ওয়ার্ড গেম সমাধান
- স্পেল চেকিং
- অটোকমপ্লিট
আপনার ট্রিতে লোড করার জন্য একটি ভালো ডিকশনারি দরকার।
আমি এই দুটি পেলাম যা আপনার জন্য উপকারী হতে পারে:
- https://raw.githubusercontent.com/first20hours/google-10000-english/master/20k.txt
- https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt
প্রিফিক্সড শব্দ খুঁজে বের করা
তবে আমরা যে কোড উদাহরণটি আপনাকে দেখিয়েছিলাম সেখানে আমরা add এবং find অপারেশন ইমপ্লিমেন্ট করেছি।
কিন্তু আমাদের একটি find_words_starting_with মেথডও দরকার।
আমরা এটি "Depth First Search" (DFS) অ্যালগরিদম ব্যবহার করে করতে পারি। আমাদের একে যেট্র্যাক রাখার উপায়ও দরকার যে আমরা কোন শব্দটি দেখছি।
মনে রাখবেন আমাদের নোডগুলো শুধু একটি ক্যারেক্টার ধারণ করে, তাই আমাদের একচুয়াল স্ট্রিংগুলো রিকনস্ট্রাক্ট করতে হবে ট্রি ওভের ওয়ক করলেও।
এখানে একটি মেথড যা সব কিছু করে:
def find_words_starting_with(prefix)
stack = []
words = []
prefix_stack = []
stack << find_word(prefix)
prefix_stack << prefix.chars.take(prefix.size-1)
return [] unless stack.first
until stack.empty?
node = stack.pop
prefix_stack.pop and next if node == :guard_node
prefix_stack << node.value
stack << :guard_node
words << prefix_stack.join if node.word
node.next.each { |n| stack << n }
end
words
end
আমরা এখানে দুটি স্ট্যাক ব্যবহার করছি, একটি অনভিজিটেড নোড ট্র্যাক রাখতে (stack) এবং আরেকটি বর্তমান স্ট্রিং ট্র্যাক রাখতে (prefix_stack)।
আমরা লুপ করি যতক্ষণ না সব নোড ভিজিট করা শেষ হয় এবং নোডের ভ্যালু prefix_stack-এ যোগ করি। প্রতিটি নোড শুধু একটি ক্যারেক্টারের ভ্যালু ধারণ করে, তাই আমাদের এই ক্যারেক্টারগুলো কালেক্ট করতে হবে একটি শব্দ বানাতে।
:guard_node সিম্বলটি prefix_stack-এ যোগ করা হয় যাতে আমরা জানি কখন আমরা ব্যাকট্র্যাক করছি। আমাদের এটি দরকার যাতে সঠিক সময়ে আমাদের স্ট্রিং বাফার (prefix_stack) থেকে ক্যারেক্টার রিমুভ করতে পারি।
তারপর যদি node.word true হয় তবে এর মানে আমরা একটি পূর্ণ শব্দ পেয়েছি এবং আমরা সেটি আমাদের শব্দের তালিকায় যোগ করি।
এই মেথড ব্যবহার করার উদাহরণ:
t.find_words_starting_with("cap") # ["cap", "cape"]
যদি কোনো শব্দ না মিলে তবে আপনি একটি খালি অ্যারে পাবেন:
t.find_words_starting_with("b") # []
এই মেথডটি অটোকমপ্লিট ফিচার ইমপ্লিমেন্ট করতে ব্যবহার করা যায়।
সারসংক্ষেপ
আপনি প্রিফিক্স ট্রি (যাকেও ট্রাই বলা হয়) সম্পর্কে শিখতে পেরেছেন, একটি ডেটা স্ট্রাকচার যা শব্দের একটি তালিকাকে একটি ট্রিতে সংগঠিত করে। আপনি দ্রুত এই ট্রিকে কোয়েরি করতে পারেন একটি শব্দ বৈধ কিনা চেক করতে এবং একই প্রিফিক্স শেয়ার করা শব্দগুলো খুঁজে বের করতে।
এই পোস্টটি শেয়ার করা ভুলবেন না যাতে আরও মানুষ শিখতে পারে!
