Re:Calculate the difference and intersection of any two regexes
by contravariant on Monday September 11, 2023 @02:43PM
(#37471759)
> 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.
Re:Calculate the difference and intersection of any two regexes
by Someone on Monday September 11, 2023 @03:50PM
(#37472692)
If 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_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.
Automata are really a lost art in modern natural language processing. We used to do things like store a large vocabulary in an deterministic acyclic minimized automaton (nice and compact, so-called dictionary automaton). And then to find, say all words within Levenshtein distance 2 of hacker, create a Levenshtein automaton for hacker and then compute (on the fly) the intersection between the Levenshtein automaton and the dictionary automaton. The language of the automaton is then all words within the intersection automaton.
I wrote a Java package a decade ago that implements some of this stuff:
https://github.com/danieldk/dictomaton