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

Question

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

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

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

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

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

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

更新:将单词组合成一个替代单词的单一模式时应注意一些。以下代码构建了一个正则表达式，但 escapes any regex special characters并对单词进行排序，以便较长的单词有机会在同一单词的任何较短的前缀之前匹配:

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)

更新: 应该注意的是，在正则表达式中，事物的顺序 ORed 在一起很重要。看看以下受 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 的应用程序意味着什么，但至少行为是已知的。

更新: 我发布了 this questions about the implementation of regular expressions in Python这有望让我们对这个问题发现的问题有所了解。