टेक्स्ट में बहुत सारी स्ट्रिंग पाएं - पायथन

Question

मैं इस समस्या को हल करने के लिए सबसे अच्छा एल्गोरिदम खोज रहा हूं: छोटे वाक्यों की एक सूची (या एक निर्देश, एक सेट) रखने के बाद, इस वाक्य की सभी घटनाओं को एक बड़े पाठ में ढूंढें । सूची में वाक्य (या dict, या set) लगभग 600k हैं, लेकिन औसतन, 3 शब्दों द्वारा गठित किया गया है। टेक्स्ट औसतन 25 शब्द लंबा है। मैंने अभी टेक्स्ट को स्वरूपित किया है (विराम चिह्न को हटा रहा है, सभी लोअरकेस और इस तरह से आगे बढ़ें)।

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) 

आउट:

यहाँ (अजगर) क्या मैं बाहर की कोशिश की है है

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

मेरे मामले में मैं एक सेट का उपयोग किया है in आपरेशन तेजी लाने के लिए

Answer 1

एक तेज़ समाधान आपके वाक्यों में से Trie बनाने और इस trie को regex में परिवर्तित करना होगा। आपके उदाहरण के लिए, पैटर्न इस प्रकार दिखाई देगा:

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

यहाँ एक example on debuggex है:

यह शब्द सीमाओं के रूप में '\b' जोड़ने के लिए, "have a team" मिलान से बचने के लिए एक अच्छा विचार हो सकता है।

आपको एक छोटे से Trie script की आवश्यकता होगी। यह अभी तक एक आधिकारिक पैकेज नहीं है, लेकिन आप इसे अपनी वर्तमान निर्देशिका में heretrie.py के रूप में डाउनलोड कर सकते हैं।

फिर आप 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'] 

आप Trie और regex बनाने के लिए कुछ समय निवेश, लेकिन संसाधन बहुत तेज किया जाना चाहिए।

यदि आप अधिक जानकारी चाहते हैं तो यहां related answer (Speed up millions of regex replacements in Python 3) है।

ध्यान दें कि यह ओवरलैपिंग वाक्य नहीं मिल जाएगा:

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

आप सकारात्मक lookaheads साथ regex modifiy को ओवरलैपिंग वाक्य को खोजने के लिए होगा।