Tìm nhiều chuỗi văn bản - Python

Question

Tôi đang tìm giải thuật tốt nhất để giải quyết vấn đề này: có danh sách (hoặc một dict, một tập hợp) các câu nhỏ, tìm tất cả các lần xuất hiện của câu này trong văn bản lớn hơn . Các câu trong danh sách (hoặc dict, hoặc bộ) là khoảng 600k nhưng hình thành, trung bình, bằng 3 từ. Văn bản trung bình là 25 từ. Tôi vừa định dạng văn bản (xóa dấu câu, tất cả chữ thường và tiếp tục như thế này).

Dưới đây là những gì tôi đã cố gắng ra (Python):

to_find_sentences = [ 
    'bla bla', 
    'have a tea', 
    'hy i m luca', 
    'i love android', 
    'i love ios', 
    ..... 
] 

text = 'i love android and i think i will have a tea with john' 

def find_sentence(to_find_sentences, text): 
    text = text.split() 
    res = [] 
    w = len(text) 
    for i in range(w): 
     for j in range(i+1,w+1): 
      tmp = ' '.join(descr[i:j]) 
      if tmp in to_find_sentences: 
       res.add(tmp) 
    return res 


print find_sentence(to_find_sentence, text) 

Out:

['i love android', 'have a tea'] 

Trong trường hợp của tôi, tôi đã sử dụng một thiết lập để tăng tốc độ hoạt động in

Answer 1

Một giải pháp nhanh sẽ là xây dựng một câu hỏi Trie trong số các câu của bạn và chuyển đổi trie này thành regex. Ví dụ của bạn, mô hình sẽ trông như thế này:

(?:bla\ bla|h(?:ave\ a\ tea|y\ i\ m\ luca)|i\ love\ (?:android|ios)) 

Dưới đây là một example on debuggex:

Nó có thể là một ý tưởng tốt để thêm '\b' như ranh giới từ, để tránh phù hợp với "have a team".

Bạn sẽ cần một số nhỏ Trie script. Nó không phải là một gói chính thức nào được nêu ra, nhưng bạn chỉ có thể tải về nó here như trie.py trong thư mục hiện tại của bạn.

Sau đó bạn có thể sử dụng đoạn mã này để tạo ra Trie/regex:

import re 
from trie import Trie 

to_find_sentences = [ 
    'bla bla', 
    'have a tea', 
    'hy i m luca', 
    'i love android', 
    'i love ios', 
] 

trie = Trie() 
for sentence in to_find_sentences: 
    trie.add(sentence) 

print(trie.pattern()) 
# (?:bla\ bla|h(?:ave\ a\ tea|y\ i\ m\ luca)|i\ love\ (?:android|ios)) 

pattern = re.compile(r"\b" + trie.pattern() + r"\b", re.IGNORECASE) 
text = 'i love android and i think i will have a tea with john' 

print(re.findall(pattern, text)) 
# ['i love android', 'have a tea'] 

Bạn đầu tư một chút thời gian để tạo ra các Trie và regex, nhưng việc xử lý nên cực kỳ nhanh chóng.

Dưới đây là related answer (Speed up millions of regex replacements in Python 3) nếu bạn muốn biết thêm thông tin.

Lưu ý rằng nó sẽ không tìm thấy câu chồng chéo:

to_find_sentences = [ 
    'i love android', 
    'android Marshmallow' 
] 
# ... 
print(re.findall(pattern, "I love android Marshmallow")) 
# ['I love android'] 

Bạn sẽ phải modifiy regex với lookaheads tích cực để tìm câu chồng chéo.