Directed acyclic word graph
From Wikipedia, the free encyclopedia
A directed acyclic word graph (DAWG) is a data structure in computer science similar to a trie but much more space efficient. It is used to represent a set of strings and supports a constant time search operation. The lookup time is proportional to the length of the search string and is the same as an equivalent trie.
The primary difference between dawg and trie is the elimination of suffix redundancy in storing strings. The trie eliminates prefix redundancy since all common prefixes are shared between strings, such as between doctors and doctorate the doctor prefix is shared. In a dawg common suffixes are also shared, such as between desertion and desertification both the prefix deserti- and suffix -tion are shared. For dictionary sets of common English words, this translates into major memory usage reduction.
