4 ms·
> That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. That sounds like a DAG-shaped FSM to me...? At least I can't
by jhgb 5y ago
> That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one.
That sounds like a DAG-shaped FSM to me...? At least I can't spot the difference.
- NieDzejkob 5y agoYeah, tries are special cases of FSMs, and so are DAWGs.
- jhgb 5y agoAh, apparently I didn't manage to connect the sentence I quoted with the preceding sentence. Now I get it.
- Someone 5y agoThat’s correct. https://en.wikipedia.org/wiki/Directed_acyclic_word_graph https://en.wikipedia.org/wiki/Directed_acyclic_word_graph links it to Deterministic acyclic finite state automaton (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...) I guess a strategy for compressing a word set could be to compile a regular expression recognizing it using a good regex engine and to then construct a compact representation of the resulting automaton.