前缀匹配/ trie for Java？

Question

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

例如给定密钥"47" , "4741", "4742输入"474578"应该产生"47"的值，​​将匹配"4741"密钥。

在C中，我用一个持有大约100k个键的trie实现了这个，我只需要关心包含ascii字符[0-9]的键，不需要关心完整的unicode字符串。

无论如何，是否有任何现有的Java库可用于此？

Answer 1

假设你不想用最长的匹配键来查找，你可以使用一个简单的实现this looks like to be what you need。此处使用的CharSequence接口由java.lang.String执行

AFAIK在JRE库中没有包含这样的类。

我会proably尝试用排序阵列和改进型二分查找

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