Java的前缀匹配/ trie？

Question

我正在将一个C程序移植到Java.我需要做前缀查找.

例如,给定键"47" , "4741", "4742的输入"474578"应该产生值"47","474153"将匹配"4741"键.

在CI实现这一点,一个trie持有大约100k键,我只需要关心包含ascii字符[0-9]的键,不需要关心完全吹制的unicode字符串.

无论如何,我可以使用任何现有的Java库吗？

Answer 1

假设您不想按最长的匹配键进行查找，您可以使用一个简单的实现，这看起来就是您所需要的。这里使用的CharSequence接口是由java.lang.String实现的

AFAIK JRE 库中不包含此类。

我可能会尝试使用排序数组和修改后的二分搜索来做到这一点

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