在Python中找到多个子串的最有效方法是什么？

Question

我有一个可能的子字符串列表，比如 ['cat', 'fish', 'dog']。实际上，这个列表里有好几百个条目。

我正在处理一个字符串，我想找到这些子字符串中第一个出现的地方的索引。

举个例子，对于 '012cat'，结果是3；而对于 '0123dog789cat'，结果是4。

我还需要知道找到的是哪个子字符串（比如它在子字符串列表中的索引，或者直接是这个子字符串的内容），或者至少知道匹配的子字符串的长度。

虽然有一些简单粗暴的方法可以做到这一点，但我想知道有没有更优雅的Python或正则表达式的解决方案。

Answer 1

我想说一下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的回答，因为它更容易理解，而且速度也更快。

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)

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 3

我认为用正则表达式比逐个检查每个子字符串要好，因为从概念上讲，正则表达式是以一种叫做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)

更新：需要注意的是，正则表达式中用“或”连接的内容的顺序是重要的。看看下面这个受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中正则表达式实现的问题，希望能给我们一些关于这个问题的见解。