Wednesday, June 15, 2011

Java Trie

I have been looking for some Java based string Tries, preferably one with compression. Here is what I've come up with so far.


There is a TernaryStringTrie in the jaspell.sourceforge.com http://jaspell.sourceforge.net/javadocs/pt/tumba/spell/TernarySearchTrie.html

There is the open patricia trie http://code.google.com/p/patricia-trie/

I just found a simple PrefixTrie one in strut2. http://struts.apache.org/2.2.3/struts2-core/apidocs/org/apache/struts2/util/PrefixTrie.html

I guess there is this one.
http://www.java2s.com/Open-Source/Java-Document/Internationalization-Localization/icu4j/com/ibm/icu/impl/CharTrie.java.htm

There is this one
http://www.digitaltsunami.net/projects/wordscope/site/apidocs/net/digitaltsunami/word/util/CharTrie.html

I would like something like the marisa trie implemented in java.
http://code.google.com/p/marisa-trie/

There is this one:
http://www.badgenow.com/p/radixtree/

This one works well: https://code.google.com/p/radixtree-java/

There is one here that gives a high degree of compression and sacrifices speed:
https://github.com/ning/tr13

Here is a nice comparison test that compares tr13 with hash implementations in terms of space and time.
http://groups.google.com/group/ning-tr13-users/msg/8c3e942335676b96

For compression I found the dsiutils project here