Python - 查找字符串中一组字符串的出现次数

Question

Python - 查找字符串中一组字符串的出现次数

3

我有一个大字符串和一个搜索字符串列表，想要构建一个布尔列表，指示每个搜索字符串是否存在于大字符串中。在Python中，最快的方法是什么？

以下是使用单纯方法的玩具示例，但我认为可能有更有效的方法。

例如，下面的示例应返回[1, 1, 0]，因为"hello"和"world"都存在于测试字符串中。

def check_strings(search_list, input):
output = []
for s in search_list:
    if input.find(s) > -1:
        output.append(1)
    else:
        output.append(0)
return output

search_strings = ["hello", "world", "goodbye"] test_string = "hello world" print(check_strings(search_strings, test_string))

这段代码的作用是检查字符串列表中是否有一个或多个元素可以在测试字符串中找到。如果能找到，它将返回True，否则返回False。

- Danny Friar

1

正确的解决方案应该是一次性实现多个密钥的 Rabin Karp 算法。 - enedil

回复 @enedil 的评论：https://dev59.com/zn3aa4cB1Zd3GeqPa0fV - Robᵩ

1

在研究Rabin Karp时，发现了一个Python实现的Aho Corasick，它似乎可以通过对测试字符串的单次遍历来解决它：https://pypi.python.org/pypi/pyahocorasick/ - Danny Friar

4个回答

4

使用Aho Corasick算法实现（https://pypi.python.org/pypi/pyahocorasick/），该算法只需对字符串进行一次遍历。

import ahocorasick
import numpy as np

def check_strings(search_list, input):
    A = ahocorasick.Automaton()
    for idx, s in enumerate(search_list):
        A.add_word(s, (idx, s))
    A.make_automaton()

    index_list = []
    for item in A.iter(input):
        index_list.append(item[1][0])

    output_list = np.array([0] * len(search_list))
    output_list[index_list] = 1
    return output_list.tolist()

search_strings = ["hello", "world", "goodbye"]
test_string = "hello world"
print(check_strings(search_strings, test_string))

- Danny Friar

如果不麻烦的话，您能否发布所有讨论实现的timeit结果，以便针对您的“真实数据”进行测试？ - Błotosmętek

2

我只是为了比较而发布它。我的比较代码：

#!/usr/bin/env python3
def gettext():
    from os import scandir
    l = []
    for file in scandir('.'):
        if file.name.endswith('.txt'):
            l.append(open(file.name).read())
    return ' '.join(l)

def getsearchterms():
    return list(set(open('searchterms').read().split(';')))

def rob(search_string, input_string):
    import re
    return [any(l)
            for l in
            zip(*re.findall('|'.join('('+i+')' for i in search_string),
                            input_string))]

def blotosmetek(search_strings, input_string):
    import re
    regexp = re.compile('|'.join([re.escape(x) for x in search_strings]))
    found = set(regexp.findall(input_string))
    return [x in found for x in search_strings]

def ahocorasick(search_list, input):
    import ahocorasick
    import numpy as np
    A = ahocorasick.Automaton()
    for idx, s in enumerate(search_list):
        A.add_word(s, (idx, s))
    A.make_automaton()

    index_list = []
    for item in A.iter(input):
        index_list.append(item[1][0])

    output_list = np.array([0] * len(search_list))
    output_list[index_list] = 1
    return output_list.tolist()

def naive(search_list, text):
    return [s in text for s in search_list]

def test(fn, args):
    start = datetime.now()
    ret = fn(*args)
    end = datetime.now()
    return (end-start).total_seconds()

if __name__ == '__main__':
    from datetime import datetime
    text = gettext()
    print("Got text, total of", len(text), "characters")
    search_strings = getsearchterms()
    print("Got search terms, total of", len(search_strings), "words")

    fns = [ahocorasick, blotosmetek, naive, rob]
    for fn in fns:
        r = test(fn, [search_strings, text])
        print(fn.__name__, r*1000, "ms")

我使用了利维坦中出现的不同单词作为搜索项，并将{{link2：Project Gutenberg下载量最高的25本书}}连接成搜索字符串。结果如下：

Got text, total of 18252025 characters
Got search terms, total of 12824 words
ahocorasick 3824.111 milliseconds
Błotosmętek 360565.542 milliseconds
naive 73765.67 ms

罗布的版本已经运行了大约一个小时，仍然没有完成。也许它坏了，也许它只是非常慢。

- enedil

好的，所以ahocorasick比regexp快两个数量级，这是值得记住的事情。谢谢。 - Błotosmętek

@Błotosmętek 我打赌，数据越多，差异就越明显 - 如果提供足够的数据，则aho-corasick可能比regexp快10**10倍。请注意，naive方法仍然比regexp快。正如古话所说，使用regexp，你现在有两个问题。 - enedil

顺便说一句，我认为这是因为ahocorasick模块是用C编写的。如果算法是在纯Python中实现的，我不认为它会如此快速。 - Błotosmętek

这里有一个扩展程序，可以搜索多个字符串：https://stackoverflow.com/questions/44744895/fastest-way-to-build-string-feature-vectors-python - Danny Friar

1

我使用正则表达式的版本：

def check_strings(search_strings, input_string):
    regexp = re.compile('|'.join([re.escape(x) for x in search_strings]))
    found = set(regexp.findall(input_string))
    return [x in found for x in search_strings]

在原始帖子提供的测试数据上，它比Rob的优美解决方案慢一个数量级，但我将在更大的样本上进行一些基准测试。

- Błotosmętek

嗯，如果你尝试使用GNU grep呢？Python和Perl实现正则表达式的已知漏洞会使一些查询成为指数级。 - enedil

1

嘿，如果你感兴趣的话 - 看看我的答案。 - enedil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Robᵩ · Accepted Answer

我不能确定这是否是最快的方法（它仍然是O(n*m)），但这是我会做的方式：

def check_strings(search_list, input_string):
    return [s in input_string for s in search_list]

下面的程序也许会更快，也可能不会。它使用正则表达式在输入字符串中执行一次匹配。请注意，根据您的需求，您可能想在re.findall()表达式中使用re.escape(i)，也可能不用。

def check_strings_re(search_string, input_string):
    import re
    return [any(l)
            for l in
            zip(*re.findall('|'.join('('+i+')' for i in search_string),
                            input_string))]

这是一个完整的测试程序：

def check_strings(search_list, input_string):
    return [s in input_string for s in search_list]


def check_strings_re(search_string, input_string):
    import re
    return [any(l)
            for l in
            zip(*re.findall('|'.join('('+i+')' for i in search_string),
                            input_string))]


search_strings = ["hello", "world", "goodbye"]
test_string = "hello world"
assert check_strings(search_strings, test_string) == [True, True, False]
assert check_strings_re(search_strings, test_string) == [True, True, False]