You probably thought this was one of my political posts right? Well, it’s about algorithms, so if you only read my posts on voting and trump and whatnot, this probably isn’t for you. Okay, maybe the picture gave it away, and maybe the second half of the title did too.

Okay now, let’s get to the post. Tries are actually data structures which store words. You can see that the example on top of the post is storing the words to, tea, ted, ten, and inn. You can easily find any word quickly. Say I want to find all the words that start with the prefix ‘te’. I simply go from the root node(top node) to the ‘t’ node, then from the ‘t’ node to the ‘te’ node. Everything under the ‘te’ node will start with ‘te’. This type of data structure is used to play word games like Scrabble, and also to autocomplete sentences on your phone.

In fact, autocomplete is the exact reason I came across tries. I learned about tries in the book The CS Detective, by Jeremy Kubica. I later decided to make an autocomplete program on my website. But, it would use word patterns similar to those in Donald Trump’s tweets, speeches, debates, and interviews. In short, it would let you type in the style of Donald Trump!

For my Donald Trump program, I needed a trie that you could add words to easily and quickly. I finally came up with a script involving 3 classes. This will add words from a text file into the trie, and then search the trie for any words that start with a given prefix. The gist is right here:

This example loads in the text file ‘loremipsum.txt’, and searches for words starting with the prefix ‘lo’. All I had to do was load a file of Donald Trump’s speeches, tweets, debates, and interviews instead of some lorem ipsum. Then, I had to link the program to a Rails form. Finally, I finished the program which is available for you to try with this link.

Print Friendly