Tries with Swift

Tries with Swift

I‘ve been spending quite some time the past weeks studying up on data structures and algorithms. I came across very interesting data structure that I had not encountered up until this time, I’m sure it would of been handy many a time ago, called “Tries”.

Tries are very handy for adding meta data onto permutations of words. A Trie can host a series of permutations for similar items, whereby each node’s position infact defines it’s content. If we take the two words Base and Bass, our Trie would have a root node of B, then a child of A, then a child of S. S now will have two children, S and E to make up the words Base & Bass.  So if we discovered ourselves on the S node, we could print out the stack we’re on, the current path we’re sitting on, and that would give us the word. Similarly if we were on the 2nd last S node, we could find 2 children, or, 2 possibilities to auto correct the user’s input.

Now tries are great for auto correct, but instead of just throwing back all children to the node for autocorrect we can add additional meta data to our nodes, for instance, the children of the node I’m looking at, which ones are infact words themselves. For that we can add a flag to each node signifying it itself is a word, and that it may even have more children. Like Base is a word, but also Baseball.

Creating a Trie in Swift

Here we will be creating a Trie with four words using Swift. Wumpus, Wumpette, Bambi & Baseball. Our root node will have a blank key, but our tree will start with two nodes under the root node, W & B. Feel free to load this up into the playground.

Searching our Trie

So let’s take some user input now and determine all the possible words that can be autocompleted. So if we now have two words Bass and Base, if we type in our Trie will show us that Base and Bass are available as we have flagged these as words.

Word Search

So one letter auto completes aren’t too handy right? Well we can do better with a Trie. Let’s expand this to do some more searching to get all the words available to us back in a list.

Introducing breadth first searches. We’re after the closest matches possible, so we start with shallow searches from our node we’ve found:

We’ll also need some changes made to our Search Trie method so that it returns full words and not just a single character:

My setup was pretty simple:

Searching this gives me [“Baseball”, “Basely”] How good!

Closest matches first please

Because we’ve returned our Trie Objects themselves we can now go about sorting them by the depth away from the original word found. Swift makes this pretty easy with function chaining:

Now my results are [“Basely”, “Baseball”]

Some handy extensions

Playground

Feel free to grab the working code via the playground file here: Trie.playground

Posted by voidet

Categorised under ios
Bookmark the permalink or leave a trackback.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

or