在Java中实现最佳匹配搜索

Question

我正在尝试使用现有Java数据结构获得最佳匹配字符串匹配.但这很慢,任何改善其表现的建议都会受到欢迎.

Sample数据看起来像这样

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

Answer 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