The Giving Trie

 Alternative Titles:

A Trie Grows in Palo Alto

The Trie of Life

The Best Time to Make a Trie is Twenty Years Ago, the Second Best Time is Now

The Trie of the Knowledge of 1 and 0

If a Trie Fails and No One Sees the Error, Does The Code Compile?


What is a Trie?

A trie (generally pronounced like "tree") is a searchable tree that has individual letters for nodes.  So in the example above, we have the following keys associated with their values:

"to": 7

"tea": 3

"ted": 4

"ten": 12

"A": 15

"i": 11

"in": 16

"inn": 25

Keys are only complete when you run into a value - so just "t" or "te" by themselves do not constitute keys for this trie.

Tries are sort of a niche data structure, but they do have some advantages: the lookup time for a trie will only ever be at most the length of the longest key.  In comparison to a binary search tree - which can at most have only 2 sub-trees coming off of each node - a trie can be very, very wide (as wide as the number of available letters for your key string), which can make for some crazy efficient searches.  In fact, you can view natural language, either spoken or written, as a trie, with the words of the language corresponding to keys and their meanings corresponding to the values.

While slower than hashes, tries have an advantage over them in that tries avoid collisions - where two values have the same key (due to a too-short input key size creating only a finite number of keys smaller than the number of values, or hashing function that incorrectly assigns two values to the same key).  On the other hand, tries often require an individual block of memory for each character in a key string, as opposed to a single block of memory for a hash key.

Tries are most often used in predictive text in things like phone autocompletes, web searches, etc. - as the user types in letters we transverse further down the trie and as the possible nodes thin out we can easily suss out what possible words users are going to write.

Tries are also used for IP routing as (see an example here) in the form of Patricia tries, a special type of trie in which nodes with only one child are merged with the parent node.  The ability of a Patricia trie to quickly deal with long prefixes makes them especially well-suited to this application. 

Examples

Here are some good implementations of Tries in my preferred languages:

JavaScript example

JavaScript example of a radix trie

Ruby example

In an exploit of writable or executable code



Comments

Post a Comment

Popular posts from this blog

The Sorting Hat

Image
Here's a lesson about the difference between theory and practical applications. Everyone knows about  bubble Sort  and  merge Sort  - they're probably the first two sorting algorithms you learned.  Everyone also knows that (1) bubble sort sucks and (2) this is due to the fact that its average time complexity is O(n^2), aka the worst time complexity.  It even generally performs worse than things like insertion sort and  selection sort , the "a D- is still a passing grade" of sorting algorithms. While all these things are true, there's a more important truth: always test your code. While reading  The Imposter's Handbook by Rob Conery  the other day and flipping through the comparison sort algorithms he provides, I decided, Why not actually test out this code?   And, the  speed test demon  that I am, my test involved sorting out his [23,4,42,15,16,8] array one million times with bubble sort and with merge sort, and I got this res...
Read more

Kadane's Algorithm

Imagine it is 1977.  You do not have a degree in computer science.  You have not spent months grinding leetcode.  You are given a algorithm problem that a decorated mathematician has already created what looks like an optimal solution. And then in less than a minute you come up with a better answer. You are  Jay Kadane , and the problem that you have solved is the maximum subarray problem. The maximum subarray problem gives you an array of numbers and asks you to pick out the subarray with the largest sum.  The problem is trivial if all the numbers are positive: [ 1 , 5 , 1 , 3 , 2 ] <- the largest subarray is obviously the entire array But what if you've got some negative numbers thrown in there? [ 1 , 5 , -1, 3 , - 2 ] <- sure, you don't want the negatives. But isn't taking the -1 worth the +3? A brute-force solution materializes pretty easily: just create every subarray and find the biggest sum: [ 1 ] = 1 [ 1 , 5 ] = 6 [ 1 , 5 , - 1 ] = 5 ...
Read more

Loose Equality, the Null Operator, and Other Oddities

 Here's a fun bit of code to run: console . log ( '0.5' == 0.5 ) //evaluates to true console . log ( '0.5' === 0.5 ) //evaluates to false The first equality statement is what's known in JavaScript as "abstract equality comparison", which people usually refer to as "loose equality."  Loose equality compares objects only after doing a type conversion - so even though '0.5' is a string and 0.5 is a number, JavaScript sort of jams them together and says "sure, good enough."  It's weird, but convenient sometimes when dealing with data that's really (in an abstract sense) numbers but could come through the pipes as either a number or a string. People have written surprisingly long algorithms to precisely define what  abstract equality  and  strict equality (aka, normal equality)  mean in JavaScript and other languages that adhere to the ECMAScript standards.  But for our regular usage, things that are to people the same ...
Read more