Thực hiện tìm kiếm đối sánh tốt nhất trong Java

Question

Tôi đang cố gắng để có được kết hợp chuỗi phù hợp nhất để làm việc bằng cách sử dụng cấu trúc dữ liệu Java hiện có. Nó là khá chậm mặc dù, bất kỳ đề xuất để cải thiện hiệu suất của nó sẽ được hoan nghênh.

dữ liệu mẫu sẽ trông như thế này

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

do đó, một tìm kiếm phù hợp nhất trên phím = 0060175552020 sẽ trở lại 006017555

Một cách tôi có thể nghĩ là có nhiều đồ cây sử dụng băm để chuyển hướng dữ liệu vào các bản đồ khác nhau do đó làm cho khu vực tìm kiếm nhỏ hơn.

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

Sử dụng và floorEntry(K key) phương pháp TreeMap:

Trả về một ánh xạ khóa-giá trị gắn liền với phím lớn nhất nhỏ hơn hoặc bằng chìa khóa nhất định, hoặc null nếu không có chìa khóa như vậy.

Sau đây là đơn giản hóa. Mã thực sẽ cần tìm kiếm nếu tìm thấy mục nhập không hợp lệ, ví dụ: nếu bản đồ có khóa 0060175551000, trong trường hợp đó, bạn cần phải tìm tiền tố chung giữa khóa tìm kiếm và khóa được tìm thấy, sau đó thực hiện tra cứu lại. Rửa sạch và lặp lại.

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 

---

CẬP NHẬT Có mã đầy đủ, với vòng lặp cho tìm kiếm mở rộng.

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

thử nghiệm

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 

Answer 2

Tôi thích câu trả lời TreeMap, nhưng đối với đầy đủ các thuật toán tương tự, bây giờ với tìm kiếm nhị phân.

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

Thuật toán này là logarit đầu tiên và sau đó lặp lại. Nếu không có mục bị bỏ qua, thời gian logarit: tốt. Vì vậy, câu hỏi là, có bao nhiêu mục cần được bỏ qua.

Nếu bạn lưu trữ ở mọi yếu tố một tham chiếu đến tiền tố của nó: từ { "00601755511", "International" }, để { "006017555", "National" }, sau đó bạn sẽ chỉ cần làm theo các tiền tố liên kết trở lại.