python - 在文本中查找很多字符串-Python

我正在寻找解决此问题的最佳算法:拥有一个包含小句子的列表(或字典，一组字典)，在较大的文本中查找所有出现的句子。列表(或字典或集合)中的句子大约为600k，但平均由3个单词组成。该文本平均长度为25个字。我刚刚格式化了文本(删除标点符号，全部小写，然后继续这样)。

这是我尝试过的内容(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)

出去:

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

就我而言，我使用了一个集合来加快in操作

最佳答案

一种快速的解决方案是从句子中构建 Trie 并将此trie转换为正则表达式。对于您的示例，模式如下所示:

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

这是一个example on debuggex:



最好添加'\b'作为单词边界，以避免匹配"have a team"。

您将需要一个小的Trie script。它不是官方软件包，但是您可以在当前目录中简单地将here作为trie.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和正则表达式，但是处理过程应该非常快。

如果您需要更多信息，这是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']

您必须使用正向先行修饰正则表达式才能找到重叠的句子。

关于python - 在文本中查找很多字符串-Python，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43628742/