30

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

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

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

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

有明显的蛮力方法可以实现这一点，我想知道是否有任何优雅的 Python/regex 解决方案。

4

6 回答 6

36

我会假设正则表达式比单独检查每个子字符串更好，因为从概念上讲，正则表达式被建模为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)

更新：应该注意的是，正则表达式中事物的顺序 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 的应用程序意味着什么，但至少行为是已知的。

更新：我发布了这个关于在 Python中实现正则表达式的问题，希望能让我们深入了解这个问题中发现的问题。

于 2009-05-09T07:34:52.783 回答
4 
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)
于 2009-05-09T07:24:07.800 回答
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

为了可读性和速度，我会选择汤姆的答案。

于 2009-05-09T21:54:58.720 回答
2

这是一个模糊的理论答案，没有提供代码，但我希望它可以为您指明正确的方向。

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

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

节点应该很容易制作。

class Node(object):
    children = []

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

字符在哪里name。

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

澄清编辑：DFA 应该比这种方法快得多，所以我应该赞同汤姆的回答。我只保留这个答案以防您的子字符串列表经常更改，在这种情况下使用树可能会更快。

于 2009-05-09T07:40:42.643 回答
0

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

于 2009-05-09T08:02:09.503 回答
0

这个怎么样。

>>> 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')

显然，您可以返回元组以外的其他内容。

这通过以下方式起作用：

  • 将子字符串列表过滤到字符串中的那些
  • 构建包含子字符串索引的元组列表，以及子字符串
  • 如果找到子字符串，则根据索引找到最小值
于 2009-05-09T08:31:56.763 回答