Kết hợp tiền tố/trie cho Java?

Question

Tôi đang chuyển qua chương trình C sang Java. Tôi cần phải tra cứu tiền tố.

ví dụ: được cung cấp các phím "47" , "4741", "4742 đầu vào là "474578" sẽ mang lại giá trị cho "47", "474153" sẽ khớp với khóa "4741".

Trong C tôi đã thực hiện điều này với một trie giữ khoảng 100k chìa khóa, tôi chỉ neeed để quan tâm đến các phím có chứa các ký tự ascii [0-9], không cần phải quan tâm về hoàn toàn thổi chuỗi unicode.

Dù sao, có bất kỳ thư viện Java hiện có nào mà tôi có thể sử dụng cho điều này không?

Answer 1

Giả sử bạn không thể tra cứu bằng khóa khớp dài nhất, bạn có thể sử dụng triển khai đơn giản this looks like to be what you need. Giao diện CharSequence được sử dụng ở đây được thực hiện bởi java.lang.String

AFAIK không có lớp nào như vậy trong thư viện JRE.

tôi proably sẽ cố gắng làm điều này với một mảng được sắp xếp và tìm kiếm nhị phân biến đổi

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