在一个较长的字符串中查找子字符串的位置

Question

我有一个大字符串和许多小的子字符串，我想检查每个子字符串是否存在于大字符串中，并获取每个子字符串的位置。

string="some large text here"
sub_strings=["some", "text"]

for each_sub_string in sub_strings:
    if each_sub_string in string:
        print each_sub_string, string.index(each_sub_string)

问题在于，由于我有大量的子字符串（约一百万个），处理时间需要大约一个小时。是否有任何方法可以缩短这个时间，例如使用正则表达式或其他方式？

- Amith

---

使用几个线程呢？ - Marged

你正在做很多额外的工作，因为在搜索一个子字符串时，你可能会潜在地找到另一个。 - xrisk

@Marged 实际上，我也有大量的字符串，并且我正在使用Python的多进程模块为每个字符串生成一个单独的进程。尽管如此，我没有考虑为子字符串运行多个线程。 - Amith

@RishavKundu 这是真的。这就是为什么我考虑使用正则表达式并将所有子字符串组合在一起的原因。有没有使用普通字符串处理将它们组合在一起进行搜索的方法？ - Amith

https://dev59.com/YXM_5IYBdhLWcg3wlEJH - xrisk

Answer 1

最好的解决方案是使用树实现。正如Rishav所提到的，你在这里重复了很多工作。理想情况下，应该将其实现为基于树的FSM。想象以下示例：

Large String: 'The cat sat on the mat, it was great'
Small Strings: ['cat', 'sat', 'ca']

假设有一棵树，每一层都是一个额外的字母。

small_lookup = {
    'c': 
        ['a', {
            'a': ['t']
        }], {
    's':
        ['at']
    }
}

抱歉，格式有点混乱，但我认为直接映射回Python数据结构是有帮助的。您可以构建一棵树，其中顶层条目是起始字母，并且它们映射到可能完成的最终子字符串列表。如果您遇到一个是列表元素并且没有更多嵌套内容的情况，那么您就已经到达了叶子节点，并且知道您已经遇到了该子字符串的第一个实例。

将该树保存在内存中有点沉重，但如果您只有一百万个字符串，则这应该是最有效的实现。您还应确保在找到单词的第一个实例时修剪树。

对于那些具有CS技能的人，或者如果您想了解更多关于此方法的信息，它是Aho-Corasick字符串匹配算法的简化版本。

如果您有兴趣了解更多关于这些方法的信息，实际上有三种主要算法：

• Aho-Corasick（fgrep的基础）[最坏情况：O(m+n)]
• Commentz-Walter（vanilla GNU grep的基础）[最坏情况：O(mn)]
• Rabin-Karp（用于检测抄袭）[最坏情况：O(mn)]

在某些领域，所有这些算法都将优于其他算法，但基于您要搜索的子字符串数量非常高，并且它们之间很可能存在大量重叠，我敢打赌Aho-Corasick将比其他两种方法提供更好的性能，因为它避免了O(mn)最坏情况。

还有一个很棒的Python库，实现了Aho-Corasick算法，可以在此处找到，这应该使您避免编写糟糕的实现细节。

- Slater Victoroff

---

谢谢。看起来实现起来有点棘手。但是似乎有一个库可以做到这一点。 - Amith

@Amith 我也是这个想法，末尾的库链接应该能够使实现过程变得非常简单。 - Slater Victoroff

Answer 2

根据您子字符串长度的分布情况，您可能可以通过预处理节省大量时间。

比如说，您的子字符串长度集合为{23，33，45}（这意味着您可能有数百万个子字符串，但每个子字符串都有这三种长度之一）。

然后，对于这些长度中的每一个，在您的大字符串上找到Rabin Window，并将结果放入该长度的字典中。也就是说，让我们以23为例。在大字符串上查找23位窗口哈希值。假设位置0的哈希值为13。因此，您将13映射到[0]，并将其插入到名为rabin23的字典中。然后您发现在位置1，哈希值也是13。然后在rabin23中更新13被映射到[0, 1]。接着在位置2，哈希值为4。所以在rabin23中，4被映射到[2]。

现在，给定一个子字符串，您可以计算它的 Rabin 哈希值，并立即检查相关的字典以获取其出现的索引（然后需要进行比较）。

---

顺便提一下，在许多情况下，你的子字符串长度会表现出帕累托行为，也就是说，90%的字符串在长度的10%内。如果是这样的话，你可以只针对这些长度进行操作。

- Ami Tavory

---

谢谢。听起来很有前途。幸运的是，我正在处理中文字符（人名），它们通常只有3或4个字符。我会进一步了解这个问题。 - Amith

Answer 3

这种方法与其他答案相比不够优化，但可能足够好，并且实现简单。思路是将算法反转，而不是逐个测试每个子字符串与较大的字符串匹配，而是迭代大字符串并在每个位置测试可能匹配的子字符串，使用字典来缩小需要测试的子字符串数量。

输出将与原始代码不同，按索引升序排序而不是按子字符串排序，但如果您想要按子字符串排序，则可以对输出进行后处理。

创建一个包含以每个可能的1-3个字符开头的子字符串列表的字典。然后迭代字符串，在每个字符处读取其后的1-3个字符，并检查该位置上是否存在与以这些1-3个字符开头的字典中的每个子字符串匹配的内容：

string="some large text here"
sub_strings=["some", "text"]

# add each of the substrings to a dictionary based the first 1-3 characters
dict = {}
for s in sub_strings:
    if s[0:3] in dict:
        dict[s[0:3]].append(s)
    else:
        dict[s[0:3]] = [s];

 # iterate over the chars in string, testing words that match on first 1-3 chars
for i in range(0, len(string)):
    for j in range(1,4):
        char = string[i:i+j]
        if char in dict:        
            for word in dict[char]:
                if string[i:i+len(word)] == word:
                    print word, i

如果您不需要匹配任何长度为1或2个字符的子字符串，则可以摆脱for j循环，并使用char = string[i:3]直接分配字符。

使用这种第二种方法，我通过读取托尔斯泰的《战争与和平》并将其拆分为唯一单词来计时算法，如下所示：

with open ("warandpeace.txt", "r") as textfile:
    string=textfile.read().replace('\n', '')    
sub_strings=list(set(string.split()))

对文本中的每个唯一单词进行完整搜索并输出每个实例共花费了124秒。

- samgak