Questions tagged [trie]
The trie tag has no usage guidance.
4
questions
0
votes
1
answer
24
views
Can a trie or DAWG loop?
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 ...
- 2,163
0
votes
0
answers
18
views
How to estimate the number of nodes in a trie based on a dictionary of words?
Say I want to build a trie out of 800,000 Sanskrit "base" words (in Devanagari script), with 20 prefixes and 2,000 possible suffixes. Each word is anywhere from 1-20 characters, and prefixes/...
- 2,163
0
votes
1
answer
44
views
Is this Patricia tree implementation wrong?
I'm reading the chapter Radix Search of the book Algorithms (Robert Sedgwick).
I've made a simple implementation and something isn't behaving as expected.
In program ...
1
vote
0
answers
77
views
Efficient generalized suffix array/tree construction for prefix trees
Is there any algorithm that can efficiently construct a generalized suffix tree or array (or something similar) for a set of strings represented by a prefix tree (trie)?
In particular, I'm wondering:
...
- 1,167