如何创建 HH:MM 优化正则表达式？

Question

以

HH:MM

的形式给出两次，我想过滤包含给定时间之间所有时间的日志。

例如，给定 09:30 和 15:30，一个简单的正则表达式

T(09:[345]|1[01234]|15:[123])

就足够了。假设输入格式正确。

创建像

T(09:30|09:31|09:32|.....|15:30)

这样的正则表达式是一个微不足道的简单循环，但我想知道我可以做哪些转换来优化这样的正则表达式，以及这样的转换是否值得。

我正在用 python 编写，这是我当前的代码。如果它能简化，我愿意接受任何 Unix 工具。

from dataclasses import dataclass
import datetime
import re

@dataclass
class TimeFilter:
   start: datetime.time
   stop: datetime.time

   def timergx(self):
     i = self.start.hour * 60 + self.start.minute
     stop = self.stop.hour * 60 + self.stop.minute
     return "T(" + "|".join(f"{x // 60:02d}:{x % 60:02d}" for x in range(i, stop)) + ")"

def HHMM2time(txt: str):
    return datetime.time(*[int(x) for x in txt.split(":")])

tf = TimeFilter(HHMM2time("9:30"), HHMM2time("15:30"))
assert re.match(rf.timergx(), "T10:30")

如何“生成”正则表达式以使其“更快”？或者，

T(09:30|09:31|09:32|.....|15:30)

形式的正则表达式实际上比任何优化形式的处理“更快”吗？如果相关，GO 正则表达式引擎将使用正则表达式。

Answer 1

这是一个动态构建类似正则表达式的函数：

import re

def single_digit(start, end):
    if start == end:
        return str(start)
    if int(start) == int(end) - 1:
        return f"[{start}{end}]"
    return f"[{start}-{end}]"


def make_regex_rec(start, end, max="23:59", need_brackets=False):
    if "00:00".endswith(start) and max.endswith(end):
        return ""
    left = start[0]
    start = start[1:]
    right = end[0]
    end = end[1:]
    n = len(start)
    if not n:
        return single_digit(left, right)
    max = ("3:59" if left == "2" and n == 4 else "9:59")[-n:]
    if left == right:
        return left + make_regex_rec(start, end, max, True)
    rest_left = make_regex_rec(start, max, max, True)
    max = ("3:59" if right == "2" and n == 4 else "9:59")[-n:]
    rest_right = make_regex_rec("00:00"[-n:], end, max, True)
    left = int(left)
    right = int(right)
    if rest_left:
        rest_left = f"{left}{rest_left}"
        left += 1
    if rest_right:
        rest_right = f"{right}{rest_right}"
        right -= 1
    rest_mid = single_digit(left, right) if right - left >= 0 else ""
    res = "|".join(filter(None, [rest_left, rest_mid, rest_right]))
    return f"(?:{res})" if need_brackets else res

def make_regex(start, end):
    if not re.match(r"\d\d:[0-5]\d", start):
        raise ValueError("start time has wrong format") 
    if not re.match(r"\d\d:[0-5]\d", end) or end > "23:59":
        raise ValueError("end time has wrong format or is out of range") 
    if start > end:
        raise ValueError("start time must not be greater then end time")
    return "^" + make_regex_rec(start, end, "23:59", True)

演示运行：

regex = make_regex("19:00", "23:59")
print(regex)
regex = make_regex("09:30", "15:30")
print(regex)

输出为：

^(?:19|2)
^(?:09:(?:[3-5])|1(?:[0-4]|5:(?:[0-3])))

如果您打算将正则表达式与

re.match

一起使用，那么您实际上并不需要

^

锚点，因为

re.match

需要匹配作为输入字符串的前缀。在这种情况下，您可以将此行作为

make_regex

:

中的最后一条语句

return make_regex_rec(start, end, "23:59", False)

那么输出将是：

19|2
09:(?:[3-5])|1(?:[0-4]|5:(?:[0-3]))