Directed Acyclic Word Graph Overview

[00:00:00]
>> The next set of optimization that we wanna look at is we wanna look at this tree. Here's our trie tree implementation that we've been working with. We wanna think about our trie tree implementation and realize it does seem like there's a fair bit of kind of wasted space in this tree.

[00:00:17]
Look at all these extra nodes that are being created here that aren't there for any other purpose other than that's the structure of a trie tree is that it goes one letter at a time. In our particular dictionary case, we're not a child on top of those, so those are kind of wasted nodes.

[00:00:33]
You might think about it as, well, I could construct the trie tree but then go back and compact that trie tree and save a whole bunch of memory. Because I'm likely to have, on average, quite a few of these nodes that are just hanging out with no reason to be there.

[00:00:49]
They're intermediary nodes with no reason to be there. It turns out there is an actual term for these kinds of trees that have been compacted. A trie tree that has been compacted is referred to as a radix tree. So the way the compaction worked as you can see is that we just took the internal nodes, combine them into one connection and then made that connection the augmentation of all of the intermediate states.

[00:01:16]
So that LAP, for example there, LAP took the place of the nodes that were L, A and P separately, right? So at each one of these levels now, instead of only having single letters, we can also have multi-letter combinations as the children, as the end point. You wouldn't construct your tree this way cuz you couldn't possibly know in advance where those would need to be.

[00:01:41]
So you would construct a trie tree with single letters and then run an optimization step to effectively compress the tree down into this format. So that would end up saving potentially a significant amount of memory usage of your trie tree. In the case of doing something like autocompletes, that ends up being a pretty effective technique because you don't lose anything.

[00:02:10]
You haven't lost any information. You still know the words, you just do a lot less traversing. It's faster and uses a lot less memory. So most of the time, a production implementation would construct a trie tree and then compress it into something like this radix tree. Unfortunately for us, the way our algorithm works, a radix tree would not be the right data structure.

[00:02:35]
It would significantly complicate our algorithm and we would lose most of the performance benefit that we wanted. So I only wanted to show you that something like this exists and when you Google around, you'll find them. But in our particular exercise, this is not the right data structure.

[00:02:50]
And had we chosen this, we would have ended up beating our head against why is this so hard, and why doesn't it work and why is it not very performing? The reason why it would be difficult is because at every level, we currently take advantage of the fact that we can take a single letter out of our remaining letters and find a child node or not find a child node.

[00:03:10]
Here, we would actually need to enumerate all of the children of every node to see if there were any matches. Cuz that would end up creating a whole lot extra performance overhead and complication. However, there are other data structures and we have now, without possibly even some of you realizing it, we just made a giant leap.

[00:03:34]
Actually, kind of a tiny leap from tree data structures into graph data structures. Why is this a graph data structure? Well, you can easily see that it's a graph data structure because you have one or more nodes that have more than one parent. The H node has two parents.

[00:03:57]
It has the C parent and it has the A parent. That's what lets you know this is a graph instead of a tree, okay? This is referred to as, actually, it goes by a couple of different names. The first place that I found it was under the name DAFSA, D-A-F-S-A which stands for Directed Acyclic Finite State Automaton.

[00:04:22]
So that's a whole bunch of really fancy sounding computer science terms. Go back to your co-workers the next time you're at your work and say, I learned about directed acyclic finite state automata, and they'll probably buy you a free lunch, right? Because that's gonna sound really impressive. It's not quite as impressive as it sounds, but it sounds good.

[00:04:43]
The other way of referring to these is DAWG, D-A-W-G, Directed Acyclic Word Graph. And I like that name a lot better cuz that speaks to what we're creating here. We're creating a word graph. This Directed Acyclic Word Graph is, you see how it looks a lot smaller? It's doing the kind of compaction that a radix tree does, but it does it in a different way.

[00:05:11]
Instead of removing nodes, it creates these extra graph links within the tree. So we get the compaction of memory usage, but we still get the properties that we're going to be able to traverse this in a similar way to the way that we were traversing a trie tree.

[00:05:29]
It's not exactly the same cuz there are complexities in graphs, you have to worry about getting into loops and, I mean, into cycles and things like that. But it ends up significantly reducing the memory footprint of the data structure, and we'll see that in a moment. And it ends up creating a pretty significantly performance implementation.

[00:05:51]
Maybe not quite as nice as the trie tree, but a very performance of limitation and much better in memory. So it ends up creating for us a potentially a better balance than what we saw a few iterations back with the trie tree implementation that we did. This one shifts the balance a little bit and makes better usage of memory.

[00:06:11]
It pays a little bit more up front. A directed acyclic word graph is a much more complex data structure to create. And we are not going to learn the algorithms of compaction that end up creating all these links. Those algorithms are significantly out of scope for our discussion.

[00:06:28]
And also, even if I taught them to you, it's so complex that I would never recommend writing this code yourself. We have firmly crossed into the area where you wanna use a known and battle-tested library to do this. And I have included for you an implementation of this from a library called Minimal Word Graphs.

[00:06:48]
That's a library that I found out there, and I've included an implementation of that, and that's what we're gonna use.