Implementing a Patricia Trie for use as a dictionary
Posted
by Regis Frey
on Stack Overflow
See other posts from Stack Overflow
or by Regis Frey
Published on 2010-03-09T03:20:46Z
Indexed on
2010/03/09
3:36 UTC
Read the original article
Hit count: 651
I'm attempting to implement a Patricia Trie with the methods addWord()
, isWord()
, and isPrefix()
as a means to store a large dictionary of words for quick retrieval (including prefix search). I've read up on the concepts but they just aren't clarifying into an implementation. I want to know (in Java or Python code) how to implement the Trie, particularly the nodes (or should I implement it recursively). I saw one person who implemented it with an array of 26 child nodes set to null/None. Is there a better strategy (such as treating the letters as bits) and how would you implement it?
© Stack Overflow or respective owner