Выполнение поиска наилучшего соответствия в Java

Я пытаюсь получить подходящую строку соответствия, подходящую для работы с существующими структурами данных Java. Это довольно медленно, но любые предложения по улучшению его производительности будут приветствоваться.

Пример данных будет выглядеть следующим образом:

Key | V
--------------------- 
0060175559138 | VIP
--------------
006017555     | National
--------------
006017        | Local
---------------
0060          | X
--------------

поэтому лучший поиск соответствия на ключе = 0060175552020 вернется 006017555

Один из способов, о котором я могу думать, состоит в том, чтобы иметь несколько TreeMaps, используя хеширование, чтобы переадресовывать данные на разные карты, тем самым уменьшая область поиска.

private final TreeMap<String, V> index;

public Set<V> syncBestMatch(String key) {              
    Entry<String,V> entry = index.headMap(key, true)
                .descendingMap().entrySet().stream()
                .filter(e -> isPartiallyOrFullyMatching(key, e.getKey()))
                .findFirst()
                .orElseThrow(() -> new NoMatchException("No match found"));

    Set<V> results = new HashSet<>();
    results.add(entry.getValue());
    return results;
}

Ответы

Ответ 1

Используйте метод TreeMap и floorEntry(K key):

Возвращает отображение значения ключа, связанное с наибольшим ключом, меньшим или равным заданному ключу, или null, если такого ключа нет.

Упрощено следующее. Реальный код должен искать, если найдена недопустимая запись, например. если у карты был ключ 0060175551000, в этом случае вам нужно будет найти общий префикс между ключом поиска и найденным ключом, а затем повторите поиск. Промыть и повторить.

TreeMap<String, String> map = new TreeMap<>();
map.put("0060175559138", "VIP");
map.put("006017555"    , "National");
map.put("006017"       , "Local");
map.put("0060"         , "X");

String key = "0060175552020";
Entry<String, String> entry = map.floorEntry(key);
if (entry == null)
    System.out.println("Not found: " + key);
else {
    System.out.println(key);
    System.out.println(entry);
}

Выход

0060175552020
006017555=National

ОБНОВЛЕНИЕ Существует полный код с циклом для расширенного поиска.

private static Entry<String, String> lookup(NavigableMap<String, String> map, String key) {
    String keyToFind = key;
    for (;;) {
        Entry<String, String> entry = map.floorEntry(keyToFind);
        if (entry == null)
            return null;
        String foundKey = entry.getKey();
        int prefixLen = 0;
        while (prefixLen < keyToFind.length() && prefixLen < foundKey.length() &&
               keyToFind.charAt(prefixLen) == foundKey.charAt(prefixLen))
            prefixLen++;
        if (prefixLen == 0)
            return null;
        if (prefixLen == foundKey.length())
            return entry;
        keyToFind = key.substring(0, prefixLen);
    }
}

Тест

TreeMap<String, String> map = new TreeMap<>();
map.put("0060175559138", "VIP");
map.put("0060175551000", "Other");
map.put("006017555"    , "National");
map.put("006017"       , "Local");
map.put("0060"         , "X");

System.out.println(lookup(map, "0060175559138"));
System.out.println(lookup(map, "0060175552020"));
System.out.println(lookup(map, "0055708570068"));
System.out.println(lookup(map, "8684064893870"));

Выход

0060175559138=VIP
006017555=National
null
null

Ответ 2

Я предпочитаю ответ TreeMap, но для полноты тот же алгоритм, теперь с бинарным поиском.

String[][] data = {
        { "0060175559138", "VIP" },           // <-- found insert position
        { "00601755511", "International" },   // <-- skipped
        { "00601755510", "International" },   // <-- skipped
        { "006017555", "National" },          // <-- final find
        { "006017", "Local" },
        { "0060", "X" },
};
Comparator<String[]> comparator = (lhs, rhs) -> lhs[0].compareTo(rhs[0]);
Arrays.sort(data, comparator);

String searchKey = "0060175552020";
int ix = Arrays.binarySearch(data, new String[] { searchKey }, comparator);
if (ix < 0) {
    ix = ~ix; // Not found, insert position
    --ix;
    while (ix >= 0) {
        if (searchKey.startsWith(data[ix][0])) {
            break;
        }
        if (searchKey.compareTo(data[ix][0]) < 0) {
            ix = -1; // Not found
            break;
        }
        --ix;
    }
}
if (ix == -1) {
    System.out.println("Not found");
} else {
    System.out.printf("Found: %s - %s%n", data[ix][0], data[ix][1]);
}

Этот алгоритм первый логарифмический, а затем цикл. Если нет пропущенных записей, логарифмическое время: штраф. Итак, вопрос в том, сколько записей нужно пропустить.

Если вы сохраняете в каждом элементе ссылку на его префикс: от { "00601755511", "International" }, до { "006017555", "National" },, тогда вам нужно будет только следовать обратным ссылкам префикса.