用 Java 实现最佳匹配搜索

我正在尝试使用现有的 Java 数据结构获得最佳匹配字符串匹配。虽然速度很慢，但任何提高其性能的建议都将受到欢迎。

样本数据看起来像这样

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

因此，对键 = 0060175552020 进行最佳匹配搜索将返回 006017555

我能想到的一种方法是使用多个 TreeMap 使用散列将数据转移到不同的映射中，从而使搜索区域更小。

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

Use a TreeMap和floorEntry(K key) https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html#floorEntry-K- method:

返回与小于或等于给定键的最大键关联的键值映射，或者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);
}

Output

0060175552020
006017555=National

UPDATE有完整的代码，带有用于扩展搜索的循环。

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

Test

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

Output

0060175559138=VIP
006017555=National
null
null