如何在Julia中生成与正则表达式匹配的随机字符串？

Question

如何在Julia中生成与正则表达式匹配的随机字符串？

8

代码

using Random: randstring

function rand_matching(regex; max_len=2^16, max_attempts=1000)
    for _ in max_attempts
        str  = randstring(max_len)
        m = match(regex, str)
        if m != nothing
            # rather than return whole string, 
            # just return the shortest bit that matches
            return m.match
        end
    end
    error("Could not find any string that matches regex")
end

演示：

julia> @time rand_matching(r"\d\d")
  0.013517 seconds (34.34 k allocations: 1.998 MiB)
"38"

julia> @time rand_matching(r"\d\d")
  0.001497 seconds (11 allocations: 128.656 KiB)
"44"

julia> @time rand_matching(r"a\d\d")
  0.000670 seconds (11 allocations: 128.656 KiB)
"a19"

julia> @time rand_matching(r"a\d\d")
  0.000775 seconds (11 allocations: 128.656 KiB)
"a83"

julia> @time rand_matching(r"a\d\db")
  0.000670 seconds (11 allocations: 128.656 KiB)
"a44b"

- Frames Catherine White

其他语言中发现的多个实现（甚至包括实现PCRE的语言）使我相信这个任务并非不可能，我没有深入研究细节，也许他们正在使用更严格的PCRE版本。随机抛出字符串希望其中一个与正则表达式匹配对于小型、简单的正则表达式来说还可以，但它不太可扩展......感谢您指向Automa，因为它正好匹配了我问题的下一步。也许它能一举解决两个问题！ - Thomas Jalabert

即使它不是不可能的（停机问题等效），它仍然应该具有巨大的时间复杂度。您可以将任何问题实现为仅接受解决方案的PCRE正则表达式。因此，例如，您可以使用仅接受私钥的PCRE打破公钥加密，然后要求一个随机的私钥。或者实现任何NP完全问题，如子集和，根据子集和是否存在接受“T”或“F”。如果您的PCRE匹配正则表达式生成器在多项式时间内工作，则恭喜您已经证明了P = NP。 - Frames Catherine White

嗯，也许 PCRE 实际上并不是图灵完备的。我可能完全错了。它们可能只相当于上下文无关文法。它们可以做一些疯狂的事情，比如素数检测。因此，你肯定可以用你的随机字符串生成器来生成质数。而且很可能可以破解公钥加密。 - Frames Catherine White

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

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

- phipsgabler · Accepted Answer

可以使用 Automa.jl构建DFA并随机遍历它。Automa使用比PCRE更简单的语法，因此您可以用它描述的语言实际上应该是正则的。

我快速地根据dot.jl中的代码编写了以下内容：

julia> function rand_re(machine::Automa.Machine)
           out = IOBuffer()
           node = machine.start
           
           while true
               if node.state ∈ machine.final_states
                   (rand() ≤ 1 / (length(node.edges) + 1)) && break
               end
               
               edge, node = rand(node.edges)
               label = rand(collect(edge.labels))
               print(out, Char(label))
           end
           
           return String(take!(out))
       end
rand_re (generic function with 1 method)

julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a6bbb"

julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a9b"

julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a3aa"

julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a1a"

julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a5ba"

警告是 Automa 使用字节编码集来表示边缘标签，因此在我只写 Char(label) 的地方需要更加小心。

由于最终状态仍然可以有出边，我选择以均匀概率处理停止和每个边缘。我认为这可能会导致潜在的无限期限要么非常短，要么非常长; 谷歌“Boltzmann抽样器”了解如何解决这个问题（不要与从Boltzmann分布中抽样混淆！），但解决方案相当复杂。

或者，您可以使用 ccall 或 PyCall 调用 rxvm_gen 或 Rxvm.gen of librxvm，其中包含（可能）非回溯正则表达式的性能良好的代码。