Looking for a good introduction on trie [closed]

S

5

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

Slugabed answered 21/5, 2012 at 11:45 Comment(3)

Related: #624392 – Severson 21/5, 2012 at 11:50

I am not looking for an implementation to use.I want to study the concept – Slugabed 21/5, 2012 at 11:51

@Slugabed Did you find an acceptable answer? – Demonstration 28/5, 2012 at 18:52

D

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.

Demonstration answered 21/5, 2012 at 12:41 Comment(8)

Thank you. I will read this. Do you have some reference for background info on trie? – Slugabed 21/5, 2012 at 13:3

I mostly used Wikipedia's description and pictures. There was another site I used, I'll see if I can find it. – Demonstration 21/5, 2012 at 13:9

I am looking into your code.I was wondering it does not create a full tree right? – Slugabed 24/5, 2012 at 5:47

I'm not sure I know what you mean by full tree. It creates a node for each unique letter in each string. – Demonstration 24/5, 2012 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'. – Demonstration 24/5, 2012 at 14:41

I was perhaps confused as I am also reading about suffix trees.They are compressed sufix tries? – Slugabed 28/5, 2012 at 5:41

Also how come you used CharSequence? – Slugabed 28/5, 2012 at 5:43

I used CharSequence, so the Trie can represent a CharBuffer, String, or StringBuffer, not just limited to String. – Demonstration 28/5, 2012 at 12:41

L

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.

Lillith answered 21/5, 2012 at 12:4 Comment(4)

I'll read your link. Also do you have a recomendation of textbook that dedicates a section specifically on Trie? – Slugabed 21/5, 2012 at 12:23

@Slugabed - no I don't. But some online bookstores allow you to view the table of contents of text books ... – Lillith 21/5, 2012 at 12:50

Actually the blog you linked to is quite good! +1 from me – Slugabed 22/5, 2012 at 7:18

+1 from my side as well....it really is a good source:) – Swaddle 10/6, 2012 at 17:51

E

1

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

Excommunication answered 21/5, 2012 at 11:49 Comment(2)

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 – Slugabed 21/5, 2012 at 11:54

help yourself... reading that article tells you everything you need to know about what's a trie and how it works – Excommunication 21/5, 2012 at 12:16