5 ms·
Interesting stuff. The article is quite verbose -- here is the Cliff Notes versions: The trie is a well-known data structure for storing string sets or string
by haberman 11y ago
Interesting stuff. The article is quite verbose -- here is the Cliff Notes versions:
The trie is a well-known data structure for storing string sets or string-keyed maps (https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie). You can compress a trie by using a DAG/FSM instead of a tree -- this lets you share states for suffixes, whereas trees only let you share states for prefixes. But for large sets minimizing a DAG is too expensive to perform on the whole trie. If you insert the keys in-order, you can minimize the DAG on-the-fly much more cheaply.
If you have a map instead of a set, the DAG is called a FST (finite state tranducer) instead of a finite state acceptor. In this case every edge has some value that you accumulate into the final result. For example, if the map values are integers, each edge can be an integer that is added to the final result. It takes a bit more cleverness in the algorithm to share prefix/suffix states while maintaining the tranducer invariants.
- burntsushi 11y agoOP here. That is an excellent summary. Thank you for that. :-) The length of these articles always surprises me. I start off with a simple idea: "I just want to explain this data structure." But when I join that with my desired target audience (some programming, some data structure experience), it takes a lot to explain and build up each idea with good examples!
- nickpsecurity 11y agoOther commenters mention that you've rediscovered an old technique. You still get my props for being clever enough to do that. :) Nonetheless, might be worth digging through any surveys of FSM's now to see what else you might find, eh?
- burntsushi 11y agoWell, I wouldn't say I rediscovered it. I knew it was old. Sorry if I had given the wrong impression! My references section[1] includes citations going back to at least 2000, but the technique is certainly older than that. (I'm not so sure the algorithm for construction presented in the article is older though. As far as I know, it was a novel result for Daciuk, Mihov and Watson in 2000.) [1] - http://blog.burntsushi.net/transducers/#references http://blog.burntsushi.net/transducers/#references
- nickpsecurity 11y agoYes, my skimming didn't catch that. So, you started with something that was once shown to work and got results with modern tech/problems. Still a good way to do programming.
- burntsushi 11y agoHmm. I'm not quite sure what you mean. I guess I had two primary motivations for writing the blog: 1. The knowledge I gained while writing the `fst` crate was difficult to obtain. I hoped to distill some of it down into a more easily consumable format so that others could learn more quickly than I could. 2. Advertise a real implementation that someone can actually use, or failing that, port to another language.
- nickpsecurity 11y agoMakes sense. Posts on solutions promoting comprehension and immediate utility are always good to have. You seemed to have pulled it off except maybe too long. You already noted that, though.
- scott_s 11y agoFor the record, I do not consider your writing "verbose". Writing advanced material for a beginner audience necessarily means you will have to explain a lot. That's okay.
- jhallenworld 11y agoVery nearly this same technique is used in glibc for representing unicode character classes. Essentially you save a huge amount of space by sharing common leaf nodes of the trie. I wrote code to construct these quickly during startup for JOE. I also noticed the minimizing you can do while building the trie in order: basically if the last constructed leaf matches the previous one, use it instead. In JOE we also have sets (for character class) or maps (for regex and case conversion tables).