python - 在文本中查找大量字符串 - Python

Question

我正在寻找解决这个问题的最佳算法:有一个小句子列表(或字典，一组)，在更大的文本中找到这个句子的所有出现。列表(或字典或集合)中的句子大约有 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 操作

Answer 1

一个快速的解决方案是构建一个 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']

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