Implementarea structurii de date Trie

Introducere

Cuvântul trie este un inflix al cuvântului „retrieval ”, deoarece trie poate găsi un singur cuvânt într-un dicționar cu doar un prefix al cuvântului.

Trie este o structură eficientă de recuperare a datelor. Folosind trie, complexitatea căutării poate fi adusă la o limită optimă, adică lungimea șirului.

Este o structură de arbore multi-mod utilă pentru stocarea șirurilor peste un alfabet, atunci când le stocăm. A fost folosit pentru a stoca dicționare mari de cuvinte în engleză, să zicem, în programe de verificare ortografică. Cu toate acestea, penalizarea la încercări este cerința de stocare.

Ce este un trie?

Un trie este un arbore ca structura de date care stochează șiruri și vă ajută să găsiți datele asociate acelui șir folosind prefixul șirului.

De exemplu, să presupunem că intenționați să construiți un dicționar pentru a stoca șiruri împreună cu semnificațiile acestora. Trebuie să vă întrebați de ce nu pot folosi pur și simplu un tabel hash, pentru a obține informațiile.

Da, puteți obține informații folosind un tabel hash, dar mese de hash pot găsi doar date în care șirul se potrivește exact cu cel pe care l-am adăugat. Dar trie ne va oferi capacitatea de a găsi șiruri cu prefixe comune, un caracter lipsă etc. într-un timp mai mic, în comparație cu un tabel hash.

Un trie de obicei, arată cam așa,

Aceasta este o imagine a unui Trie, care stochează cuvintele {assoc, algo, all, also, tree, trie}.

Cum se implementează un trie

Să implementăm un trie în python, pentru stocarea cuvintelor cu semnificațiile lor dintr-un dicționar englez.

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.

După cum puteți vedea, marginile au o lungime de 26, fiecare index făcând referire la fiecare caracter din alfabet. „A” corespunde la 0, „B” la 1, „C” la 2… „Z” la cel de-al 25-lea indice. Dacă personajul pe care îl căutați indică None, asta înseamnă că cuvântul nu este acolo în trie.

Un Trie tipic ar trebui să implementeze cel puțin aceste două funcții:

• add_word(word,meaning)
• search_word(word)
• delete_word(word)

În plus, se poate adăuga și ceva de genul

• get_all_words()
• get_all_words_with_prefix(prefix)

Adăugarea Word la trie

	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

Preluarea datelor

	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 funcția ne va spune dacă cuvântul există sau nu în Trie. Deoarece al nostru este un dicționar, trebuie să preluăm și sensul, acum să declarăm o funcție pentru a face acest lucru.

	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:])

Ștergerea datelor

Ștergând date, trebuie doar să modificați variabila ends_here la False. Dacă faceți acest lucru, nu modificați prefixele, dar totuși șterge semnificația și existența cuvântului din trie.

	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:])

Rulați Codul