¿Cómo generar cadenas aleatorias que coincidan con una expresión regular en Julia?

Preguntas relacionadas:

• Cadena aleatoria que coincide con una expresión regular
• ¿Cómo generar una cadena alfanumérica aleatoria en julia?

La pregunta es bastante simple. Encontré numerosas alternativas para otros idiomas, pero no en Julia:

Generador de texto aleatorio basado en expresiones regulares

Tampoco Random.randstringse toma Regexcomo argumento.

Debería ser posible usar Automa.jl para construir un DFA y recorrerlo aleatoriamente. Automa utiliza una sintaxis más simple que PCRE, por lo que el lenguaje que puede describir en realidad debería ser regular.

Rápidamente reuní lo siguiente, basado principalmente en el código en 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"

La advertencia es que Automa utiliza conjuntos codificados en bytes para las etiquetas de borde, por lo que se debe tener más cuidado cuando escribo Char(label).

Como los estados finales aún pueden tener bordes salientes, elegí tratar la detención y cada borde con probabilidad uniforme. Creo que esto probablemente tendrá el efecto de que términos potencialmente infinitos serán muy cortos o muy largos; google "muestreadores de Boltzmann" sobre cómo resolver eso (¡no debe confundirse con el muestreo de una distribución de Boltzmann!), pero la solución es matemáticamente complicada.

Julia tiene PCRE , lo que significa que sus expresiones regulares son mucho más poderosas que las verdaderas expresiones regulares. Y de hecho, están completos. Sospecho que hay un montón de ciencias informáticas teóricas interesantes sobre esto. Sospecho que su tarea para PCRE podría resultar imposible debido al problema de detención . Pero aún así, lo que podemos hacer es probar un montón de cadenas aleatorias y tirar las que no coinciden. Y para expresiones regulares simples, eso es muy útil. Sin embargo, no se garantiza que responda.

Si uno quisiera una expresión regular más estricta, como las cubiertas por Automa.jl , probablemente haya algo mejor que se pueda hacer, ya que puede recorrer la máquina de estados resolviéndola de a poco. Esperemos que alguien que sepa Automa.jl pueda publicar su propia respuesta.

Código

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

manifestación:

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"