I am looking at DAWGs, which are compressed tries, like this:
It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure.
For example, I am thinking how to represent and store Turkish words in some sort of trie. Turkish can have almost an infinite number of words, because allows "sentence words" basically. They are formed from a word "base", and a set of suffixes, out of say ~1000 possible suffixes. So you can have upward of 10 suffixes appended to a base, that is 10^10 or at least 10 billion possibilities, on top of say 10,000 base words, that is a lot of possibilities. Maybe there are more or less, not totally sure, but it's probably too many to store in memory on a modest computer (and would be impractical).
So I'm imagining a case where you have a trie composed of the 11000 fragments (bases or suffixes). Each trie node has a
constraint which says that if it is a "leaf", whether or not it is accepted as a fragment. So say you have these example fragments and composed "words":
foo bar baz
he she be ke la ma na pa po
fooheshebelanapo foo fooshelapo barla bazpomala ...
The constraint might say things like:
- You can't repeat a suffix more than once.
So suffixes and words would be marked
leaf: true, but with a
constraint: 'only-once' sort of thing on them. As you are traversing the trie, you would keep track of the serialized string you have traversed, and only "accept" the fragment if it statisfies the
only-once constraint when tested against the serialized string.
query: barlala b: not-accepted ba: not-accepted bar: ACCEPTED, now loop back around and start at the beginning of the trie barl: not-accepted barla: ACCEPTED, loop back... barlal: not-accepted barlala: not-accepted, because we already included that `la` suffix
Is this an acceptable data structure? Is there a better way to accomplish it? Once again, this would be 1 trie with 11000 fragments (10k words, 1k suffixes), and they would all loop, with constraints. Is there literature on such a structure, or any problems it will face? Can a DAWG loop basically? Will it solve this problem?