搜索元组列表以查找匹配子字符串的算法方法？

Question

我有一个由大约10万个元组组成的列表。每个元组包含一个id和一个字符串，我的目标是列出这些元组的id，这些字符串中包含给定子字符串列表中的任何一个子字符串。

我当前的解决方法是使用集合推导式，ids可能会重复。

tuples = [(id1, 'cheese trees'), (id2, 'freezy breeze'),...]
vals = ['cheese', 'flees']
ids = {i[0] for i in tuples if any(val in i[1] for val in vals)}

output: {id1}

是否有一种算法可以更快地实现这个目标？我对精确子字符串匹配和近似匹配都很感兴趣。这里最重要的是，我需要一种比纯理解更具速度优势的算法。

- Daniel Kislyuk

---

什么是“算法方式”？ - martineau

@martineau 嗯，一些搜索算法，适合这个任务）在稍微不同的情况下，我会使用Aho-Corasick来匹配子字符串，但我无法将其适应于此任务。因此，问题变成了什么是合适的匹配算法。 - Daniel Kislyuk

有一种叫做“模糊匹配”的技术可以进行近似字符串匹配。我知道 Python 中的一个实现是 FuzzyWuzzy。 - martineau

@martineau，虽然FuzzyWuzzy可以对单个字符串进行近似字符串匹配，但它并不能提高处理大量字符串的速度，这对我来说是主要问题。 - Daniel Kislyuk

两个小点：（1）您可以通过多进程加速此过程。（2）如果按ID分组，则只需处理一组，直到找到第一个匹配项为止（可能会节省一些时间）。 - Timus

Answer 1

免责声明 我是trrex的作者。

对于精确匹配的情况，一种解决方法是使用Trie，正如评论中所提到的那样。trrex是一个库，它可以生成一个Trie-Regex（以正则表达式格式表示的Trie），可以与Python的正则表达式引擎一起使用：

import random
import pandas as pd
import trrex as tx
import re

df = pd.read_csv('jeopardy-small.csv')
with open('words-sample') as infile:
    words = [line.strip() for line in infile]


tuples = [(random.randint(1, 250), sentence) for sentence in df['question']]


def fun_kislyuk(ws, ts):
    return {t[0] for t in ts if any(w in t[1] for w in ws)}


def fun_trrex(ws, ts):
    pattern = re.compile(tx.make(ws, left='', right=''))
    return {i for i, s in ts if pattern.search(s)}


if __name__ == "__main__":
    print(fun_trrex(words, tuples) == fun_kislyuk(words, tuples))

输出

True

以上功能的时间如下：

%timeit fun_trrex(words, tuples)
11.3 ms ± 34.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit fun_kislyuk(words, tuples)
67.5 ms ± 1.75 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

数据是Jeopardy游戏中约2K道问题和500个随机选择的单词列表。您可以在此处找到重现实验的资源。 更新 如果您使用评论中提到的分组策略，时间改进将增加，以下是该函数：

def fun_grouping_trrex(ws, ts):
    pattern = re.compile(tx.make(ws, left='', right=''))
    groups = defaultdict(list)
    for i, s in ts:
        groups[i].append(s)

    return {i for i, vs in groups.items() if any(pattern.search(v) for v in vs)}

和时间：

%timeit fun_trrex(words, tuples)
11.2 ms ± 61.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit fun_grouping_trrex(words, tuples)
4.96 ms ± 320 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit fun_kislyuk(words, tuples)
67.4 ms ± 1.47 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

使用“分组+trrex”方法，性能可以提高约10倍。但是要注意，最后的结果非常依赖于数据集。

- Dani Mesejo