11 ms·
> deterministic acyclic minimized automaton That's basically a Trie right? To be fair I have only heard of them and know they can be used to do neat tricks, I'
by contravariant 3y ago
> deterministic acyclic minimized automaton
That's basically a Trie right? To be fair I have only heard of them and know they can be used to do neat tricks, I've rarely used one myself.
- Someone 3y agoIf you do not plan to update it often and don’t need to store extra data with each word, a dawg (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...) is more compact. You often can merge leaf nodes. For example, if you have words talk talked talking talks walk walked walking walks there’s no need to repeat the “”, “ed”, “ing”, “s” parts.
- microtonal 3y agoNo. In a minimized automaton shared string suffixes also share states/transitions.