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 ?
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 ));
}
}
}
