Präfixvergleich/Trie für Java?

Question

Ich portiere über ein C-Programm nach Java. Ich muss Präfix-Lookups machen.

z.B. Bei den Tasten "47" , "4741", "4742 sollte ein Eingang von "474578" den Wert für "47" ergeben, "474153" würde dem Schlüssel "4741" entsprechen.

In C habe ich dies mit einem Trie implementiert, der ungefähr 100k Schlüssel enthält. Ich brauchte nur die Schlüssel zu beachten, die die ASCII-Zeichen [0-9] enthielten, sie müssen sich nicht um vollständig durchgebrannte Unicode-Strings kümmern.

Wie auch immer, gibt es vorhandene Java-Bibliotheken, die ich dafür verwenden kann?

Answer 1

Angenommen, Sie suchen nach dem am längsten übereinstimmenden Schlüssel, können Sie eine einfache Implementierung this looks like to be what you need verwenden. Die hier verwendete CharSequence-Schnittstelle ist implementiert durch java.lang.String

AFAIK gibt es keine solche Klasse in JRE-Bibliotheken enthalten.

Ich würde proably versuchen, dies zu tun mit einem sortierten Array und einer modifizierten binären Suche

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