在大型数据集中查找匹配项的方法

Question

我有一个项目，给定一个包含约 10,000 个唯一字符串的列表，我想找到这些字符串在具有 10,000,000 多个字符串条目的文件中出现的位置。如果可能的话，我还想包括部分匹配项。我的约 10,000 个字符串列表是动态数据，每 30 分钟更新一次，目前我无法处理所有搜索以跟上更新的数据。我现在的搜索大约需要 3 个小时（相比之下我必须在 30 分钟内完成搜索），所以我觉得我解决这个问题的方法不太正确。

我目前的方法是首先从 10,000,000 多个字符串条目中创建一个列表。然后使用 in-search 在更大的列表中搜索动态列表中的每个项目。

results_boolean = [keyword in n for n in string_data]

有没有一种方法可以通过更合适的方法大大加快速度？

Answer 1

使用带有集合的生成器可能是你最好的选择......我认为这个解决方案会工作并且可能更快

def find_matches(target_words,filename_to_search):
    targets = set(target_words)
    with open("search_me.txt") as f:
        for line_no,line in enumerate(f):
            matching_intersection = targets.intersection(line.split())
            if matching_intersection:
                yield (line_no,line,matching_intersection) # there was a match
    
for match in find_matches(["unique","list","of","strings"],"search_me.txt"):
    print("Match: %s"%(match,))
    input("Hit Enter For next match:") #py3 ... just to see your matches

当然，如果您的匹配不是单个单词，就会变得更难，尤其是在没有可靠的分组定界符的情况下

Answer 2

一般来说，您可能希望对大量不变的数据进行预处理以加快重复搜索的速度。但你说的太少，无法提出一些明显实用的建议。比如：这些字符串有多长？什么是字母表（例如，7 位 ASCII 或完整的 Unicode？）？总共有多少字符？字母表中的字符是否同样有可能出现在每个字符串位置，或者分布是否高度倾斜？如果是这样，如何？等等。

这里是关于最简单的索引类型，构建一个条目数等于 string_data 中唯一字符数的字典。它将每个字符映射到包含该字符的字符串的 string_data 索引集。然后可以将对关键字的搜索限制为目前已知的唯一 string_data 个条目，其中包含关键字的第一个字符。

现在，根据您所说的无法猜测的细节，可能即使这种适度的索引也会消耗比您拥有的更多的 RAM - 或者它是可能它已经足以让你获得你似乎需要的 6 倍加速：

# Preprocessing - do this just once, when string_data changes.
def build_map(string_data):
    from collections import defaultdict
    ch2ixs = defaultdict(set)
    for i, s in enumerate(string_data):
        for ch in s:
            ch2ixs[ch].add(i)
    return ch2ixs

def find_partial_matches(keywords, string_data, ch2ixs):
    for keyword in keywords:
        ch = keyword[0]
        if ch in ch2ixs:
            result = []
            for i in ch2ixs[ch]:
                if keyword in string_data[i]:
                    result.append(i)
            if result:
                print(repr(keyword), "found in strings", result)

然后，例如，

string_data = ['banana', 'bandana', 'bandito']
ch2ixs = build_map(string_data)

find_partial_matches(['ban', 'i', 'dana', 'xyz', 'na'],
                     string_data,
                     ch2ixs)

显示：

'ban' found in strings [0, 1, 2]
'i' found in strings [2]
'dana' found in strings [1]
'na' found in strings [0, 1]

如果，例如，您仍然有足够的 RAM，但需要更快的速度，并且愿意放弃（可能愚蠢 - 但不能从这里猜测） 1 个字符的匹配项，您可以改为索引双字母组（相邻的字母对）。

在极限情况下，您可以从 string_data 构建一个 trie，这将需要大量 RAM，但可以将搜索嵌入关键字的时间减少到与搜索次数成正比的操作次数关键字中的字符，与 string_data.

中的字符串数量无关

请注意，您真的应该找到摆脱它的方法：

results_boolean = [keyword in n for n in string_data]

为每个关键字搜索构建一个包含超过 1000 万个条目的列表会使每次搜索都变得昂贵，无论您如何巧妙地为数据编制索引。

注意：可能对上述内容的实际改进是将搜索限制为包含所有关键字字符的字符串：

def find_partial_matches(keywords, string_data, ch2ixs):
    for keyword in keywords:
        keyset = set(keyword)
        if all(ch in ch2ixs for ch in keyset):
            ixs = set.intersection(*(ch2ixs[ch] for ch in keyset))
            result = []
            for i in ixs:
                if keyword in string_data[i]:
                    result.append(i)
            if result:
                print(repr(keyword), "found in strings", result)

在大型数据集中查找匹配项的方法

Approaches for finding matches in a large dataset

python

search

large-data