在Java中實現最佳匹配搜索

我正在嘗試使用現有的Java數據結構來獲得最佳匹配字符串匹配。這是相當緩慢，任何改善其表現的建議將受到歡迎。在Java中實現最佳匹配搜索

樣本數據是這樣

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

等關鍵的最佳匹配搜索= 0060175552020將返回我能想到的是有使用哈希來轉移多個樹狀的006017555

的一種方式數據放入不同的地圖，從而縮小搜索範圍。

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

來源

2016-09-15 spakai

你可能會考慮使用這個https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm – Vihar

也有人建議Trie。會看看他們兩個。謝謝 – spakai

使用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

來源

2016-09-15 06:24:16 Andreas

'if（entry == null ||！key.startsWith（entry.getKey（））'但是一個非常好的解決方案。 –

我的評論有誤導性，您需要使用'getLowerEntry'循環並進行檢查。 –

@JoopEggen正如我在答案中所說的那樣，「再次進行查找，然後沖洗並重復」。 – Andreas

我喜歡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" },那麼只需要按照前綴的反向鏈接。

來源

2016-09-15 06:50:55

在Java中實現最佳匹配搜索

回答

相關問題