3 ms·
Also called DAWGs (Directed Acyclic Word Graphs [1]). John Resig blogged about a similar problem 5 years ago, for which I wrote a JavaScript solution [2]. [1]
by mckoss 11y ago
Also called DAWGs (Directed Acyclic Word Graphs [1]). John Resig blogged about a similar problem 5 years ago, for which I wrote a JavaScript solution [2].
[1] https://en.m.wikipedia.org/wiki/Directed_acyclic_word_graph https://en.m.wikipedia.org/wiki/Directed_acyclic_word_graph
[2] https://github.com/mckoss/lookups https://github.com/mckoss/lookups
- kmike84 11y agoAnother name for it is DAFSA (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...).
- danieldk 11y agoMy Java library, which does some of the things described in the article (DAWGS, perfect hashing, Levenshtein automata): https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
- kmike84 11y agoDAWG name is ambiguous, there are 2 different structures called DAWG - sometimes it is used as a synonym to DAFSA and sometimes it is used as a synonym to DAFSA which has all key substrings in it, not only keys. The linked DAWG wikipedia article is for a wrong one.
- ricardobeat 11y agoSimilar, but the data structure described here is a different kind of beast. It is more efficient, allows for fuzzy matching, regular expression searches and more.