如何提高大文本数据集的模式匹配效率

Question

我现在正在做一个项目，涉及处理大量的文本数据，用于自然语言处理的任务。其中一个关键环节是字符串匹配，我需要高效地在句子中找到与预定义模式相匹配的子字符串。

这里有一个模拟的例子来说明这个问题，以下是一些句子：

sentences = [
    "the quick brown fox jumps over the lazy dog",
    "a watched pot never boils",
    "actions speak louder than words"
]

我还有一组模式：

patterns = [
    "quick brown fox",
    "pot never boils",
    "actions speak"
]

我的目标是高效地找出包含这些模式的句子。此外，我还需要对每个句子进行分词，并对匹配到的子字符串进行进一步分析。

目前，我使用的是一种暴力的方法，采用嵌套循环，但对于大数据集来说，这种方法不够灵活。我希望能找到更高级的技术或算法来优化这个过程。

在这种情况下，我该如何实现字符串匹配，同时考虑到可扩展性和性能呢？任何建议都非常感谢！

Answer 1

为了避免对每个句子和每个模式进行暴力搜索，我们可以创建一种索引。通过这个索引，你可以缩小搜索范围，更快找到正确的句子：

举个例子：

sentences = [
    "the quick brown fox jumps over the lazy dog",
    "a watched pot never boils",
    "actions speak louder than words",
]

patterns = ["quick brown fox", "pot never boils", "actions speak"]


def build_index(sentences):
    out = {}

    for s in sentences:
        for word in set(s.split()):
            out.setdefault(word, []).append(s)

    return out


def find_patterns(index, patterns):
    out = {}

    for p in patterns:
        word, *_ = p.split(maxsplit=1)
        out[p] = []
        for s in index.get(word, []):
            if p in s:
                out[p].append(s)

    return out


index = build_index(sentences)
print(find_patterns(index, patterns))

这段代码会输出：

{
    "quick brown fox": ["the quick brown fox jumps over the lazy dog"],
    "pot never boils": ["a watched pot never boils"],
    "actions speak": ["actions speak louder than words"],
}

---

更强大的一种方法是使用更高级的工具，比如在SQLite中进行全文搜索（SQLite是Python自带的，比如：使用真正的“全文搜索”和拼写错误的SQLite（FTS+spellfix结合）等）。