Hacker News new | ask | show | jobs
by thaunatos 3508 days ago
What do you think about finite state machines for storing strings? (http://blog.burntsushi.net/transducers/)

It doesn't support adding words at run-time, but it seems to have attractive space usage.

1 comments

If I recall correctly, that is kind of like a compressed trie, only instead of a tree one builds a directed acyclic graph. Basically, taking common suffixes into account aswell.

Space usage is indeed the biggest advantage, as you are reducing redundant branches from the tree for of a trie. Construction of these seems difficult (from the article, it seems to involve building the tree, and using hashes to find redundant branches.

I think I never gave them much thought because it doesn't work for suffix tries, which can be used not to search for prefixes (like a normal trie) but for substrings (considering them prefixes of suffixes). The optimalization to get the O(n^2) total length of all suffixes seem to make it hard to turn this into a DAG.