Από τις πρώτες μέρες στη ζωή μας ως προγραμματιστές , έχουμε όλοι ασχοληθεί με τις δομές δεδομένων: Οι πίνακες, οι συνδεδεμένες λίστες, τα δέντρα, τα σύνολα, οι στοίβες και οι ουρές είναι οι καθημερινές μας συντρόφους και έμπειρος προγραμματιστής ξέρει πότε και γιατί να τα χρησιμοποιήσει. Σε αυτό το άρθρο θα δούμε πώς μια συχνά παραμελημένη δομή δεδομένων, η τρι , πραγματικά λάμπει σε τομείς εφαρμογών με συγκεκριμένες λειτουργίες, όπως παιχνίδια λέξεων.
Παιχνίδια λέξεων ως παράδειγμα Trie
Για αρχάριους, ας εξετάσουμε ένα απλό παζλ λέξεων: βρείτε όλες τις έγκυρες λέξεις σε έναν πίνακα γραμμάτων 4x4, συνδέοντας γειτονικά γράμματα οριζόντια, κάθετα ή διαγώνια. Για παράδειγμα, στον παρακάτω πίνακα, βλέπουμε τα γράμματα 'W', 'A', 'I' και 'T' να συνδέονται για να σχηματίσουν τη λέξη 'WAIT'.
Η αφελής λύση για την εύρεση όλων των έγκυρων λέξεων θα ήταν να εξερευνήσετε τον πίνακα ξεκινώντας από την επάνω αριστερή γωνία και στη συνέχεια μετακινώντας το βάθος-πρώτα σε μεγαλύτερες ακολουθίες, ξεκινώντας ξανά από το δεύτερο γράμμα στην πρώτη σειρά, και ούτω καθεξής. Σε μια πλακέτα 4x4, επιτρέποντας κάθετες, οριζόντιες και διαγώνιες κινήσεις, υπάρχουν 12029640 ακολουθίες, που κυμαίνονται σε μήκος από έναν έως δεκαέξι χαρακτήρες.
Τώρα, στόχος μας είναι να βρούμε την καλύτερη δομή δεδομένων για την εφαρμογή αυτού του ελεγκτή έγκυρης λέξης, δηλαδή του λεξιλογίου μας. Λίγα σημεία που πρέπει να θυμάστε:
- Χρειαζόμαστε μόνο ένα αντίγραφο κάθε λέξης, δηλαδή, το λεξιλόγιό μας είναι ένα σύνολο, από λογική άποψη.
- Πρέπει να απαντήσουμε στις ακόλουθες ερωτήσεις για οποιαδήποτε δεδομένη λέξη:
- Η τρέχουσα ακολουθία χαρακτήρων περιλαμβάνει μια έγκυρη λέξη;
- Υπάρχουν μεγαλύτερες λέξεις που ξεκινούν με αυτήν την ακολουθία; Αν όχι, μπορούμε να εγκαταλείψουμε την πρώτη μας εξερεύνηση σε βάθος, καθώς το βάθος δεν θα δώσει έγκυρες λέξεις.
Για να επεξηγήσετε το δεύτερο σημείο, σκεφτείτε τον ακόλουθο πίνακα: Δεν έχει νόημα να εξερευνήσετε μεταγενέστερες κινήσεις, καθώς δεν υπάρχουν λέξεις στο λεξικό που ξεκινούν με 'ASF'.
τι είναι ένα αθλητικό franchise
Θα θέλαμε η δομή δεδομένων μας να απαντήσουμε σε αυτές τις ερωτήσεις το συντομότερο δυνατό. ~ O (1) ο χρόνος πρόσβασης (για τον έλεγχο μιας ακολουθίας) θα ήταν ιδανικός!
Μπορούμε να ορίσουμε τη διεπαφή λεξιλογίου έτσι (βλ εδώ για το repo GitHub):
public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); } Δομή δεδομένων Trie έναντι εναλλακτικών λύσεων
Υλοποίηση του contains() Η μέθοδος απαιτεί μια δομή δεδομένων υποστήριξης που σας επιτρέπει να βρίσκετε στοιχεία αποτελεσματικά, ενώ το isPrefix() Η μέθοδος απαιτεί από εμάς να βρούμε το 'επόμενο μεγαλύτερο στοιχείο', δηλαδή πρέπει να διατηρήσουμε το λεξιλόγιο ταξινομημένο με κάποιο τρόπο.
Μπορούμε εύκολα να εξαιρέσουμε σύνολα που βασίζονται σε κατακερματισμούς από τη λίστα των υποψηφίων: ενώ μια τέτοια δομή θα μας έδινε συνεχή έλεγχο για contains(), θα είχε αρκετά κακή απόδοση στο isPrefix(), στη χειρότερη περίπτωση που απαιτεί σαρώνουμε ολόκληρο το σετ.
Για τον αντίθετο λόγο, μπορούμε επίσης να αποκλείσουμε ταξινομημένες συνδεδεμένες λίστες, καθώς απαιτούν σάρωση της λίστας τουλάχιστον έως το πρώτο στοιχείο που είναι μεγαλύτερο ή ίσο με τη λέξη ή το πρόθεμα που αναζητήθηκε.
Δύο έγκυρες επιλογές χρησιμοποιούν μια ταξινομημένη λίστα που υποστηρίζεται από πίνακες ή ένα δυαδικό δέντρο.
Στη λίστα ταξινομημένων με υποστήριξη πίνακα μπορούμε να χρησιμοποιήσουμε δυαδική αναζήτηση για να βρούμε την τρέχουσα ακολουθία εάν υπάρχει ή το επόμενο μεγαλύτερο στοιχείο με κόστος O (log2 (n)) , που ν είναι ο αριθμός των λέξεων στο λεξικό.
Μπορούμε να εφαρμόσουμε ένα λεξιλόγιο με συστοιχία που διατηρεί πάντα τη σειρά των ομοίων Αυτό , χρησιμοποιώντας το πρότυπο java.util.ArrayList και java.util.Collections.binarySeach:
public class ListVocabulary implements Vocabulary { private List words = new ArrayList(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos = 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 = 0; } } Εάν αποφασίσαμε να χρησιμοποιήσουμε ένα δυαδικό δέντρο, η εφαρμογή θα μπορούσε να είναι ακόμη πιο σύντομη και πιο κομψή (και πάλι, εδώ είναι σύνδεσμος προς τον κωδικό ):
public class TreeVocabulary extends TreeSet implements Vocabulary { public TreeVocabulary(Collection c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } } Και στις δύο περιπτώσεις, μπορούμε να περιμένουμε O (ημερολόγιο n) απόδοση για κάθε μέθοδο πρόσβασης (contains() και isPrefix()). Όσον αφορά τις απαιτήσεις χώρου, απαιτούνται τόσο η υλοποίηση που υποστηρίζεται από τον πίνακα όσο και η εφαρμογή που δεν υποστηρίζεται από δέντρο O (n + M) όπου n είναι ο αριθμός των λέξεων στο λεξικό και το M είναι το bytesize του λεξικού, δηλαδή το άθροισμα του μήκους των συμβολοσειρών στο λεξικό.
Εφαρμογές Trie: Πότε και γιατί χρησιμοποιείτε το Tries
Η λογαριθμική απόδοση και η γραμμική μνήμη δεν είναι κακές. Ωστόσο, υπάρχουν μερικά ακόμη χαρακτηριστικά του τομέα εφαρμογών που μπορούν να μας οδηγήσουν σε καλύτερη απόδοση:
- Μπορούμε να υποθέσουμε με ασφάλεια ότι όλες οι λέξεις είναι πεζά.
- Δεχόμαστε μόνο γράμματα a-z - χωρίς σημεία στίξης, χωρίς παύλες, χωρίς τόνους κ.λπ.
- Το λεξικό περιέχει πολλές παραμορφωμένες μορφές: πληθυντικούς, συζευγμένα ρήματα, σύνθετες λέξεις (π.χ. σπίτι -> οικονόμος). Ως εκ τούτου, πολλές λέξεις μοιράζονται το ίδιο στέλεχος .
- Οι λέξεις έχουν περιορισμένο μήκος. Για παράδειγμα, εάν εργαζόμαστε σε έναν πίνακα 4x4, όλες οι λέξεις μεγαλύτερες από 16 χαρακτήρες μπορούν να απορριφθούν.
Εδώ μπαίνει η trie (προφέρεται «δοκιμή»). Αλλά τι ακριβώς είναι μια τρι; Οι προσπάθειες είναι παραμελημένες δομές δεδομένων, που βρίσκονται σε βιβλία αλλά σπάνια σε τυπικές βιβλιοθήκες.
Για κίνητρο, ας εξετάσουμε πρώτα το παιδί αφίσα της Πληροφορικής: το δυαδικό δέντρο. Τώρα, όταν αναλύουμε την απόδοση ενός δυαδικού δέντρου και λέμε τη λειτουργία Χ είναι O (ημερολόγιο (n)) , μιλάμε συνεχώς τη βάση καταγραφής 2. Αλλά τι γίνεται αν, αντί για ένα δυαδικό δέντρο, χρησιμοποιούσαμε ένα τριμερές δέντρο, όπου κάθε κόμβος έχει τρία παιδιά (ή, έναν ανεμιστήρα των τριών). Τότε, θα μιλούσαμε τη βάση καταγραφής 3. (Αυτή είναι μια βελτίωση της απόδοσης, αν και μόνο από έναν σταθερό παράγοντα.) Ουσιαστικά, τα δέντρα μας θα γινόταν πλατύτερα αλλά μικρότερα και θα μπορούσαμε να κάνουμε λιγότερες αναζητήσεις καθώς δεν χρειάζεται να κατεβούμε αρκετά τόσο βαθιά.
Κάνοντας ένα βήμα παραπέρα, τι γίνεται αν είχαμε ένα δέντρο με ανεμιστήρα ίσο με τον αριθμό των πιθανών τιμών του τύπου δεδομένων μας;
Αυτό είναι το κίνητρο πίσω από το trie. Και όπως μπορεί να μαντέψατε, ένα tri είναι πράγματι ένα δέντρο, ένα trie δέντρο για να το πούμε!
Αλλά, σε αντίθεση με τα περισσότερα δυαδικά δέντρα που θα χρησιμοποιούσατε για την ταξινόμηση συμβολοσειρών, αυτά που θα αποθηκεύσουν ολόκληρες λέξεις στους κόμβους τους, κάθε κόμβος ενός trie έχει έναν μόνο χαρακτήρα (και ούτε καν αυτό, όπως θα δούμε σύντομα) και έχει μέγιστο ανεμιστήρα ίσο με το μήκος του αλφαβήτου. Στην περίπτωσή μας, το μήκος του αλφαβήτου είναι 26. ως εκ τούτου, οι κόμβοι του tri έχουν μέγιστο ανεμιστήρα από 26. Και, ενώ ένα ισορροπημένο δυαδικό δέντρο έχει log2 (n) βάθος, το μέγιστο βάθος του trie είναι ίσο με το μέγιστο μήκος μιας λέξης! (Και πάλι, ευρύτερο αλλά μικρότερο.)
Περιγράψτε τις αρχές gestalt της ομοιότητας εγγύτητας, συνέχειας και κλεισίματος
Μέσα σε ένα trie, λέξεις με το ίδιο στέλεχος (πρόθεμα) μοιράζονται την περιοχή μνήμης που αντιστοιχεί στο στέλεχος.
Για να απεικονίσετε τη διαφορά, ας εξετάσουμε ένα μικρό λεξικό που αποτελείται από πέντε λέξεις. Ας υποθέσουμε ότι τα ελληνικά γράμματα δείχνουν δείκτες, και σημειώστε ότι στην τρίη, Οι κόκκινοι χαρακτήρες υποδεικνύουν κόμβους με έγκυρες λέξεις .
Εφαρμογή Java Trie
Όπως γνωρίζουμε, στο δέντρο τα στοιχεία δείκτη προς τα παιδιά εφαρμόζονται συνήθως με μια αριστερή και δεξιά μεταβλητή, επειδή το μέγιστο ανεμιστήρα είναι σταθερό στα δύο.
Σε ένα trie ευρετήριο ένα αλφάβητο 26 γραμμάτων, κάθε κόμβος έχει 26 πιθανά παιδιά και, επομένως, 26 πιθανούς δείκτες. Κάθε κόμβος διαθέτει έτσι μια σειρά από 26 (δείκτες προς) δευτερεύοντα δέντρα, όπου κάθε τιμή θα μπορούσε είτε να είναι μηδενική (εάν δεν υπάρχει τέτοιο θυγατρικό) ή άλλος κόμβος.
Πώς, λοιπόν, αναζητούμε μια λέξη σε ένα τρίγωνο; Εδώ είναι η μέθοδος που, δεδομένου του String s, θα προσδιορίσει τον κόμβο που αντιστοιχεί στο τελευταίο γράμμα της λέξης, εάν υπάρχει στο δέντρο:
public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i Το LOWERCASE.getIndex(s.charAt(i)) Η μέθοδος απλώς επιστρέφει τη θέση του με χαρακτήρας στο αλφάβητο. Στον κόμβο που επιστράφηκε, μια ιδιότητα Boolean node υποδηλώνει ότι ο κόμβος αντιστοιχεί στο τελευταίο γράμμα μιας λέξης, δηλαδή ένα γράμμα που σημειώθηκε με κόκκινο χρώμα στο προηγούμενο παράδειγμα. Δεδομένου ότι κάθε κόμβος διατηρεί έναν μετρητή του αριθμού των παιδιών, εάν αυτός ο μετρητής είναι θετικός, τότε υπάρχουν μεγαλύτερες λέξεις στο λεξικό που έχουν την τρέχουσα συμβολοσειρά ως πρόθεμα. Σημείωση: ο κόμβος δεν χρειάζεται πραγματικά να διατηρεί μια αναφορά στον χαρακτήρα στον οποίο αντιστοιχεί, επειδή είναι έμμεσος στη θέση του στο trie.
ένα pmo δεν χρησιμοποιείται
Ανάλυση απόδοσης
Αυτό που κάνει τη δομή trie να έχει πραγματικά καλή απόδοση σε αυτές τις καταστάσεις είναι ότι το κόστος αναζήτησης μιας λέξης ή προθέματος είναι σταθερό και εξαρτάται μόνο από τον αριθμό των χαρακτήρων της λέξης και όχι από το μέγεθος του λεξιλογίου.
Στον συγκεκριμένο τομέα μας, δεδομένου ότι έχουμε συμβολοσειρές που έχουν το πολύ 16 χαρακτήρες, απαιτούνται ακριβώς 16 βήματα για να βρούμε μια λέξη που βρίσκεται στο λεξιλόγιο, ενώ μπορεί να ληφθεί οποιαδήποτε αρνητική απάντηση, δηλαδή η λέξη ή το πρόθεμα στο τρίμηνο. σε έως και 16 βήματα! Λαμβάνοντας υπόψη ότι έχουμε προηγουμένως αγνοήσει το μήκος της συμβολοσειράς κατά τον υπολογισμό της πολυπλοκότητας του χρόνου εκτέλεσης τόσο για τη λίστα ταξινόμησης που υποστηρίζεται από πίνακα όσο και για το δέντρο, το οποίο είναι κρυμμένο στις συγκρίσεις συμβολοσειρών, μπορούμε επίσης να το αγνοήσουμε εδώ και να δηλώσουμε με ασφάλεια ότι η αναζήτηση έχει γίνει σε Ο (1) χρόνος.
Λαμβάνοντας υπόψη τις απαιτήσεις χώρου (και να θυμόμαστε ότι έχουμε δείξει με Μ το bytesize του λεξικού), το trie θα μπορούσε να έχει Μ κόμβοι στη χειρότερη περίπτωση, εάν δεν υπάρχουν δύο συμβολοσειρές κοινόχρηστο πρόθεμα. Αλλά επειδή έχουμε παρατηρήσει ότι υπάρχει μεγάλος βαθμός πλεονασμού στο λεξικό, πρέπει να γίνει πολλή συμπίεση. Το αγγλικό λεξικό που χρησιμοποιείται στον κώδικα παραδείγματος είναι 935.017 bytes και απαιτεί 250.264 κόμβους, με λόγο συμπίεσης περίπου 73%.
Ωστόσο, παρ 'όλα αυτά, ακόμη και ένα συμπιεσμένο trie συνήθως απαιτεί περισσότερη μνήμη από ένα δέντρο ή έναν πίνακα. Αυτό συμβαίνει επειδή, για κάθε κόμβο, τουλάχιστον 26 x sizeof(pointer) απαιτούνται bytes, συν κάποια γενικά έξοδα για το αντικείμενο και πρόσθετα χαρακτηριστικά. Σε ένα μηχάνημα 64-bit, κάθε κόμβος απαιτεί περισσότερα από 200 bytes, ενώ ένας χαρακτήρας συμβολοσειράς απαιτεί ένα byte, ή δύο, αν λάβουμε υπόψη UTF συμβολοσειρές.
Σχετίζεται με: Κορυφαία 10 πιο συνηθισμένα λάθη που κάνουν οι προγραμματιστές Java: Ένας οδηγός για αρχάριους Java Δοκιμές και δοκιμές απόδοσης
Λοιπόν, τι γίνεται με την απόδοση; Οι υλοποιήσεις του λεξιλογίου δοκιμάστηκαν σε δύο διαφορετικές καταστάσεις: έλεγχος για 20.000.000 τυχαίες συμβολοσειρές και εύρεση όλων των λέξεων σε 15.000 πίνακες που δημιουργήθηκαν τυχαία από την ίδια λίστα λέξεων.
Αναλύθηκαν τέσσερις δομές δεδομένων: μια ταξινομημένη λίστα με συστοιχία, ένα δυαδικό δέντρο, το trie που περιγράφηκε παραπάνω και ένα trie χρησιμοποιώντας πίνακες byte που αντιστοιχούν στο αλφάβητο-δείκτη των ίδιων των χαρακτήρων (μια δευτερεύουσα και εύκολα εφαρμόσιμη βελτιστοποίηση απόδοσης). Εδώ είναι τα αποτελέσματα, σε ms:
Ο μέσος αριθμός κινήσεων που έγιναν για την επίλυση του πίνακα είναι 2.188. Για κάθε κίνηση, γίνεται αναζήτηση λέξεων και αναζήτηση προθέματος, δηλαδή για έλεγχο όλων των πινάκων, πραγματοποιήθηκαν περισσότερες από 32 εκατομμύρια αναζητήσεις λέξεων και 32 εκατομμύρια προθέματα. Σημείωση: αυτά θα μπορούσαν να γίνουν σε ένα βήμα, τα κράτησα χωριστά για λόγους σαφήνειας στην έκθεση. Η συμπίεση τους σε ένα μόνο βήμα θα μείωνε τον χρόνο για την επίλυση των σανίδων σχεδόν στο μισό, και μάλλον θα ευνοούσε το trie ακόμη περισσότερο.
Όπως μπορεί να φανεί παραπάνω, η αναζήτηση λέξεων αποδίδει καλύτερα με το trie ακόμη και όταν χρησιμοποιεί συμβολοσειρές και είναι ακόμη πιο γρήγορη όταν χρησιμοποιείτε ευρετήρια αλφαβήτου, με το τελευταίο να λειτουργεί περισσότερο από δύο φορές πιο γρήγορα από ένα τυπικό δυαδικό δέντρο. Η διαφορά στην επίλυση των πινάκων είναι ακόμη πιο εμφανής, με τη γρήγορη λύση tri-alphabet-index να είναι περισσότερο από τέσσερις φορές πιο γρήγορη από τη λίστα και το δέντρο.
Τυλίγοντας
Το trie είναι μια πολύ εξειδικευμένη δομή δεδομένων που απαιτεί πολύ περισσότερη μνήμη από τα δέντρα και τις λίστες. Ωστόσο, όταν ισχύουν συγκεκριμένα χαρακτηριστικά τομέα, όπως ένα περιορισμένο αλφάβητο και υψηλή απόλυση στο πρώτο μέρος των συμβολοσειρών, μπορεί να είναι πολύ αποτελεσματικό στην αντιμετώπιση της βελτιστοποίησης απόδοσης.
βιβλιογραφικές αναφορές
Μια εκτενής εξήγηση των δοκιμών και των αλφαβήτων βρίσκεται στο κεφάλαιο 5 του βιβλίου του Robert Sedgewick «Αλγόριθμοι, 4η έκδοση». Ο συνοδευτικός ιστότοπος στο Princeton έχει το κώδικα για μια εφαρμογή του Alphabet και του TrieST που είναι πιο εκτεταμένο από το παράδειγμά μου.
πώς να γράψετε ένα έγγραφο σχεδίασης λογισμικού
Μπορείτε επίσης να βρείτε την περιγραφή του trie και τις εφαρμογές για διάφορες γλώσσες Βικιπαίδεια και μπορείτε να ρίξετε μια ματιά σε αυτό Πόρος Πανεπιστημίου της Βοστώνης επισης.
Σχετίζεται με: Needle in a Haystack: Ένας εκπαιδευτικός αλγόριθμος αναζήτησης κειμένου μεγάλης κλίμακας Κατανόηση των βασικών
Τι είναι το trie;
Το trie είναι μια δομημένη δομή δεδομένων, ένας τύπος δέντρου αναζήτησης που χρησιμοποιείται για την αποθήκευση συσχετιστικών δομών δεδομένων. Αναφέρεται επίσης ως δέντρο Radix ή δέντρο προθέματος.
Τι είναι το συμπιεσμένο trie;
Ένα συμπιεσμένο trie είναι ουσιαστικά μια δομή δεδομένων trie με έναν επιπλέον κανόνα ότι κάθε κόμβος πρέπει να έχει δύο ή περισσότερα παιδιά.
Ποια προφορά trie είναι σωστή;
Ένα trie προφέρεται «δοκιμή», αν και το όνομα trie προέρχεται από «ανάκτηση».
Σε τι χρησιμεύει η δομή δεδομένων trie;
Η δομή δεδομένων trie ταιριάζει σε αλγόριθμους που ταιριάζουν, καθώς βασίζονται στο πρόθεμα κάθε συμβολοσειράς. Οι δοκιμές χρησιμοποιούνται συνήθως όταν ασχολούνται με ομάδες χορδών και όχι μεμονωμένων χορδών, επιτρέποντάς τους να λύσουν ένα ευρύ φάσμα προβλημάτων.
