Η δομή δεδομένων Trie (Πρόθεμα δέντρου)

Το A Trie(επίσης γνωστό ως δέντρο προθέματος) είναι ένας ειδικός τύπος δέντρου που χρησιμοποιείται για την αποθήκευση συσχετιστικών δομών δεδομένων

Ένα trie (προφέρεται δοκιμή) παίρνει το όνομά του από το re trie val - η δομή του το καθιστά έναν αστρικό αλγόριθμο που ταιριάζει.

Συμφραζόμενα

Write your own shuffle method to randomly shuffle characters in a string. 
Use the words text file, located at /usr/share/dict/words, and your shuffle method to create an anagram generator that only produces real words.
Given a string as a command line argument, print one of its anagrams. 

Μου παρουσίασαν αυτήν την πρόκληση αυτήν την εβδομάδα στην Ακαδημία Προϊόντων του Make School.

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

Μια προσέγγιση σε αυτήν την πρόκληση είναι:

  • ανακατέψτε τυχαία τους χαρακτήρες στη συμβολοσειρά
  • Στη συνέχεια, ελέγξτε το με όλες τις λέξεις που ήταν στο / usr / share / dict / words για να επιβεβαιώσετε ότι είναι πραγματική λέξη.

Ωστόσο, αυτή η προσέγγιση απαιτεί να ελέγξω ότι οι τυχαία ανακατεμένοι χαρακτήρες στη νέα συμβολοσειρά ταιριάζουν με μία από τις 235.887 λέξεις σε αυτό το αρχείο - αυτό σημαίνει 235.887 λειτουργίες για κάθε συμβολοσειρά που θέλω να επαληθεύσω ως πραγματική λέξη.

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

def generateAnagram(string, language="en_US"): languageDict = enchant.Dict(language) numOfPossibleCombinationsForString = math.factorial(len(string)) for i in range(0, numOfPossibleCombinationsForString): wordWithShuffledCharacters = shuffleCharactersOf(string)
 if languageDict.check(wordWithShuffledCharacters): return wordWithShuffledCharacters return "There is no anagram in %s for %s." % (language, string)

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

Ήμουν θετικός ότι η βιβλιοθήκη δεν χρησιμοποιούσε την προσέγγιση που ανέφερα νωρίτερα. Ήμουν περίεργος και έσκαψα τον πηγαίο κώδικα - βρήκα ένα tri.

Τρι

Ένα trie αποθηκεύει δεδομένα σε "βήματα". Κάθε βήμα είναι ένας κόμβος στο trie.

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

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

Δημιούργησα μια δοκιμή καταλόγων στην επιφάνεια εργασίας μου για να οπτικοποιήσω την αποχώρηση από κόμβους. Πρόκειται για ένα trie που περιέχει δύο λέξεις: apple και app.

Σημειώστε ότι το τέλος μιας λέξης συμβολίζεται με '$'. Χρησιμοποιώ το '$' επειδή είναι ένας μοναδικός χαρακτήρας που δεν θα υπάρχει σε καμία λέξη σε καμία γλώσσα.

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

Καθώς κατεβαίνω το trie, τα δύο πρώτα γράμματα του «διαφράγματος» υπάρχουν ήδη στο trie, οπότε κατεβαίνω αυτούς τους κόμβους.

Ωστόσο, το τρίτο γράμμα «e» δεν είναι θυγατρικό του κόμβου «p». Ένας νέος κόμβος δημιουργείται για να αντιπροσωπεύει το γράμμα «e», διακλαδίζοντας από τις άλλες λέξεις στο trie. Δημιουργούνται επίσης νέοι κόμβοι για τα γράμματα που ακολουθούν.

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

Ίσως σκέφτεστε: «Περιμένετε, δεν θα χρειαστεί πολύς χρόνος για να δημιουργήσετε το trie από αυτό το αρχείο κειμένου με 235.887 λέξεις σε αυτό; Ποιο είναι το νόημα του βρόχου πάνω από κάθε χαρακτήρα σε κάθε λέξη; "

Ναι, η επανάληψη σε κάθε χαρακτήρα κάθε λέξης για τη δημιουργία ενός trie χρειάζεται λίγο χρόνο. Ωστόσο, ο χρόνος που απαιτείται για τη δημιουργία του trie αξίζει τον κόπο - γιατί για να ελέγξετε αν υπάρχει μια λέξη στο αρχείο κειμένου, χρειάζεται το πολύ, όσες λειτουργίες είναι όσο το μήκος της ίδιας της λέξης . Πολύ καλύτερα από τις 235.887 πράξεις που επρόκειτο να λάβει πριν.

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

endOfWord = "$"
def generateTrieFromWordsArray(words): root = {} for word in words: currentDict = root for letter in word: currentDict = currentDict.setdefault(letter, {}) currentDict[endOfWord] = endOfWord return root
def isWordPresentInTrie(trie, word): currentDict = trie for letter in word: if letter in currentDict: currentDict = currentDict[letter] else: return False return endOfWord in currentDict

Μπορείτε να δείτε τη λύση μου για τη γεννήτρια anagram στο Github μου. Από τότε που εξερεύνησα αυτόν τον αλγόριθμο, αποφάσισα να κάνω αυτήν την ανάρτηση ιστολογίου μία από τις πολλές - κάθε ανάρτηση καλύπτει έναν αλγόριθμο ή δομή δεδομένων. Ο κωδικός είναι διαθέσιμος στους αλγορίθμους και τις δομές δεδομένων μου - αστεράξτε τον για να μείνετε ενημερωμένοι!

Επόμενα βήματα

Προτείνω να ρίξετε μια ματιά στο τρίποδο του Ray Wenderlich. Αν και είναι γραμμένο στο Swift, είναι μια πολύτιμη πηγή για εξηγήσεις διαφόρων αλγορίθμων.

Παρόμοιο με το trie (αλλά πιο αποδοτικό στη μνήμη) είναι ένα δέντρο επιθήματος ή ακτίνα. Με λίγα λόγια, αντί να αποθηκεύονται μεμονωμένοι χαρακτήρες σε κάθε κόμβο, το τέλος μιας λέξης, το επίθημά της, αποθηκεύεται και οι διαδρομές δημιουργούνται σχετικά.

Ωστόσο, μια ακτίνα είναι πιο περίπλοκη στην εφαρμογή από το trie. Προτείνω να ρίξετε μια ματιά στο ρεπόξ του Ray Wenderlich αν ενδιαφέρεστε.

Αυτή είναι η πρώτη ανάρτηση της σειράς αλγορίθμων και δομών δεδομένων. Σε κάθε ανάρτηση, θα παρουσιάσω ένα πρόβλημα που μπορεί να λυθεί καλύτερα με έναν αλγόριθμο ή δομή δεδομένων για να απεικονίσει τον ίδιο τον αλγόριθμο / δομή δεδομένων.

Αστέρι το repo των αλγορίθμων μου στο Github και ακολουθήστε με στο Twitter αν θέλετε να ακολουθήσετε!

Κερδίσατε αξία διαβάζοντας αυτό το άρθρο; Κάντε κλικ εδώ για να το μοιραστείτε στο Twitter! Αν θέλετε να βλέπετε περιεχόμενο σαν αυτό πιο συχνά, ακολουθήστε με στο Medium και εγγραφείτε παρακάτω στο ενημερωτικό δελτίο μου το μήνα. Μη διστάσετε να μου αγοράσετε και έναν καφέ.