Stack Overflow
Stack Overflow

Questions tagged [trie]

A tree-like data structure used to hold an associative array, also called a Prefix Tree.

Tries are specialized data structures where a word can be stored as a sequence of characters. Reading the word involves traversing down the branch of the tree. At each node, the possible completions of the partial word can be found by traversing down all possible paths to the leaf level. It is useful for implementing dictionary based functionality such as autocomplete.

1108 questions
164
votes
8 answers

How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?

So if I have to choose between a hash table or a prefix tree what are the discriminating factors that would lead me to choose one over the other. From my own naive point of view it seems as though using a trie has some extra overhead since it isn't…
Justin Bozonier
  • 7,584
  • 9
  • 44
  • 46
162
votes
16 answers

How to create a trie in Python

I'm interested in tries and DAWGs (direct acyclic word graph) and I've been reading a lot about them but I don't understand what should the output trie or DAWG file look like. Should a trie be an object of nested dictionaries? Where each letter is…
Phil
  • 13,875
  • 21
  • 81
  • 126
93
votes
7 answers

Suffix tree and Tries. What is the difference?

I am reading about Tries commonly known as Prefix trees and Suffix Trees. Although I have found code for a Trie I can not find an example for a Suffix Tree. Also I get the feeling that the code that builds a Trie is the same as the one for a Suffix…
Cratylus
  • 52,998
  • 69
  • 209
  • 339
83
votes
4 answers

Difference between Tries and Trees?

I remotely remember that tries don't store the whole data per node, only the suffix to the parent node. Where trees do store the whole data, but only organize themselves based on a prefix. So tries get smaller, which allows for example to compress…
The Surrican
  • 29,118
  • 24
  • 122
  • 168
80
votes
14 answers

Where do I find a standard Trie based map implementation in Java?

I have a Java program that stores a lot of mappings from Strings to various objects. Right now, my options are either to rely on hashing (via HashMap) or on binary searches (via TreeMap). I am wondering if there is an efficient and standard…
Uri
  • 88,451
  • 51
  • 221
  • 321
67
votes
12 answers

Trie implementation

Is there any speed- and cache-efficient implementations of trie in C/C++? I know what a trie is, but I don't want reinvent the wheel, implementing it myself.
Anton Kazennikov
  • 3,574
  • 5
  • 30
  • 38
48
votes
1 answer

Is there a Trie in Java?

Possible Duplicate: Where do I find a standard Trie based map implementation in Java? I want to use Trie in Java, is there an implementation I can use ? (I tried looking for one but I didn't found it).
Belgi
  • 14,542
  • 22
  • 58
  • 68
46
votes
7 answers

Trie vs. suffix tree vs. suffix array

Which structure provides the best performance results; trie (prefix tree), suffix tree or suffix array? Are there other similar structures? What are good Java implementations of these structures? Edit: in this case I want to make string matching…
David Campos
  • 1,287
  • 2
  • 13
  • 29
46
votes
1 answer

Trie complexity and searching

What is the complexity of creating a trie of a list of words and what is complexity of searching other set of word in that trie? Should I use trie for string searching, when i have hashtable?
Varun
  • 1,159
  • 1
  • 14
  • 19
42
votes
9 answers

How to create a trie in c#

Does anyone know where I can find an example of how to construct a trie in C#? I'm trying to take a dictionary/list of words and create a trie with it.
locoboy
  • 38,002
  • 70
  • 184
  • 260
39
votes
11 answers

Implementing a simple Trie for efficient Levenshtein Distance calculation - Java

UPDATE 3 Done. Below is the code that finally passed all of my tests. Again, this is modeled after Murilo Vasconcelo's modified version of Steve Hanov's algorithm. Thanks to all that helped! /** * Computes the minimum Levenshtein Distance between…
Hristo
  • 45,559
  • 65
  • 163
  • 230
35
votes
3 answers

How do you store a trie in a relational database?

I have a prefix trie. What is the recommended schema for representing this structure in a relational database? I need substring matching to remain efficient.
blank
33
votes
3 answers

Trie data structures - Java

Is there any library or documentation/link which gives more information of implementing Trie data structure in java? Any help would be great! Thanks.
JJunior
  • 2,831
  • 16
  • 56
  • 66
31
votes
4 answers

Need memory efficient way to store tons of strings (was: HAT-Trie implementation in java)

I am working with a large set (5-20 million) of String keys (average length 10 chars) which I need to store in an in memory data structure that supports the following operation in constant time or near constant time: // Returns true if the input is…
hashable
  • 3,791
  • 2
  • 23
  • 22
30
votes
4 answers

Hash Array Mapped Trie (HAMT)

I am trying to get my head around the details of a HAMT. I'd have implemented one myself in Java just to understand. I am familiar with Tries and I think I get the main concept of the HAMT. Basically, Two types of nodes: Key/Value Key Value Node: …
Justin
  • 4,196
  • 4
  • 24
  • 48
1
2 3
…
73 74