logo标签列表

Python：数字范围转正则表达式匹配字符串

pythonregex
9
这可能是一个已经解决的问题，但我无法理解。我有两个较大的整数，称它们为start_number和end_number（它们代表连续的电话号码块）。其他数字（表示为字符串）将被输入到我的系统中，我需要使用正则表达式将其与“范围正则表达式”匹配，以查看该数字字符串是否在start_number和end_number之间或之上。

例如：

  • start_number = 99519000
  • end_number = 99519099
因此
  • expression = "^995190[0-9][0-9]$"
这样，我最终可以匹配以下示例号码（一次到达我的系统，并且可能随时到达）：

  • "99519000" <- MATCH
  • "99519055" <- MATCH
  • "99519099" <- MATCH
  • "99519100" <- NOT MATCH
  • "99512210" <- NOT MATCH
  • "41234123" <- NOT MATCH
如何使用Python为任何合理的start_number和end_number 创建正则表达式字符串模式“expression”？我必须为几个起始/结束数字块创建正则表达式模式，我只需要一种以编程方式生成这些模式的方法。

可以合理地假设：

  • Start_number始终小于end_number
  • 始终是正整数。
  • 在我的情况下，如果表示为字符串时具有相同数量的十进制“字符”，则start_number和end_number始终具有相同的“长度”，如果会使生活更轻松。
