寻找优化的Regex/other解决方案进行大规模字符串匹配

Question

我当前代码的一部分涉及（伪）随机生成相当多的不同长度的字符串对-具体来说

shiftspace = {
    2: 20,
    3: 79,
    4: 250,
    5: 791,
    6: 2500,
    7: 7906,
    8: 25000,
    9: 79059
}

其中key=字符串长度，value=要生成的对。这些字符串可以由字符0-9的任何变体以及表示任何字符的字符*组成。问题在于，我不希望集合包含任何重复。在实现*之前，我只是检查是否已经生成了一个新生成的数字，但是现在字符串可以“重叠”，尽管它们不相同。例如，“*056*3”的存在使生成的序列“*05693”或“905623”或“4056*3”无效

目前的解决方案是我的老“朋友”Regex。我只需生成一个由[char1*][char2*][char3*]等组成的正则表达式字符串，它能够完美地挑出这些匹配项。问题是速度——我根据每个条目检查正则表达式，当达到更高的数字时，正则表达式会及时膨胀（检查的最大可能集可以达到近80k条目的值）。以前需要5分钟的训练现在需要一个小时或更长时间。下面是实现这一切的代码

def regexfit(strang,set):
    regex = ""
    for char in strang:
        regex = regex + "["+char+"*]"
    match = re.search(regex,set)
    if match:
        return True

def shiftgen():
    baseset = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "*"]
    shiftset = {}
    keys = list(shiftspace.keys())
    togo = sum(shiftspace.values())
    print(togo)
    for i in range(min(keys), max(keys) + 1):
        print(i)
        shiftset[i] = {}
        shiftset[i]["0"] = 0
        for j in range(shiftspace[i]):
            num = 0
            num2 = 0
            while num == num2:
                num = np.random.choice(baseset, size=i)
                num = "".join(num)
                numset = [i for i in str(num)]
                while any((regexfit(num,x) for x in shiftset[i].keys())):
                    num = np.random.choice(baseset, size=i)
                    num = "".join(num)
                    numset = [i for i in str(num)]
                if len(str(num)) < i:
                    for k in range(i - len(str(num))):
                        numset.append(0)
                num2 = np.random.choice(numset, size=i, replace=False)
                num2 = "".join(num2)
            shiftset[i][num] = num2
            togo = togo - 1
            if togo % 1000 == 0:
                print([num, num2])
        shiftset[i].pop("0")
    return shiftset

我考虑过的事情：

• 将所有序列连接到一个大字符串中（使用分隔符char防止正则表达式在两个序列之间匹配），并在该字符串上使用正则表达式。我对re引擎的内部结构知之甚少，不知道最终会有多好。一旦我完成了上面代码的第一次定时测试，我将测试它的运行速度

• 将这些带星号的字符串添加到数据库中，尽可能简单地进行所有可能的排列（即：2*添加为21、22、23等）>；。然后，您只需搜索数据库（或者，如果生成一个带星号的字符串，则搜索每个排列并检查是否有正排列）。我非常怀疑这会更有效率，但你永远不知道

• 某种解决方案，您可以生成序列，确定它们之前未生成或将被先前生成的序列“覆盖”，从而消除完全搜索的需要。这不是一个真正的解决方案，因为我不知道如何做到这一点，但只是把它扔出去

• 某种更高级的正则表达式，计算速度更快

• 某种神奇的模块/公式，出于某种原因，它非常擅长做这件事

• 黑魔法、向老神献祭等。

TL：博士，我正在寻找一种更快的方法来匹配具有许多潜在排列的序列，以确保之前没有选择排列

Answer 1

几句评论，总的来说太长了一句评论

在当前代码中构建的正则表达式实际上并不正确。当您在{}中遇到一个{}时创建的字符类{}将仅与{}中的一个{}相匹配，您实际上希望在该类中匹配任何字符。当您在strang中遇到一个*时，实际上应该在正则表达式中放置一个.。例如：

regex = ''.join('.' if c == '*' else '[*' + c + ']' for c in strang)

其次，您应该使用re.match而不是re.search，因为它将搜索定位到字符串的开头，从而防止从输入中的每个位置开始搜索。这将稍微提高速度

最后，它应该比使用regex（我的测试表明是3-4x）简单地迭代每个值中的字符更快，一个接一个地比较它们，并且在没有匹配时立即失败，例如

def regexfit(strang,set):
    for a, b in zip(strang, set):
        if a != '*' and b != '*' and a != b:
            return False
    return True