Соответствие префикса / Trie для Java?

Question

Я портирую через C-программу на Java. Мне нужно сделать поиск префикса.

например. учитывая, что ключи "47" , "4741", "4742 при вводе "474578" должны давать значение для "47", "474153" будет соответствовать клавише "4741".

В C я реализовал это с помощью дерева, содержащего около 100 тыс. Ключей, мне нужно только заботиться о ключах, содержащих символы ascii [0-9], не нужно заботиться о полностью перенесенных строках юникода.

В любом случае, существуют ли какие-либо библиотеки 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 ));
        }   
    }
}