Can a trie or DAWG loop?

Question

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

bases:

foo
bar
baz

suffixes:

he
she
be
ke
la
ma
na
pa
po

composed words:

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?

Answer 1

I will try to answer your questions from my personal experience with tries. Some time ago I had to face a similar problem: I had to store all well-formed meaningful Italian words (300'000 more or less) using a trie for detecting duplicates in a text and possibly suggest them to the user during typing. I didn't have the necessity to match suffixes, however. In my use case, the matching algorithm was implemented in C++ and was quite efficient, it could answer in less than 50 milliseconds.

Telling whether the data structure is acceptable depends on you, which time guarantees do you want to achieve? In my case I had to support the user and as we know users are a slow information source.

If I were you I would first try something simpler: I would design the trie for matching words and in case a match exists, switch to a second trie that matches suffixes only. Consequently, the problem of matching suffixes would be captured by the second trie, and constraints could be encoded in the trie rather than annotated on the data structure. This would allow you to trade space for implementation simplicity: you could use the same matching algorithm for both tries. Since I don't know Turkish I don't know which combinations of suffixes make sense, but I would insert in the "suffixes trie" only those combinations that are meaningful. To recap my suggestion is: to collapse contraints in a second trie and see whether it is effective for your use case.

It is even possible the second trie should not be a trie, but the min-DFA matching meaningful suffixes. This would allow you to minimize the space required for matching suffixes, however, you must compute it using well-known algorithms.

Regarding literature, the use case you are mentioning reminds me of the problem considered in this article by Aho and Corasick, however, the encoding of loops in their case does not limit the number of matches you could have. The described automaton has loops but they are encoded through a separate function.

I hope this will be useful!