Talk:Deterministic acyclic finite state automaton

Trade-off between DAWG and trie

It seems to me that there is a complication in replacing a trie with a directed acyclic word graph, but this is not mentioned in the article. Specifically, allowing nodes to have multiple incoming edges results in nodes that inherently represent (or store) multiple keys (e.g. both desertion and desertification, as in the article's example). This forces these nodes to be buckets, in the same way that a hash table has buckets for hash collisions. These collisions introduce a bit of extra complexity when growing or shrinking this data structure. When, where, and how should paths in the graph be split (to reduce the number of collisions) or joined (to preserve the storage space benefit)? In short, what are the algorithms associated with this data structure? Can someone with access to the article's reference elaborate on this? JCarlos 04:39, 22 October 2007 (UTC)[reply]

Contradiction in opening paragraph

Am I missing something here? The opening paragraph seems to have an inherent contradiction (emphasis mine):

"... 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."

Not to mention the fact that a DAWG doesn't look like it would support a constant-time search operation. --ian (talk) 18:00, 4 December 2007 (UTC)[reply]