Prefix matching/trie for Java ?

Question

I'm porting over a C program to Java. I need to do prefix lookups.

e.g. given the keys "47" , "4741", "4742 a input of "474578" should yield the value for "47" , "474153" would match the "4741" key.

In C I implemented this with a trie holding around 100k keys, I only neeed to care about keys containing the ascii chars [0-9], don't need to care about fully blown unicode strings.

Anyway, are there any existing Java libraries I can use for this ?

Answer 1

Assuming you wan't to lookup by the longest matching key, you could use a simple implementation this looks like to be what you need. The CharSequence interface used here is implemented by java.lang.String

AFAIK there is no such class include in JRE libraries.

I would proably try do this with a sorted array and a modified binary search

import java.util.ArrayList;
class Item {
    public Item(String key, String val) {
        this.key = key;
        this.val = val;
    }
    String key;
    String val;
};
public class TrieSim {

    private static Item binarySearch(Item[] a, String key) {
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int len = Math.min(key.length(),a[mid].key.length());
            String midVal = a[mid].key.substring(0,len);
            String cmpKey = key.substring(0,len);
            System.out.println( midVal + " ~ " + cmpKey );
            if (midVal.compareTo( cmpKey ) >0 ) 
                low = mid + 1;
            else if (midVal.compareTo( cmpKey) <0 )
                high = mid - 1;
            else
                return a[mid];
        }
        return null;
    }

    public static void main(String[] args) {

        ArrayList<Item> list = new ArrayList<Item>();
        list.add(new Item("47", "val of 47 "));
        list.add(new Item("4741", "val of 4741 "));
        list.add(new Item("4742", "val of 4742 "));
        Item[] array = new Item[list.size()];
        // sorting required here
        array = (Item[]) list.toArray( array );

        for (Item i : array) {
            System.out.println(i.key + " = " + i.val);
        }
        String keys[] = {  "474578" , "474153" };
        for ( String key : keys ) {
            Item found = binarySearch(array, key );
            System.out.println( key + " -> " + (found == null ?" not found" : found.val ));
        }   
    }
}