4 ms·
What do you think about finite state machines for storing strings? (http://blog.burntsushi.net/transducers/ http://blog.burntsushi.net/transducers/) It doesn't
by thaunatos 10y ago
What do you think about finite state machines for storing strings? (http://blog.burntsushi.net/transducers/ http://blog.burntsushi.net/transducers/)
It doesn't support adding words at run-time, but it seems to have attractive space usage.
- rocqua 10y agoIf 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.