我正在尝试使用现有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;
}
用一个 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
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);
}
}
测试
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
我更喜欢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" }, 那么你只需要按照前缀后面的链接。