Where Do I Find a Standard Trie Based Map Implementation in Java

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

You might want to look at the Trie implementation that Limewire is contributing to the Google Guava.

Does the Java API or an open source library provide for a TreeMap-like data structure with constant-time lookup?

Only if your keys adhere to a pattern that you can take advantage of in the data structure.

A good example would be a TrieMap. See Wikipedia for a description and here for a discussion containing references to implementations.

I posted a Trie implementation here some time ago. Not sure how efficient it is but it works. I have certainly improved it since that post.

Trie implementation in Java

First of all, when you insert a node, you should set end=true at the tail node. And then when lookup a prefix in Trie, you only need to find the node of last character in prefix and then get all strings recursively. Here is a example maybe could help you:

public class Trie {

private class Node{
    private Map<Character, Node> children;
    boolean end;

    public Node(){
        children = new HashMap<>();
        end = false;
    }
}

private Node root;

public Trie(){
    root = new Node();
}

public void insert(String word){
    Node current = root;
    for (int i=0; i < word.length(); i++){
        char c = word.charAt(i);
        Node node = current.children.get(c);
        if(node == null){
            node = new Node();
            current.children.put(c, node);
        }
        current = node;
    }
    // Set end to true
    current.end = true;
}

public boolean search(String word){
    Node current = root;
    for(int i =0; i < word.length(); i++){
        char c = word.charAt(i);
        Node node = current.children.get(c);
        if(node == null)
            return false;
        current = node;
    }
    return current.end;
}

private List<String> getAll(String prefix, Node node) {
    List<String> r = new ArrayList<>();
    if (node.end) {
        r.add(prefix);
    }
    for (Map.Entry<Character, Node> child : node.children.entrySet()) {
        List<String> subSuffix = getAll(prefix + child.getKey(), child.getValue());
        r.addAll(subSuffix);
    }
    return r;
}

public List<String> returnAllChildren(String str){
    List<String> r = new ArrayList<>();
    Node current = root;
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        Node node = current.children.get(c);
        if (node == null) {
            // Not found
            return r;
        }
        current = node;
    }
    // If you don't need the prefix, you can just
    // return getAll("", current);
    return getAll(str, current);
}

public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("abc");
    trie.insert("abcd");
    trie.insert("ab");

    List<String> r = trie.returnAllChildren("a");
    for (String s : r) {
        System.out.println(s);
    }
}
}

Is there a Trie in Java?

There is no trie data structure in the core Java libraries.

This may be because tries are usually designed to store character strings, while Java data structures are more general, usually holding any Object (defining equality and a hash operation), though they are sometimes limited to Comparable objects (defining an order). There's no common abstraction for "a sequence of symbols," although CharSequence is suitable for character strings, and I suppose you could do something with Iterable for other types of symbols.

Here's another point to consider: when trying to implement a conventional trie in Java, you are quickly confronted with the fact that Java supports Unicode. To have any sort of space efficiency, you have to restrict the strings in your trie to some subset of symbols, or abandon the conventional approach of storing child nodes in an array indexed by symbol. This might be another reason why tries are not considered general-purpose enough for inclusion in the core library, and something to watch out for if you implement your own or use a third-party library.

Any trie implementation in java( with maven repo )

Check out concurrent-trees, which contains a concurrent Radix Tree/Patricia Trie implementation. It also has published artifacts to the standard maven repo.

Looking for a good introduction on trie

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.

Are Tries still a good idea on modern architectures?

I hadn't thought of this as an area of concern before, but now that you mention it, there are times when a standard Trie implementation might be handy. On the other hand, as far as I know, Tries are used by Python and Perl and other string-savvy languages that I use now.

Last I checked, which was ages ago, the BSD kernel code used Tries (Patricia Tries) in the code to select the best interface for sending packets. Looks like Wikipedia has some info.

---

Related Topics