تنفيذ هيكل البيانات Trie
المقدمة
الكلمة trie هي جزء من كلمة "re trie val" ، لأن trie يمكن أن يجد كلمة واحدة في قاموس ببادئة الكلمة فقط.
Trie هو هيكل بيانات فعال لاسترجاع البيانات. باستخدام trie ، يمكن الوصول إلى تعقيدات البحث إلى الحد الأمثل ، أي طول السلسلة.
إنها بنية شجرية متعددة الاتجاهات مفيدة لتخزين السلاسل فوق الأبجدية ، عندما نقوم بتخزينها. تم استخدامه لتخزين قواميس كبيرة من اللغة الإنجليزية ، على سبيل المثال ، الكلمات في برامج التدقيق الإملائي. ومع ذلك ، فإن عقوبة المحاولات هي متطلبات التخزين.
ما هو Trie؟
المثلث هو شجرة مثل بنية البيانات التي تخزن السلاسل ، وتساعدك في العثور على البيانات المرتبطة بهذه السلسلة باستخدام بادئة السلسلة.
على سبيل المثال ، لنفترض أنك تخطط لبناء قاموس لتخزين السلاسل مع معانيها. يجب أن تتساءل لماذا لا يمكنني ببساطة استخدام جدول التجزئة للحصول على المعلومات.
نعم ، يمكنك الحصول على معلومات باستخدام جدول التجزئة ، لكن جداول التجزئة يمكنها فقط العثور على البيانات التي تتطابق فيها السلسلة تمامًا مع تلك التي أضفناها. لكن Trie يمنحنا القدرة على العثور على سلاسل ذات بادئات مشتركة ، وحرف مفقود وما إلى ذلك في وقت أقل ، مقارنةً بجدول التجزئة.
عادة ما يبدو شيء مثل هذا ،
هذه صورة Trie ، تخزن الكلمات {assoc، algo، all، also، tree، trie}.
كيفية تنفيذ Trie
دعنا نطبق trie في python لتخزين الكلمات مع معانيها من قاموس إنجليزي.
ALPHABET_SIZE = 26 # For English class TrieNode: def __init__(self): self.edges = [None]*(ALPHABET_SIZE) # Each index respective to each character. self.meaning = None # Meaning of the word. self.ends_here = False # Tells us if the word ends here.كما ترى ، يبلغ طول الحواف 26 ، يشير كل فهرس إلى كل حرف في الأبجدية. "A" تقابل 0 ، "B" تقابل 1 ، "C" تساوي 2 ... "Z" تشير إلى الفهرس الخامس والعشرين. إذا كان الحرف الذي تبحث عنه يشير إليه None، فهذا يعني أن الكلمة ليست موجودة في trie.
يجب أن تنفذ Trie النموذجية هاتين الوظيفتين على الأقل:
add_word(word,meaning)search_word(word)delete_word(word)
بالإضافة إلى ذلك ، يمكن للمرء أيضًا إضافة شيء مثل
get_all_words()get_all_words_with_prefix(prefix)
إضافة كلمة إلى الثلاثي
def add_word(self,word,meaning): if len(word)==0: self.ends_here = True # Because we have reached the end of the word self.meaning = meaning # Adding the meaning to that node return ch = word[0] # First character # ASCII value of the first character (minus) the ASCII value of 'a'-> the first character of our ALPHABET gives us the index of the edge we have to look up. index = ord(ch) - ord('a') if self.edges[index] == None: # This implies that there's no prefix with this character yet. new_node = TrieNode() self.edges[index] = new_node self.edges[index].add(word[1:],meaning) #Adding the remaining wordاسترجاع البيانات
def search_word(self,word): if len(word)==0: if self.ends_here: return True else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch)-ord('a') if self.edge[index]== None: return False else: return self.edge[index].search_word(word[1:])و search_wordسوف ظيفة تخبرنا في حالة وجود الكلمة في حاكموا أم لا. نظرًا لأن قاموسنا هو قاموس ، فنحن بحاجة إلى جلب المعنى أيضًا ، والآن دعنا نعلن عن وظيفة للقيام بذلك.
def get_meaning(self,word): if len(word)==0 : if self.ends_here: return self.meaning else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].get_meaning(word[1:])حذف البيانات
بحذف البيانات ، تحتاج فقط إلى تغيير المتغير ends_hereإلى False. لا يؤدي القيام بذلك إلى تغيير البادئات ، ولكن الصور الثابتة تحذف معنى الكلمة ووجودها من المثلث.
def delete_word(self,word): if len(word)==0: if self.ends_here: self.ends_here = False self.meaning = None return "Deleted" else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].delete_word(word[1:])
تشغيل الكود
