Εφαρμογή δομής δεδομένων Trie

Εισαγωγή

Η λέξη trie είναι ένα inflix της λέξης "re trie val", επειδή η trie μπορεί να βρει μία μόνο λέξη σε ένα λεξικό με μόνο πρόθεμα της λέξης.

Το Trie είναι μια αποτελεσματική δομή δεδομένων ανάκτησης δεδομένων. Χρησιμοποιώντας το trie, οι περιπλοκές αναζήτησης μπορούν να φτάσουν στο βέλτιστο όριο, δηλαδή το μήκος της συμβολοσειράς.

Είναι μια πολύπλευρη δομή δέντρου χρήσιμη για την αποθήκευση συμβολοσειρών πάνω από ένα αλφάβητο, όταν τα αποθηκεύουμε. Έχει χρησιμοποιηθεί για την αποθήκευση μεγάλων λεξικών αγγλικών, ας πούμε, λέξεων σε προγράμματα ορθογραφικού ελέγχου. Ωστόσο, η ποινή στις δοκιμές είναι οι απαιτήσεις αποθήκευσης.

Τι είναι το trie;

Το trie είναι μια δομή δεδομένων σαν δέντρο που αποθηκεύει συμβολοσειρές και σας βοηθά να βρείτε τα δεδομένα που σχετίζονται με αυτήν τη συμβολοσειρά χρησιμοποιώντας το πρόθεμα της συμβολοσειράς.

Για παράδειγμα, ας υποθέσουμε ότι σκοπεύετε να δημιουργήσετε ένα λεξικό για να αποθηκεύσετε συμβολοσειρές μαζί με τις έννοιες τους. Πρέπει να αναρωτιέστε γιατί δεν μπορώ απλά να χρησιμοποιήσω έναν πίνακα κατακερματισμού, για να λάβω τις πληροφορίες.

Ναι, μπορείτε να λάβετε πληροφορίες χρησιμοποιώντας έναν πίνακα κατακερματισμού, αλλά οι πίνακες κατακερματισμού μπορούν να βρουν μόνο δεδομένα όπου η συμβολοσειρά ταιριάζει ακριβώς με αυτήν που έχουμε προσθέσει. Αλλά το trie θα μας δώσει τη δυνατότητα να βρούμε συμβολοσειρές με κοινά προθέματα, έναν χαρακτήρα που λείπει κλπ σε λιγότερο χρόνο, σε σύγκριση με έναν πίνακα κατακερματισμού.

Μια τρίπα συνήθως, μοιάζει κάπως έτσι,

Τρι

Αυτή είναι μια εικόνα ενός Trie, το οποίο αποθηκεύει τις λέξεις {assoc, algo, all, επίσης, 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" στον 25ο δείκτη. Αν ο χαρακτήρας που ψάχνετε δείχνει None, αυτό σημαίνει ότι η λέξη δεν υπάρχει εκεί.

Ένα τυπικό Trie πρέπει να εφαρμόζει τουλάχιστον αυτές τις δύο λειτουργίες:

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

Επιπλέον, μπορεί κανείς να προσθέσει κάτι σαν

  • get_all_words()
  • get_all_words_with_prefix(prefix)

Προσθήκη του Word στο 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

Ανάκτηση δεδομένων

 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συνάρτηση θα μας πει εάν η λέξη υπάρχει στο Trie ή όχι. Δεδομένου ότι το δικό μας είναι λεξικό, πρέπει επίσης να πάρουμε το νόημα, τώρα ας δηλώσουμε μια συνάρτηση για να το κάνουμε αυτό.

 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. Κάνοντας αυτό δεν αλλάζει τα προθέματα, αλλά εξακολουθεί να διαγράφει το νόημα και την ύπαρξη της λέξης από το 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:])
:ρουκέτα:

Εκτέλεση κώδικα