UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.10 Free with a free account
Tries: Storing Vocabularies in Prefix Trees
Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.10 · lesson 76 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Huffman Coding: Shorter Codes for Frequent Characters →← Pattern Matching: Finding a Word Inside a TextNext lesson: Huffman Coding: Shorter Codes for Frequent Characters →
In this lesson
How tries and radix tries store words for fast prefix queries.
- Build a trie and use end-of-word flags to tell words from prefixes
- Implement insert, contains, and starts-with in time proportional to word length
- Explain how autocomplete collects words alphabetically from a subtree
- Compare plain tries, radix tries, and hash sets on memory and speed
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,661 words). Read along, or search it.
Opening Question
Thumb Tabs and a Search Box
A printed dictionary has thumb tabs along its edge. To find carpet, nobody reads from the start. You jump to the C tab, then to the part where the second letter is A, and narrow down, letter by letter. Now picture a search box. As you type t, r, i, it must answer: which words start with tri? A hash table, so good at exact words, has no good way to answer that. So how should a vocabulary be stored, so that questions about beginnings are fast?
Core Idea
Words as Paths of Letters
A trie, pronounced try, from retrieval, turns that habit into a data structure. It's a tree in which every step down follows one letter. A word is stored as a path from the top. And all the words that start the same way share the beginning of their path. It matters most for large vocabularies: spell checkers, search suggestions, phone keyboards, and contact lists that complete a name as you type.
Worked Example
Six Words in Ten Nodes
Here's a trie holding six words: car, card, care, cat, do, and dog. The root stands for the empty prefix. Below it, c and d. Every other node stands for the prefix spelled on the way down to it. Under c comes a, and the c-a node is shared by four words. Below it, r and t. Under r, the letters d and e finish card and care. And on the other side, d, o, and g spell do and dog. A node doesn't store its own letter. The letter is the label of the link leading into it. The six words hold nineteen letters, but need only ten nodes, root included.
End-of-Word Flag
Telling Words From Prefixes
So each node holds two things: a way to find the child for each possible next letter, and an end-of-word flag. The flag is essential. The node reached by c, a, r is a word, car, and also a stepping stone toward card and care. The node reached by c, a is only a prefix. It's not a word. Without the flag, the trie couldn't tell the two apart.
Node Design
Array Nodes Versus Map Nodes
There are two common ways for a node to find its child. An array node keeps one slot for every letter of the alphabet: twenty-six for lowercase English. The child is found by direct indexing. The letter r has index seventeen: r minus a. A map node keeps only the letters that are actually present, from letter to child. The array node finds a child instantly, but most of its slots are empty. The map node stores only what exists, and handles any characters at all, at the cost of some map overhead.
Operations
Insert, Contains, and Starts-With
To insert a word, start at the root and take one letter at a time. If the current node has no child for the letter, create one. Move to that child, and continue. After the last letter, set the end-of-word flag on the node where the path ends. To search, follow the same path without creating anything. If a child is missing, the word isn't stored. If the whole path exists, contains says yes only when the flag is set. Starts-with only asks whether the path exists. After inserting the six words: contains car is true, contains c-a is false, starts-with c-a is true, and starts-with c-o-b is false, at its second letter.
Running Time
Cost Grows With Word Length Only
Both operations take one step per letter: order L, for a word of length L. The cost doesn't depend on how many words are stored. A test used a real vocabulary of twenty-five thousand, five hundred twenty-seven words, about seven point six letters long on average. Stored as a thousand words, or ten thousand, or all of them, a search visited about eight point six nodes: the word length, plus the root. A binary search over the same sorted words would need more probes as the list grows, and each probe compares whole strings.
Quick Check
Counting Nodes for Five Words
Quick check. Into an empty trie, insert five words: to, tea, ten, in, and inn. How many nodes does the trie have, counting the root? Pause, and decide. Nine. The t node is shared by three words, and t-e is shared by tea and ten. That's t, o, e, a, and n. Then i, n, and a second n. Eight letter nodes, plus the root. Fourteen would be one node per letter, with nothing shared.
Autocomplete
Collecting a Prefix's Subtree
A prefix query asks for every stored word that starts with some text. In a trie, the answer is waiting in one place: the subtree below the node the prefix reaches. So autocomplete takes two steps. First, follow the prefix, letter by letter. Second, collect every word in the subtree below that node. The collection is a depth-first walk that visits children in letter order, a to z. Each time it reaches a node with the flag set, it records the text built so far. So the words come out in alphabetical order, with no sorting at all. Autocomplete of c-a gives car, card, care, cat. And a limit lets the walk stop once a search box has enough.
Prefix Cost
Trie Versus Hash Set for Prefixes
On the real vocabulary, the prefix t-r-i had forty matches, starting tri, trial, triangle, triangles. A prefix with no matches fails within a few steps. The cost is order L plus m, where m is the number of nodes in the subtree walked. It follows the matches, not the vocabulary. A hash set has no shortcut, because its entries are scattered with no relation between a word and its prefix. It must examine every entry. On a thousand random three-letter prefixes, both found the same fifty-nine thousand matches. The trie visited about a quarter million nodes. The hash set examined over twenty-five million entries, about a hundred times more.
Radix Trie
Merging Single-Child Chains Into Edges
Look at a trie for romane, romanus, and romulus. The letters r, o, and m form a chain: the r and o nodes each have exactly one child, and end no word. Such chains are common. In the full vocabulary, sixty-four percent of the plain trie's nodes had one child and ended no word. A compressed trie, also called a radix trie, merges each chain into a single edge that carries a whole string of letters. Now every node except the root either ends a word or has at least two children. The example shrinks from thirteen nodes to six, with edges rom, then an or ulus, and so on.
Edge Splitting
Inserting romulus After romanus
Inserting is the interesting part, because a new word may agree with an edge for only some of its letters. Then the edge must be split. Start with a radix trie holding only romanus. It's a single edge. Now insert romulus. It shares only r, o, m with that edge. So a new middle node is created after rom. The shared letters, rom, stay on the upper edge. The rest of the old label, a-n-u-s, moves to a new edge below the middle node. And a new edge, u-l-u-s, is added for the new word. The middle node now has two children, so it can't form a chain. The radix property holds.
Savings
Thirty-Six Percent of the Nodes
A larger example: seven words beginning r-o-m or r-u-b need twenty-eight nodes as a plain trie, and only fourteen as a radix trie. On the full vocabulary, the radix trie needed thirty-one thousand nodes: only thirty-six percent of the plain trie's eighty-seven thousand. Search and autocomplete still work as before. Each step now compares a whole edge label against the next part of the word, instead of a single letter.
Quick Check
Inserting roman Into a Radix Trie
Quick check. The radix trie for romane, romanus, and romulus has six nodes. Now insert one more word: roman. How many nodes does the radix trie have afterward? Pause, and decide. Still six. Roman follows the edge rom, then the whole edge a-n, and ends exactly at an existing node. Nothing is split and nothing is added. Insertion just sets that node's end-of-word flag. A split would happen only if roman stopped partway along an edge.
Trade-Offs
Memory and Lookup Speed Against a Hash Set
Is a trie always the better structure? The final test says no. First, memory. The plain trie saves fifty-five percent of the letters, but each array node reserves twenty-six slots. Only about four percent of them ever held a child. The hash set used one point six megabytes. The array trie used almost fourteen, about eight and a half times as much. The radix trie used about five. Then exact lookup. Half a million lookups took about eleven milliseconds with the hash set, and about four hundred twenty with the array trie: roughly forty times slower. A Java string remembers its hash code, so a lookup is one table access and one comparison. A trie lookup hops through about nine separate nodes, scattered across memory.
Decision Guide
When a Trie Earns Its Memory
So a hash set is the right tool when words are only ever looked up whole. A trie earns its memory when the program needs autocomplete, prefix counts, or alphabetical listing. And a radix trie is the usual choice when memory matters, since it keeps the prefix abilities at a fraction of the plain trie's size. Two cautions. An array trie crashes on a capital letter or a hyphen, because the character minus a goes negative. Normalize the input, or use a map node. And a trie finds words that start with a text, not words that merely contain it.
Key Takeaways
Tries in Brief
To sum up. A trie stores each word as a path of letters, and a flag marks which prefixes are words. Insert and search take order L for a word of length L, whatever the vocabulary size. Autocomplete follows the prefix and collects the subtree, in alphabetical order. A radix trie merges single-child chains into labeled edges, and splits an edge when a word shares only part of it. Against a hash set, a trie costs more memory and is slower for exact lookups, but it wins on prefixes.
Think About It
Finding Words That End in ing
Here's something to think about. A trie answers, which words start with tri, very quickly. How could you use a trie to answer, which words end with i-n-g? What would you store, and what would it cost?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Tries: Storing Vocabularies in Prefix Trees
What is a trie data structure?
How does autocomplete work with a trie?
What is a radix trie?
Is a trie faster than a hash set?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →