有效的方法来检查一个字符串是否以一组字符串中的任意一个字符串开始

Question

有效的方法来检查一个字符串是否以一组字符串中的任意一个字符串开始

7

我需要匹配一个字符串，以查看它是否以大约40个字符串中的一个开头，并且这种方法被频繁调用。

目前它执行以下操作：

for pref, newval in list_of_prefixes:
    if oldval.startswith(pref):
         return newval
return oldval

然而，由于它被大量调用，尽可能高效是有意义的。我可以确保list_of_prefixes已排序，然后在pref>oldval时立即退出循环，但这似乎并没有带来太大的收益。

当前，最大数量的输入值在两个前缀之间，因此我可以明确测试这一点，或者按相反的顺序进行搜索，但尽管这对现在的数据集有效，但数据集发生变化时可能不那么有效。

最初只有1个可能的前缀，因此性能可能不是问题。

我查看了string.startswith(tuple())，但那似乎只是使编写更容易，并且它不告诉我匹配哪个元组，因此在有匹配时，我必须检查两次。

- Tom Tanner

1

听起来像是正则表达式的一个案例，这次可以用上它了。 - tripleee

前缀长度是否可预测？您可以将前缀列表放入字典中，然后查找所有可能是前缀长度的 oldval[: x]。特别是随着前缀列表的增长，字典查找速度会更快。 - jgfооt

@jgfoot，你基本上是在重新发明正则表达式，只不过正则表达式中的状态机是一个网络，每个节点可以有多个出口路径与一组可接受字符相关联；这也消除了字符串长度固定的要求。 - tripleee

1个回答

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

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

- tripleee · Accepted Answer

使用编译的正则表达式，当匹配的字符串不止几个时，我预计编译正则表达式的开销将得到回报。基本上，编译后的正则表达式是一个自动机，如果前缀不被自动机识别，则可遍历路径会很快消耗完。特别是当所有匹配都锚定在字符串开头时，如果没有匹配，应该很快失败。

import re

prefixes = ['foo', 'bar', 'baz']
rx = re.compile(''.join(['^(?:', '|'.join(prefixes), ')']))
for line in input:
    match = rx.match(line)
    if match:
        matched = match.group(0)

如果您需要更复杂的正则表达式（例如，在右括号后面有尾随上下文的表达式），您需要使用正则表达式组合括号 ( 而不是非组合括号 (?:，并获取 group(1)。

以下是一个将前缀映射到替换内容的示例:

prefixes = {'foo': 'nu', 'bar': 'beer', 'baz': 'base'}
rx = re.compile(''.join(['^(?:', '|'.join(prefixes.keys()), ')']))
for line in input:
    match = rx.match(line)
    if match:
        newval = prefixes[match.group(0)]

实际上，正如评论中指出的那样，在使用re.match()函数时，^并不是必须的。