时间戳

首页 > 解决方案 > 在给定超字符串正则表达式的情况下查找字符串的值

regex - 在给定超字符串正则表达式的情况下查找字符串的值

问题描述

如何匹配作为给定输入字符串的子字符串的字符串，最好使用正则表达式？

给定一个值: A789Lfu891MatchMe2ENOTSTH，构造一个匹配字符串的正则表达式，其中字符串是给定值的子字符串。

预期匹配：

预期不匹配

对我来说，做相反的事情似乎更容易：/\w*MatchMe\w*/，但我无法解决这个问题。

类似于 SQL 的做法： SELECT * FROM my_table mt WHERE 'A789Lfu891MatchMe2ENOTSTH' LIKE '%' || mt.foo || '%';

标签： regex

解决方案

前缀后缀

您可以替换前缀后缀，例如将超字符串abcd转换为^(a|(a)?b|((a)?b)?c|(((a)?b)?c)?d)$. 对于您的示例，该模式有 1253 个字符（比 @tobias_k 少 2000 个字符）。

生成正则表达式的 Python 代码，然后可以使用 tobias_k 的代码进行测试（在线尝试）：

from itertools import accumulate

t = "A789Lfu891MatchMe2ENOTSTH"
p = '^(' + '|'.join(accumulate(t, '({})?{}'.format)) + ')$'

后缀前缀

后缀前缀看起来更好并且匹配更快：^(a(b(c(d)?)?)?|b(c(d)?)?|c(d)?|d)$. 可悲的是，生成代码不太优雅。

分而治之

对于较短的正则表达式，我们可以使用分而治之。例如对于 superstring abcdefg，每个子字符串都属于以下三种情况之一：

  • 包含中间字符 (the d)。模式：((a?b)?c)?d(e(fg?)?)?
  • 是那个中间字符的左边。所以递归地为超字符串构建一个正则表达式abc: a|a?bc?|c。
  • 是那个中间字符的权利。所以递归地为超字符串构建一个正则表达式efg: e|e?fg?|g。

然后对这三种情况进行交替：

a|a?bc?|c|((a?b)?c)?d(e(fg?)?)?|e|e?fg?|g

正则表达式长度将是 Θ(n log n) 而不是我们之前的 Θ(n 2 )。

25 个字符的超字符串示例的结果是这个 301 个字符的正则表达式：

^(A|A?78?|8|((A?7)?8)?9(Lf?)?|Lf?|f|(((((A?7)?8)?9)?L)?f)?u(8(9(1(Ma?)?)?)?)?|89?|9|(8?9)?1(Ma?)?|Ma?|a|(((((((((((A?7)?8)?9)?L)?f)?u)?8)?9)?1)?M)?a)?t(c(h(M(e(2(E(N(O(T(S(TH?)?)?)?)?)?)?)?)?)?)?)?|c|c?hM?|M|((c?h)?M)?e(2E?)?|2E?|E|(((((c?h)?M)?e)?2)?E)?N(O(T(S(TH?)?)?)?)?|OT?|T|(O?T)?S(TH?)?|TH?|H)$

基准

速度基准测试并没有那么大的意义，因为实际上我们只是做一个常规的子字符串检查（在 Python 中s in t），但无论如何让我们做一个。

在我的 PC 上使用 Python 3.9.6 匹配超字符串的所有子字符串的结果：

 1.09 ms  just_all_substrings
25.18 ms  prefix_suffixes
 3.47 ms  suffix_prefixes
 3.46 ms  divide_and_conquer

在 TIO 和他们的“Python 3.8 (pre-release)”上，结果完全不同：

 0.30 ms  just_all_substrings
46.90 ms  prefix_suffixes
 2.24 ms  suffix_prefixes
 2.95 ms  divide_and_conquer

正则表达式长度（也由以下基准代码打印）：

 3253 characters - just_all_substrings
 1253 characters - prefix_suffixes
 1253 characters - suffix_prefixes
  301 characters - divide_and_conquer

基准代码（在线试用！）：

from timeit import repeat
import re
from itertools import accumulate

def just_all_substrings(t):
    return "^(" + '|'.join(t[i:k] for i in range(0, len(t))
                                  for k in range(i+1, len(t)+1)) + ")$"

def prefix_suffixes(t):
    return '^(' + '|'.join(accumulate(t, '({})?{}'.format)) + ')$'

def suffix_prefixes(t):
    return '^(' + '|'.join(list(accumulate(t[::-1], '{1}({0})?'.format))[::-1]) + ')$'
    
def divide_and_conquer(t):

    def suffixes(t):
        # Example: abc => ((a?b)?c)?
        regex = f'{t[0]}?'
        for c in t[1:]:
            regex = f'({regex}{c})?'
        return regex

    def prefixes(t):
        # Example: efg => (e(fg?)?)?
        regex = f'{t[-1]}?'
        for c in t[-2::-1]:
            regex = f'({c}{regex})?'
        return regex

    def superegex(t):
        n = len(t)
        if n == 1:
            return t
        if n == 2:
            return f'{t}?|{t[1]}'
        mid = n // 2
        contain = suffixes(t[:mid]) + t[mid] + prefixes(t[mid+1:])
        left = superegex(t[:mid])
        right = superegex(t[mid+1:])
        return '|'.join([left, contain, right])

    return '^(' + superegex(t) + ')$'

creators = just_all_substrings, prefix_suffixes, suffix_prefixes, divide_and_conquer,


t = "A789Lfu891MatchMe2ENOTSTH"

substrings = [t[start:stop]
              for start in range(len(t))
              for stop in range(start+1, len(t)+1)]
def test(p):
    match = re.compile(p).match
    return all(map(re.compile(p).match, substrings))

for creator in creators:
    print(test(creator(t)), creator.__name__)
print()

print('Regex lengths:')
for creator in creators:
    print('%5d characters -' % len(creator(t)), creator.__name__)
print()

for _ in range(3):
    for creator in creators:
        p = creator(t)
        number = 10
        time = min(repeat(lambda: test(p), number=number)) / number
        print('%5.2f ms ' % (time * 1e3), creator.__name__)
    print()

推荐阅读