3 ms·
Directed acyclic word graphs (DAWGs)! They’re like tries, but with identical subtrees glued together. They’re capable of encoding real-world dictionaries of mi
by nathell 4y ago
Directed acyclic word graphs (DAWGs)!
They’re like tries, but with identical subtrees glued together. They’re capable of encoding real-world dictionaries of millions of words into ~1 byte per word, when stored cleverly (see [0]). They let you do things like efficiently finding a list of words in a dictionary whose Levenshtein’s distance to a given word is less than x. Their cousins, GADDAGs, are _the_ data structure of choice in Scrabble-playing engines.
[0]: http://www.jandaciuk.pl/fsa.html http://www.jandaciuk.pl/fsa.html
- microtonal 4y agoAlso related: Levenshtein automata -- automata for words that match every word within a given Levenshtein distance. The intersection of a Levenshtein automaton of a word and a DAWG gives you an automaton of all words within the given edit distance. I haven't done any Java in years, but I made a Java package in 2013 that supports: DAWGs, Levenshtein automata and perfect hash automata: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton