Python中查找多个子字符串的最有效方法是什么？

Question

我有一个可能子字符串的列表，例如['cat', 'fish', 'dog']。在实践中，此列表包含数百个条目。

我正在处理一个字符串，我要找到的是任何这些子字符串第一次出现的索引。

为了澄清，对于'012cat'，结果是3，对于'0123dog789cat'，结果是4。

我还需要知道找到了哪个子字符串（例如其在子字符串列表中的索引或文本本身），或者至少匹配的子字符串长度。

有明显的暴力方法来实现这一点，我想知道是否有任何优雅的Python /正则表达式解决方案。

- Roee Adler

---

子字符串列表是否是常量？我问这个问题是因为使用正则表达式类型的解决方案通常涉及到对正则表达式（或者在你的情况下，子字符串列表）进行一些预计算。那么这种预计算会在多次搜索中分摊吗？ - Accipitridae

Answer 1

我认为使用正则表达式比逐个检查子字符串更好，因为从概念上讲，正则表达式被建模为一个DFA，因此随着输入的消耗，所有匹配都在同时进行测试（导致对输入字符串的一次扫描）。

所以这里是一个例子：

import re

def work():
  to_find = re.compile("cat|fish|dog")
  search_str = "blah fish cat dog haha"
  match_obj = to_find.search(search_str)
  the_index = match_obj.start()  # produces 5, the index of fish
  which_word_matched = match_obj.group()  # "fish"
  # Note, if no match, match_obj is None

更新：在将单词组合成单个替代单词模式时，应该注意一些细节。以下代码构建了一个正则表达式，但是转义了任何正则表达式特殊字符并对单词进行排序，以便更长的单词在匹配任何相同单词的较短前缀之前有机会匹配：

def wordlist_to_regex(words):
    escaped = map(re.escape, words)
    combined = '|'.join(sorted(escaped, key=len, reverse=True))
    return re.compile(combined)

>>> r.search('smash atomic particles').span()
(6, 10)
>>> r.search('visit usenet:comp.lang.python today').span()
(13, 29)
>>> r.search('a north\south division').span()
(2, 13)
>>> r.search('012cat').span()
(3, 6)
>>> r.search('0123dog789cat').span()
(4, 7)

更新结束

需要注意的是，您应该尽可能少地形成正则表达式（即 - 调用re.compile()）。最好的情况是您提前知道您的搜索内容是什么（或者您计算它们一次/不经常），然后将re.compile()的结果保存在某个地方。我的示例只是一个简单的无意义函数，以便您可以看到正则表达式的用法。这里有更多的正则表达式文档：

http://docs.python.org/library/re.html

希望这能帮到你。

更新: 我不确定 Python 如何实现正则表达式，但是为了回答 Rax 的问题，即 re.compile() 是否有限制（例如，一次尝试匹配多少个单词），以及编译需要的时间：这两者似乎都不是问题。我尝试了这段代码，它已经足够让我相信。（我可以通过添加计时和报告结果，以及将单词列表放入集合中以确保没有重复项来改进它...但这两个改进似乎过度设计了）。这段代码运行非常快，让我相信我能够搜索 2000 个大小为 10 的单词，并且它们都会被适当地匹配。以下是代码：

import random
import re
import string
import sys

def main(args):
    words = []
    letters_and_digits = "%s%s" % (string.letters, string.digits)
    for i in range(2000):
        chars = []
        for j in range(10):
            chars.append(random.choice(letters_and_digits))
        words.append(("%s"*10) % tuple(chars))
    search_for = re.compile("|".join(words))
    first, middle, last = words[0], words[len(words) / 2], words[-1]
    search_string = "%s, %s, %s" % (last, middle, first)
    match_obj = search_for.search(search_string)
    if match_obj is None:
        print "Ahhhg"
        return
    index = match_obj.start()
    which = match_obj.group()
    if index != 0:
        print "ahhhg"
        return
    if words[-1] != which:
        print "ahhg"
        return

    print "success!!! Generated 2000 random words, compiled re, and was able to perform matches."

if __name__ == "__main__":
    main(sys.argv)

更新： 需要注意的是正则表达式中OR操作符连接的顺序很重要。看看以下测试，它受到了TZOTZIOY的启发：

>>> search_str = "01catdog"
>>> test1 = re.compile("cat|catdog")
>>> match1 = test1.search(search_str)
>>> match1.group()
'cat'
>>> match1.start()
2
>>> test2 = re.compile("catdog|cat")  # reverse order
>>> match2 = test2.search(search_str)
>>> match2.group()
'catdog'
>>> match2.start()
2

这表明顺序很重要 :-/。我不确定这对Rax的应用有什么影响，但至少已知道其行为。

更新：我发布了有关Python中正则表达式实现的问题此问题，希望能为我们解决这个问题提供一些见解。

- Tom

---

@ rax，你看到我的新解决方案了吗？我基本上修复了它的所有问题，并在这个提交后的 20 秒内提交了它。 - Unknown

许多所谓的正则表达式语法实际上并不是“正则”的。也就是说，它们比真正的正则表达式更强大，因此不能表示为DFA。在Python、Perl甚至grep中出现的一个例子是反向引用。以Python正则表达式r“(a+)b\1”为例。这匹配一些a，一个b，然后与之前相同数量的a。这是非正则的。支持反向引用的RE引擎实际上使用NFA。一些RE引擎足够聪明，可以在实际上是正则的正则表达式上切换到使用DFA，但我认为Python没有这样做。 - Laurence Gonsalves

@Laurence：很有见地。我很想在某个地方发帖关于Python中REs的实现。我不明白为什么要使用NFA。NFA和DFA是等价的。你可以使用Thompson的子集构造将NFA转换为DFA。你是指需要使用PDA以便堆栈可以跟踪您已经看到了多少个a吗？我甚至不确定这一点，因为我对语法不完全确定...但我确定NFA和DFA是等价的。 - Tom

@Unknown：请查看我在您的帖子上的评论。 - Tom

@TZOTZIOY：我打算添加一个更新，提到我尝试过的一些东西...如果你同意，请告诉我。 - Tom

Answer 2

subs = ['cat', 'fish', 'dog']
sentences = ['0123dog789cat']

import re

subs = re.compile("|".join(subs))
def search():
    for sentence in sentences:
        result = subs.search(sentence)
        if result != None:
            return (result.group(), result.span()[0])

# ('dog', 4)

- Unknown

---

我认为他只有一个“句子”。 - Paolo Bergantino

谢谢，但这不是我要找的。首先，它没有找到第一次出现（在第二个句子中，它将返回“cat”的出现，即10，而不是“dog”的出现，即4）。有明显的解决方案，但它非常暴力（迭代直到最后一个子字符串并不断维护第一次出现）。我认为Python必须有一些库函数可以做到这一点... - Roee Adler

@Tom，“我不喜欢“return”语句，因为如果你有更多的句子，它会过早地退出。”但是我认为Rax想要找到第一个匹配项？ - Unknown

@Unknown：我发表评论的原因是，如果您要将更多的句子添加到句子列表中，您的代码会短路，因为它只会检查第一个句子。也就是说，如果您不打算编写适用于更大列表的代码，那么您不应该使用subs和sentences列表。 - Tom

抱歉，不只是检查第一句话，而是只检查直到第一个匹配的句子（在这种情况下，第一句话）。 - Tom

Answer 3

我想指出DisplacedAussie和Tom回答之间的时间差异。两个回答都很快，使用一次不应该有明显等待时间，但当你计时它们：

import random
import re
import string

words = []
letters_and_digits = "%s%s" % (string.letters, string.digits)
for i in range(2000):
    chars = []
    for j in range(10):
        chars.append(random.choice(letters_and_digits))
    words.append(("%s"*10) % tuple(chars))
search_for = re.compile("|".join(words))
first, middle, last = words[0], words[len(words) / 2], words[-1]
search_string = "%s, %s, %s" % (last, middle, first)

def _search():
    match_obj = search_for.search(search_string)
    # Note, if no match, match_obj is None
    if match_obj is not None:
         return (match_obj.start(), match_obj.group())

def _map():
    search_for = search_for.pattern.split("|")
    found = map(lambda x: (search_string.index(x), x), filter(lambda x: x in search_string, search_for))
    if found:
        return min(found, key=lambda x: x[0])


