Tìm kiếm một danh sách các chuỗi đối với bất kỳ phụ chuỗi từ một danh sách khác

Question

Với những 3 danh sách các dữ liệu và một danh sách các từ khóa:

good_data1 = ['hello, world', 'hey, world'] 
good_data2 = ['hey, man', 'whats up'] 
bad_data = ['hi, earth', 'sup, planet'] 
keywords = ['world', 'he'] 

Tôi đang cố gắng để viết một hàm đơn giản để kiểm tra nếu một trong các từ khóa tồn tại dưới dạng chuỗi con của bất kỳ từ nào trong danh sách dữ liệu. Nó phải trả về True cho các danh sách good_data và False cho bad_data.

tôi biết làm thế nào để làm điều này trong những gì dường như là một cách hiệu quả:

def checkData(data): 
    for s in data: 
    for k in keywords: 
     if k in s: 
     return True 
    return False 

Answer 1

Trong ví dụ của bạn, với quá ít mục, nó không thực sự quan trọng. Nhưng nếu bạn có danh sách vài nghìn mục, điều này có thể hữu ích.

Vì bạn không quan tâm yếu tố nào trong danh sách chứa từ khóa, bạn có thể quét toàn bộ danh sách một lần (dưới dạng một chuỗi) thay vì một mục vào thời điểm đó. Đối với điều đó, bạn cần một ký tự kết nối mà bạn biết sẽ không xảy ra trong từ khóa, để tránh dương tính giả. Tôi sử dụng dòng mới trong ví dụ này.

def check_data(data): 
    s = "\n".join(data); 
    for k in keywords: 
     if k in s: 
      return True 

    return False 

Trong thử nghiệm hoàn toàn không khoa học, phiên bản của tôi đã kiểm tra danh sách 5000 mục 100000 lần trong khoảng 30 giây. Tôi đã dừng phiên bản của bạn sau 3 phút - mệt mỏi vì phải chờ =)

Answer 2

Bạn đang tìm kiếm

any(k in s for k in keywords) 

Đó là nhỏ gọn hơn, nhưng có thể ít hiệu quả.

Answer 3

Tôi nghĩ điều này khá hiệu quả và rõ ràng, mặc dù bạn có thể sử dụng map() để tránh nhiều tổ. Tôi đồng ý với ross về ý tưởng từ điển cho các danh sách lớn hơn.

Answer 4

Bạn có thể cải thiện vấn đề bằng cách tạo danh sách từ khóa của bạn dưới dạng cụm từ thông dụng.

Điều này có thể cho phép chúng được kiểm tra song song, nhưng sẽ phụ thuộc rất nhiều vào từ khóa (ví dụ: một số công việc có thể được sử dụng lại cho "hello" và "hell" thay vì tìm kiếm mọi cụm từ ngay từ đầu . cho mỗi từ

Bạn có thể làm điều này bằng cách thực hiện:

import re 
keyword_re = re.compile("|".join(map(re.escape, keywords))) 

Sau đó:

>>> bool(keyword_re.search('hello, world')) 
True 
>>> bool(keyword_re.search('hi, earth')) 
False 

(Nó sẽ thực sự trả về một đối tượng phù hợp trên được tìm thấy, và Không nếu không tìm thấy - điều này có thể hữu ích nếu bạn cần biết từ khóa nào phù hợp)

Tuy nhiên, số tiền (nếu có) lợi ích này bạn sẽ phụ thuộc vào từ khóa. Nếu bạn chỉ có một hoặc hai, hãy giữ cách tiếp cận hiện tại của bạn. Nếu bạn có một danh sách lớn, nó có thể đáng tring và profiling để xem cái nào hoạt động tốt hơn.

[Chỉnh sửa] Để tham khảo, dưới đây là cách các phương pháp làm ví dụ của bạn:

   good1 good2 good3 bad1 bad2 
original  : 0.206 0.233 0.229 0.390 63.879 
gnud (join) : 0.257 0.347 4.600 0.281 6.706 
regex  : 0.766 1.018 0.397 0.764 124.351 
regex (join) : 0.345 0.337 3.305 0.481 48.666 

Rõ ràng đối với trường hợp này, cách tiếp cận của bạn thực hiện tốt hơn nhiều so với cái regex. Cho dù điều này sẽ luôn luôn là trường hợp phụ thuộc rất nhiều vào số lượng và độ phức tạp của các từ khóa, và các dữ liệu đầu vào sẽ được kiểm tra. Đối với số lượng lớn từ khóa và danh sách dài hoặc cụm từ hiếm khi phù hợp, regex có thể hoạt động tốt hơn, nhưng làm nhận thông tin thời gian và có thể thử thậm chí tối ưu hóa đơn giản hơn (như chuyển các từ phổ biến nhất sang trước danh sách từ khóa của bạn). Đôi khi cách tiếp cận đơn giản nhất thực sự là tốt nhất.

[Edit2] Cập nhật bảng với gnud's solution và cách tiếp cận tương tự trước khi áp dụng các regex. Tôi cũng đã thêm 2 thử nghiệm mới:

good_data3 = good_data2 * 500 # 1000 items, the first of which matches. 
bad_data2 = bad_data * 500  # 1000 items, none of which matches. 

Hiển thị các điểm mạnh và điểm yếu khác nhau.Việc tham gia không tồi tệ hơn khi một kết quả phù hợp sẽ được tìm thấy ngay lập tức (vì có một chi phí trả trước luôn được trả trong danh sách - đây là trường hợp tốt nhất có thể cho phương pháp tìm kiếm tuyến tính), tuy nhiên đối với danh sách không khớp, nó sẽ thực hiện tốt hơn. Nhiều tốt hơn khi có một số lượng lớn các mục trong danh sách.case).

Answer 5

Nếu bạn có nhiều từ khóa, bạn có thể muốn thử cây hậu tố [1]. Chèn tất cả các từ trong ba danh sách dữ liệu, lưu trữ danh sách mà mỗi từ xuất phát từ đó là nút chấm dứt. Sau đó, bạn có thể thực hiện các truy vấn trên cây cho mỗi từ khóa thực sự, rất nhanh.

Cảnh báo: cây hậu tố rất phức tạp để triển khai!

[1] http://en.wikipedia.org/wiki/Suffix_tree