một phần phù hợp với chuỗi trong trường hợp List.contains (String)

Question

Tôi có một List<String>

List<String> list = new ArrayList<String>(); 
list.add("ABCD"); 
list.add("EFGH"); 
list.add("IJ KL"); 
list.add("M NOP"); 
list.add("UVW X"); 

nếu tôi làm list.contains("EFGH"), nó sẽ trả true. Tôi có thể nhận được sự thật trong trường hợp list.contains("IJ") không? Tôi có nghĩa là, tôi có thể một phần phù hợp với chuỗi để tìm thấy nếu họ tồn tại trong danh sách?

Tôi có danh sách 15000 chuỗi. Và tôi phải kiểm tra khoảng 10000 chuỗi nếu chúng tồn tại trong danh sách. Điều gì có thể là một cách khác (nhanh hơn) để làm điều này?

Cảm ơn.

Answer 1

Có lẽ bạn muốn đặt mỗi nhóm chuỗi vào một HashSet, và theo phân đoạn, tôi có nghĩa là không thêm "IJ KL" mà là thêm "IJ" và "KL" riêng biệt. Nếu bạn cần cả danh sách và khả năng tìm kiếm này, bạn có thể cần duy trì hai bộ sưu tập.

Answer 2

Bạn có thể lặp qua danh sách, sau đó gọi hàm contains() trên mỗi Chuỗi.

public boolean listContainsString(List<string> list. String checkStr) 
{ 
    Iterator<String> iter = list.iterator(); 
    while(iter.hasNext()) 
    { 
     String s = iter.next(); 
     if (s.contain(checkStr)) 
     { 
      return true; 
     } 
    } 
    return false; 
} 

Điều gì đó tương tự sẽ hiệu quả, tôi nghĩ vậy.

Answer 3

Là câu trả lời thứ hai, khi đọc lại câu hỏi của bạn, bạn cũng có thể kế thừa từ giao diện List, chỉ dành cho Strings và ghi đè phương thức contains().

