我正在尝试使用现有
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;
}
解决方法
使用TreeMap和
floorEntry(K key)方法：
Returns a key-value mapping associated with the greatest key less than or equal to the given key,or
nullif there is no such key.
以下简化.如果找到无效条目,则实际代码将需要搜索.如果地图有一个键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,"VIP");
map.put("0060175551000","Other");
map.put("006017555","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
