6

I am looking for a good introduction/tutorial on Tries.
Most of the links I find googling are either too succint and abstract for me or too trivial.
Could someone please provide a good reference with examples in Java for me to study?

Thanks

Jim
  • 18,826
  • 34
  • 135
  • 254

5 Answers5

2

Googling found this blog with a series of articles in Java.

But I'd recommend buying a text book. Lots of Java oriented books on Data Structures and Algorithms are available from your favourite online bookstore.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
1

Sure, have a look at Steve Hanov's site, like Fast and Easy Levenshtein distance using a Trie.

Gregory Pakosz
  • 69,011
  • 20
  • 139
  • 164
  • Thank you, but the link is about using a Trie to improve on `Levenstein` and it assumes you know what a Trie is, more or less, and it is in Python, which I don't know at all – Jim May 21 '12 at 11:54
  • help yourself... reading that article tells you everything you need to know about what's a trie and how it works – Gregory Pakosz May 21 '12 at 12:16
1

I've recently coded up a Trie and Patricia Trie in Java. They are written to be easy to follow. All the data structures were built from their Wikipedia descriptions.

Related classes: Radix Trie, Suffix Trie, Trie Map.

If you have any questions, feel free to ask.

Justin
  • 4,196
  • 4
  • 24
  • 48
  • Thank you. I will read this. Do you have some reference for background info on trie? – Jim May 21 '12 at 13:03
  • I mostly used Wikipedia's description and pictures. There was another site I used, I'll see if I can find it. – Justin May 21 '12 at 13:09
  • I am looking into your code.I was wondering it does not create a full tree right? – Jim May 24 '12 at 05:47
  • I'm not sure I know what you mean by full tree. It creates a node for each unique letter in each string. – Justin May 24 '12 at 14:16
  • A trie is a prefix tree, so all strings inputted into the trie with a common prefix would share the same nodes off the root. If the trie has two strings named bat and bag inputted. The root would have one node hanging off with the value 'b' which has a single child with a value of 'a'. The 'a' node would have two children with values 't' and 'g'. – Justin May 24 '12 at 14:41
  • I was perhaps confused as I am also reading about `suffix trees`.They are compressed `sufix tries`? – Jim May 28 '12 at 05:41
  • Also how come you used `CharSequence`? – Jim May 28 '12 at 05:43
  • I used CharSequence, so the Trie can represent a CharBuffer, String, or StringBuffer, not just limited to String. – Justin May 28 '12 at 12:41
0

I recommend Stefan Nilsson's Ph.D. thesis from 1996, Radix Sorting & Searching (The searching part is what you are looking for.) It is quite an easy read for a research publication and contains a lot of both theory and practice about tries.

The examples are in C, not Java, but you shouldn't have much trouble understanding them if you know Java.

njlarsson
  • 2,128
  • 1
  • 18
  • 27
0

Found this topcoder link on trie quite useful :

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

rai.skumar
  • 10,309
  • 6
  • 39
  • 55