前綴匹配/ 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)); 
     } 
    } 
}