public class PartialStringList extends ArrayList<String> 
{ 
    public boolean contains(Object o) 
    { 
     if(!(o instanceof String)) 
     { 
      return false; 
     } 
     String s = (String)o; 
     Iterator<String> iter = iterator(); 
     while(iter.hasNext()) 
     { 
      String iStr = iter.next(); 
      if (iStr.contain(s)) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 
} 

Đánh giá bởi nhận xét trước đây của bạn, đây có thể không phải là tốc độ bạn đang tìm kiếm, nhưng điều này có tương tự với những gì bạn đang yêu cầu không?

Answer 4

Làm thế nào về:

java.util.List<String> list = new java.util.ArrayList<String>(); 
list.add("ABCD"); 
list.add("EFGH"); 
list.add("IJ KL"); 
list.add("M NOP"); 
list.add("UVW X"); 
java.util.regex.Pattern p = java.util.regex.Pattern.compile("IJ"); 
java.util.regex.Matcher m = p.matcher(""); 
for(String s : list) 
{ 
    m.reset(s); 
    if(m.find()) System.out.println("Partially Matched"); 
} 

Answer 5

Nếu gợi ý từ Roadrunner-EX không đủ rồi, tôi tin rằng bạn đang tìm kiếm Knuth–Morris–Pratt algorithm.

Thời gian phức tạp:

• Time độ phức tạp của thuật toán bảng là O (n), tiền xử lý thời gian
• Thời gian phức tạp của thuật toán tìm kiếm là O (k)

Vì vậy, độ phức tạp của thuật toán tổng thể là O (n + k).

• n = Kích thước của danh sách
• k = chiều dài của mẫu bạn đang tìm kiếm

Bình thường Brute-Force sẽ có độ phức tạp thời gian O (nm)

Hơn nữa thuật toán KMP sẽ có cùng độ phức tạp O (k) để tìm kiếm với cùng chuỗi tìm kiếm, mặt khác, nó sẽ luôn là O (km) cho phương pháp tiếp cận vũ lực.

Answer 6

Dưới đây là một số mã sử dụng regex để tắt vòng lặp bên trong nếu không có của chuỗi kiểm tra được tìm thấy trong chuỗi mục tiêu.

public static void main(String[] args) throws Exception { 
    List<String> haystack = Arrays.asList(new String[] { "ABCD", "EFGH", "IJ KL", "M NOP", "UVW X" }); 
    List<String> needles = Arrays.asList(new String[] { "IJ", "NOP" }); 

    // To cut down on iterations, create one big regex to check the whole haystack 
    StringBuilder sb = new StringBuilder(); 
    sb.append(".*("); 
    for (String needle : needles) { 
     sb.append(needle).append('|'); 
    } 
    sb.replace(sb.length() - 1, sb.length(), ").*"); 
    String regex = sb.toString(); 

    for (String target : haystack) { 
     if (!target.matches(regex)) { 
      System.out.println("Skipping " + target); 
      continue; 
     } 

     for (String needle : needles) { 
      if (target.contains(needle)) { 
       System.out.println(target + " contains " + needle); 
      } 
     } 
    } 
} 

Output:

Skipping ABCD 
Skipping EFGH 
IJ KL contains IJ 
M NOP contains NOP 
Skipping UVW X 

Nếu bạn thực sự muốn có được dễ thương, bạn có thể chia hai nga sử dụng tìm kiếm nhị phân để xác định các nhóm trong danh sách mục tiêu phù hợp, nhưng nó có thể không có giá trị nó.

Điều đó phụ thuộc vào khả năng bạn sẽ tìm thấy lần truy cập. Tỷ lệ truy cập thấp sẽ mang lại kết quả tốt. Tỷ lệ truy cập cao sẽ hoạt động không tốt hơn nhiều so với phiên bản vòng lặp lồng nhau đơn giản. xem xét đảo ngược các vòng nếu một số kim tiêm trúng nhiều mục tiêu, và các hit khác không.

Đó là tất cả về việc hủy bỏ đường dẫn tìm kiếm càng sớm càng tốt.

Answer 7

Để bắt đầu, vì tình yêu của thần, hãy sử dụng một tập hợp (ví dụ: HashSet) chứ không phải là Danh sách. Làm một contains() trên một List là O (n), nhưng trên một tập hợp nó là O (1). Đó là một sửa chữa rất nhỏ một mình sẽ giúp bạn tiết kiệm rất nhiều thời gian.

Bây giờ, hãy chèn từng mục của bạn, bao gồm chia nhỏ từng từ. Ví dụ:

java.util.Set<String> set = new java.util.HashSet<String>(); 
set.add("ABCD"); 
set.add("IJ"); 
set.add("IJ KL"); 

nếu bạn muốn từ trận đấu một phần ở giữa của chuỗi (không chỉ bắt đầu với), thêm:

set.add("KL"); 

Check-out String.split() để nhanh chóng chia văn bản dựa trên không gian.

Bây giờ, khi bạn đang tìm kiếm, bạn có thể làm:

boolean isItThere = set.contains("IJ"); 

Tada! Rất đơn giản O (1) tìm kiếm. Điều này sẽ rất nhanh. Lưu ý: giả sử 10.000 mục nhập 10 ký tự, mỗi mục có trung bình 2 từ cho mỗi mục nhập, nghĩa là chúng tôi đang sử dụng < 200k bộ nhớ tại đây (10k * 10 * 2 = 200k). Nếu kích thước chuỗi của bạn tăng lên, hoặc số lượng từ của bạn phát triển, điều này có thể thoát ra khỏi một cách vội vàng. Sau đó, bạn nên nhìn vào một cái gì đó như Lucene.

Answer 8

Có, bạn có thể! Sắp xếp.

Điều bạn đang tìm kiếm, thường được gọi là fuzzy searching or approximate string matching và có một số giải pháp cho vấn đề này. Ví dụ:

Với ví dụ: FuzzyWuzzy lib, bạn có thể có tất cả các chuỗi được gán điểm dựa trên mức độ tương đồng của chúng với cụm từ tìm kiếm cụ thể. Các giá trị thực tế dường như là phần trăm số nguyên của số ký tự phù hợp với độ dài chuỗi tìm kiếm.

Sau khi gọi FuzzySearch.extractAll, bạn có thể quyết định điểm số tối thiểu nào cho chuỗi được coi là trùng khớp.

Ngoài ra còn có các thư viện tương tự khác đáng để khám phá, như google-diff-match-patch hoặc Apache Commons Text Similarity API, v.v.

Nếu bạn cần một cái gì đó thực sự hạng nặng, đặt cược tốt nhất của bạn có lẽ sẽ Lucene (cũng như được đề cập bởi Ryan Shillington)

Answer 9

Bạn có thể sử dụng IterableUtils từ Apache Commons Collections.

List<String> list = new ArrayList<String>(); 
list.add("ABCD"); 
list.add("EFGH"); 
list.add("IJ KL"); 
list.add("M NOP"); 
list.add("UVW X"); 

boolean hasString = IterableUtils.contains(list, "IJ", new Equator<String>() { 
    @Override 
    public boolean equate(String o1, String o2) { 
     return o2.contains(o1); 
    } 

    @Override 
    public int hash(String o) { 
     return o.hashCode(); 
    } 
}); 

System.out.println(hasString); // true