if __name__ == '__main__':
    from timeit import Timer


    t = Timer("_search(search_for, search_string)", "from __main__ import _search, search_for, search_string")
    print _search(search_for, search_string)
    print t.timeit()

    t = Timer("_map(search_for, search_string)", "from __main__ import _map, search_for, search_string")
    print _map(search_for, search_string)
    print t.timeit()

输出：

(0, '841EzpjttV')
14.3660159111
(0, '841EzpjttV')
# I couldn't wait this long

我会选择Tom的答案，因为它更易读且速度更快。

- Nick Presta

---

谢谢Nick！为了公平起见，你可以帮助DisplacedAussie（稍微）通过删除对split("|")的调用并只给他一个列表来开始。为了更全面，你应该添加暴力方法。for word in search_for:, index = search_string.index(word), if index < smallest_index:, # 记录新的最小idx和匹配的单词。（抱歉不能在评论中编写代码）。然后等待并发布所有时间。考虑到这一点是一件好事，我希望能有一个特殊的元帖来处理这样的事情，因为评论和答案帖子都不是好地方。 - Tom

在有关效率的问题中进行基准测试，真是太棒了！ - dbr

Answer 4

这是一个没有提供代码的模糊而理论性的答案，但我希望它能指引你走向正确的方向。

首先，你需要更高效的查找子字符串列表。我建议使用某种树形结构。从根开始，如果任何子字符串以 'a' 开头，则添加一个 'a' 节点，如果任何子字符串以 'b' 开头，则添加一个 'b' 节点，依此类推。对于这些节点中的每一个，都要继续添加子节点。

例如，如果你有一个包含单词 "ant" 的子字符串，那么你应该有一个根节点、一个子节点 'a'、一个孙子节点 'n' 和一个曾孙节点 't'。

节点应该很容易制作。

class Node(object):
    children = []

    def __init__(self, name):
        self.name = name

其中name是一个字符。

逐个遍历您的字符串中的每个字母，并跟踪您所处的字母。在每个字母处，尝试使用接下来的几个字母来遍历树。如果成功，您的字母编号将是子字符串的位置，您的遍历顺序将指示找到的子字符串。

澄清编辑：DFA应该比这种方法快得多，因此我应该支持Tom的答案。 我只保留此答案，以防您的子字符串列表经常更改，在这种情况下，使用树可能更快。

- Wesley

---

谢谢，我完全理解字符串索引和搜索的理论和实践，并且可以自己实现，但是我希望Python有一个专门用于这个目的的工具。我理解目前没有这样的工具？ - Roee Adler

我不知道Python内置了这样的功能，因此我无法确定它是否存在。因此，恐怕我的回答对您没有任何帮助。我在这里看到的最接近的答案是Tom的。 - Wesley

Answer 5

这个怎么样？

>>> substrings = ['cat', 'fish', 'dog']
>>> _string = '0123dog789cat'
>>> found = map(lambda x: (_string.index(x), x), filter(lambda x: x in _string, substrings))
[(10, 'cat'), (4, 'dog')]
>>> if found:
>>>     min(found, key=lambda x: x[0])
(4, 'dog')

显然，你可以返回除元组以外的其他东西。

这个方法的实现方式是：

• 将子字符串列表过滤为那些在字符串中的
• 构建一个包含子字符串索引和子字符串本身的元组列表
• 如果找到了子字符串，则基于索引找到最小值

- DisplacedAussie

---

这似乎是一个非常低效的答案。它肯定会多次扫描字符串。即使是一种蛮力方法，你手动使用每个要搜索的字符串的字符串index()方法（实时跟踪最小值）也比这个好。map()可以是一个强大的函数，但这不是这种情况的例子。 - Tom

Answer 6

首先，我建议您按升序对初始列表进行排序。因为扫描较短的子字符串比扫描较长的子字符串更快。

- Anonymous

---

你确定这会有所不同吗？如果我自己实现正则表达式（作为DFA），长度就不重要了。每个子字符串将同时被搜索。我现在很好奇Python如何实现正则表达式... - Tom