从大型列表中的子字符串中高效查找匹配字符串

Question

我有两个列表，每个列表包含大约 500 万个项目。

List_1

是一个元组列表，每个元组有两个字符串。

List_2

，是一长串字符串。

我正在尝试在

List_2

中找到由这些元组组成的复合字符串。

因此，如果

List_1

中的元组是

("foo", "bar")

，并且

List_2

包含

["flub", "blub", "barstool", "foo & bar: misadventures in python"]

，我会尝试从

List_2

获取“foo & bar：python 中的不幸事件”。

我目前的做法是迭代

List_1

，并通过理解扫描

List_2

。虽然对

List_2

的搜索速度很快，执行大约需要一秒钟，但它需要遍历所有

List_1

，因此需要过多的时间（大约 1000 小时）才能完成，这使得我想知道是否有更快、更有效的方法来做同样的事情。

代码示例：

list_1 = [] #Insert List
list_2 = [] #Insert List

for search_term in list_1:
    compound_string = "{search_first} & {search_second}".format(search_first=search_term[0], search_second=search_term[1])
    result = next((s for s in list_2 if compound_string in s), None) #Short-circuit, so we don't need to search through the whole list
    if result:
        #do exciting things

我研究过使用集合和交集来执行比较，但是，使用集合交集来进行比较仅适用于整个字符串。由于我事先不知道整个字符串，因此如果不使用 for 循环和列表，使用该方法似乎不可行，这会遇到同样的问题。

Answer 1

这个问题似乎有些不明确，但也有些过度明确。例如，元组到底有什么关系？

我会假设像这样重新构建它：你有一个字符串列表，

needles

，和另一个字符串列表，

haystacks

。您想要找到所有包含（至少一根）针的干草堆。

首先想到的是对针进行预处理，构建一个特里结构，以便更有效地搜索其中的任何一个。然后一次一个地跨过干草堆，使用该结构来测试它们。

这是我脑海中浮现出来的简单代码。听起来 RAM 对你来说不会是一个问题，但如果是的话，有更奇特的方法来构建“压缩”尝试。顺便说一句，如果你的all针包含3个字符的子字符串

" & "

，那么最好的猜测是大多数干草堆不会，所以在大多数情况下你可以通过先检查这么多来获得便宜的结果。

from collections import defaultdict

class Node:
    __slots__ = 'final', 'ch2node'

    def __init__(self):
        self.final = False
        self.ch2node = defaultdict(Node)

def add(trie, s):
    for ch in s:
        trie = trie.ch2node[ch]
    trie.final = True

# Does s[i:] start with a string in the trie?
def find(trie, s, i):
    for i in range(i, len(s)):
        if trie.final:
            return True
        ch = s[i]
        if ch in trie.ch2node:
            trie = trie.ch2node[ch]
        else:
            return False
    return trie.final

def search(trie, s):
    return any(find(trie, s, i) for i in range(len(s)))

needles = ["a & b", "kik", "c & as"]
haystacks = ["sldjkfa & b", "c&as", "akiko", "xc & asx", "kkc & a"]

root = Node()
for n in needles:
    add(root, n)
print(list(h for h in haystacks if search(root, h)))

哪个打印

['sldjkfa & b', 'akiko', 'xc & asx']