编辑：为清晰起见
1
@rnbcoder写道，你不能将字符串转换为整数并进行比较吗？int(start_number) <= test_number <= (end_number) - Srikar Appalaraju
1
有没有必要用正则表达式来做这件事呢？我会把数字转换为整数，并检查其是否在起始数字和结束数字之间。这可能会略微低效，但时间复杂度是一样的，因为检查正则表达式匹配是O(n)，而将字符串转换为整数是O(n)，然后两个整数比较是O(1)。 - Vyassa Baratham
很不幸，正则表达式是必需的：expression字符串被放入配置文件中，并由某些硬件/固件解析。我也希望有其他方法！:( - TC Fox
1
那么，每当您从流中接收到一个数字时，只需将其发送到一个函数，该函数将将其转换为整数，并检查它是否在范围内-无需使用正则表达式。您正在使用哪个流？我会开一个新问题，因为这是另一个XY问题的典型例子。 - Inbar Rose
1
很令人沮丧的是，这里的人告诉你使用不同的解决方案，只是因为他们无法回答问题。你所要求的是可能的，并且考虑到你所面临的限制，似乎是合理的。 - andrew cooke
显示剩余9条评论
2个回答
21

[假设你需要这个，因为这是某些奇怪的第三方系统需要正则表达式]

新方法

越来越多地考虑到Frederik的评论，我越来越同意。即使输入字符串很长，正则表达式引擎也应该能够将其编译成紧凑的DFA。对于许多情况，以下是一个明智的解决方案:

import re

def regexp(lo, hi):
    fmt = '%%0%dd' % len(str(hi))
    return re.compile('(%s)' % '|'.join(fmt % i for i in range(lo, hi+1)))

在下面的测试中，包括99519000 - 99519099在内的所有数字范围都可正常工作。一个草率的估算表明，1GB的内存大约是9位数的极限。如果只匹配少量这样大小的数字，则可以使用更大的数字。

旧方法

[再次更新以获得更短的结果-除了偶尔聚合\d\d之外，它与手动生成的一样好]

假设所有数字长度相同（即如有必要，在左侧进行零填充），则此方法有效：

import re

def alt(*args):
    '''format regexp alternatives'''
    if len(args) == 1: return args[0]
    else: return '(%s)' % '|'.join(args)

def replace(s, c): 
     '''replace all characters in a string with a different character'''
    return ''.join(map(lambda x: c, s))

def repeat(s, n):
    '''format a regexp repeat'''
    if n == 0: return ''
    elif n == 1: return s
    else: return '%s{%d}' % (s, n)

def digits(lo, hi): 
    '''format a regexp digit range'''
    if lo == 0 and hi == 9: return r'\d'
    elif lo == hi: return str(lo)
    else: return '[%d-%d]' % (lo, hi)

def trace(f):
    '''for debugging'''
    def wrapped(lo, hi):
        result = f(lo, hi)
        print(lo, hi, result)
        return result
    return wrapped

#@trace  # uncomment to get calls traced to stdout (explains recursion when bug hunting)
def regexp(lo, hi):
    '''generate a regexp that matches integers from lo to hi only.
       assumes that inputs are zero-padded to the length of hi (like phone numbers).
       you probably want to surround with ^ and $ before using.'''

    assert lo <= hi
    assert lo >= 0

    slo, shi = str(lo), str(hi)
    # zero-pad to same length
    while len(slo) < len(shi): slo = '0' + slo
    # first digits and length
    l, h, n = int(slo[0]), int(shi[0]), len(slo)

    if l == h:
        # extract common prefix
        common = ''
        while slo and slo[0] == shi[0]:
            common += slo[0]
            slo, shi = slo[1:], shi[1:]
        if slo: return common + regexp(int(slo), int(shi))
        else: return common

    else:
        # the core of the routine.
        # split into 'complete blocks' like 200-599 and 'edge cases' like 123-199
        # and handle each separately.

        # are these complete blocks?
        xlo = slo[1:] == replace(slo[1:], '0')
        xhi = shi[1:] == replace(shi[1:], '9')

        # edges of possible complete blocks
        mlo = int(slo[0] + replace(slo[1:], '9'))
        mhi = int(shi[0] + replace(shi[1:], '0'))

        if xlo:
            if xhi:
                # complete block on both sides
                # this is where single digits are finally handled, too.
                return digits(l, h) + repeat('\d', n-1)
            else:
                # complete block to mhi, plus extra on hi side
                prefix = '' if l or h-1 else '0'
                return alt(prefix + regexp(lo, mhi-1), regexp(mhi, hi))
        else:
            prefix = '' if l else '0'
            if xhi:
                # complete block on hi side plus extra on lo
                return alt(prefix + regexp(lo, mlo), regexp(mlo+1, hi))
            else:
                # neither side complete, so add extra on both sides
                # (and maybe a complete block in the middle, if room)
                if mlo + 1 == mhi:
                    return alt(prefix + regexp(lo, mlo), regexp(mhi, hi))
                else:
                    return alt(prefix + regexp(lo, mlo), regexp(mlo+1, mhi-1), regexp(mhi, hi))


# test a bunch of different ranges
for (lo, hi) in [(0, 0), (0, 1), (0, 2), (0, 9), (0, 10), (0, 11), (0, 101),
                 (1, 1), (1, 2), (1, 9), (1, 10), (1, 11), (1, 101),
                 (0, 123), (111, 123), (123, 222), (123, 333), (123, 444),
                 (0, 321), (111, 321), (222, 321), (321, 333), (321, 444),
                 (123, 321), (111, 121), (121, 222), (1234, 4321), (0, 999),
                 (99519000, 99519099)]:
    fmt = '%%0%dd' % len(str(hi))
    rx = regexp(lo, hi)
    print('%4s - %-4s  %s' % (fmt % lo, fmt % hi, rx))
    m = re.compile('^%s$' % rx)
    for i in range(0, 1+int(replace(str(hi), '9'))):
        if m.match(fmt % i):
            assert lo <= i <= hi, i
        else:
            assert i < lo or i > hi, i

regexp(lo, hi)函数生成一个匹配介于lo和hi(补零到最大长度)之间的值的正则表达式。在使用时，可能需要在正则表达式前面加上^，并在后面加上$，以强制匹配整个字符串（就像测试代码中一样）。

实际上，这个算法非常简单——它将事物递归地分成公共前缀和“完整块”。其中，一个完整块是类似于200-599的东西，并且可以可靠地匹配（在本例中使用[2-5]\d{2}）。因此，123-599被分成了123-199和200-599两个部分。后半部分是完整块，前半部分有1这个公共前缀以及23-99这个子区间，这些都会被递归地处理。其中23-29是公共前缀，30-99是完整块（最终我们会结束递归，因为每次调用的参数都比初始输入短）。

唯一棘手的细节在于prefix，它是必需的，因为调用regexp()函数生成正则表达式时所传入的参数是整数，因此当调用生成00-09的正则表达式时，它实际上会生成没有前导0的0-9的正则表达式。

输出是一些测试用例，显示了范围和正则表达式：

   0 - 0     0
   0 - 1     [0-1]
   0 - 2     [0-2]
   0 - 9     \d
  00 - 10    (0\d|10)
  00 - 11    (0\d|1[0-1])
 000 - 101   (0\d\d|10[0-1])
   1 - 1     1
   1 - 2     [1-2]
   1 - 9     [1-9]
  01 - 10    (0[1-9]|10)
  01 - 11    (0[1-9]|1[0-1])
 001 - 101   (0(0[1-9]|[1-9]\d)|10[0-1])
 000 - 123   (0\d\d|1([0-1]\d|2[0-3]))
 111 - 123   1(1[1-9]|2[0-3])
 123 - 222   (1(2[3-9]|[3-9]\d)|2([0-1]\d|2[0-2]))
 123 - 333   (1(2[3-9]|[3-9]\d)|2\d\d|3([0-2]\d|3[0-3]))
 123 - 444   (1(2[3-9]|[3-9]\d)|[2-3]\d{2}|4([0-3]\d|4[0-4]))
 000 - 321   ([0-2]\d{2}|3([0-1]\d|2[0-1]))
 111 - 321   (1(1[1-9]|[2-9]\d)|2\d\d|3([0-1]\d|2[0-1]))
 222 - 321   (2(2[2-9]|[3-9]\d)|3([0-1]\d|2[0-1]))
 321 - 333   3(2[1-9]|3[0-3])
 321 - 444   (3(2[1-9]|[3-9]\d)|4([0-3]\d|4[0-4]))
 123 - 321   (1(2[3-9]|[3-9]\d)|2\d\d|3([0-1]\d|2[0-1]))
 111 - 121   1(1[1-9]|2[0-1])
 121 - 222   (1(2[1-9]|[3-9]\d)|2([0-1]\d|2[0-2]))
1234 - 4321  (1(2(3[4-9]|[4-9]\d)|[3-9]\d{2})|[2-3]\d{3}|4([0-2]\d{2}|3([0-1]\d|2[0-1])))
 000 - 999   \d\d{2}
99519000 - 99519099  995190\d\d

最后一个测试循环遍历99999999个数字，因此运行需要一段时间。

表达式应该足够紧凑，以避免任何缓冲区限制（我猜最坏情况下的内存大小与最大数字位数的平方成正比）。

注：我使用的是Python 3，但我不认为这对结果有太大影响。

1
顺带一提，Python的正则表达式引擎会自动处理其中的一些问题，你可以尝试执行re.sre_parse.parse("|".join(str(i) for i in range(99519000,99519100)))，你会看到它是如何提取共同前缀的。但我认为编译器还不够聪明，无法将0-9映射成\d。 - Fredrik
1
祝你调试好运。 - mbatchkarov
你有什么不明白的吗？我已经在代码中添加了注释，但如果你有任何疑问，我很乐意进行更详细的解释（你不需要调试正则表达式 - 你需要关注的是代码）。 - andrew cooke
2
这是一个非常令人印象深刻的回复！真的很感激你所付出的努力，认真地！ - TC Fox
我运行了几个测试，从内存方面来看，“新方法”远不如“旧方法”高效。当范围差异很大时，这一点开始变得明显。虽然没有证据，但我怀疑“新方法”可能有一个O(N)的组件，其中N是范围差异。只需注意以下内容的大小：re.sre_parse.parse("|".join(str(i) for i in range(10000, 40000))) - speedplane
@andrewcooke 你介意我拿你的代码，做一些修改并放在Github上吗？ 如果你提供你的github帐号，我会给你署名，并且按照Apache许可或类似方式进行发布。 - speedplane
3

使用Python包regex_engine生成数字范围的正则表达式

您可以使用pip安装此包

pip install regex-engine

from regex_engine import generator

generate = generator()

regex = generate.numerical_range(99519000, 99519099)

print(regex)

^(995190[1-8][0-9]|9951900[0-9]|9951909[0-9])$

你还可以生成浮点数和负数范围的正则表达式。

from regex_engine import generator

generate = generator()

regex1 = generate.numerical_range(5,89)
regex2 = generate.numerical_range(81.78,250.23)
regex3 = generate.numerical_range(-65,12)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接