Wie generiere ich zufällige Zeichenfolgen, die mit einem Regex in Julia übereinstimmen?

Antworten:

5

Es sollte möglich sein, Automa.jl zu verwenden, um einen DFA zu erstellen und ihn zufällig zu durchlaufen. Automa verwendet eine einfachere Syntax als PCRE, daher sollte die Sprache, die Sie damit beschreiben können, eigentlich regelmäßig sein.

Ich habe schnell Folgendes zusammengeschmissen, hauptsächlich basierend auf dem Code in 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"

Die Einschränkung besteht darin, dass Automa bytekodierte Sätze für Kantenbeschriftungen verwendet. Daher sollte beim Schreiben mehr Vorsicht geboten sein Char(label).

Da Endzustände immer noch ausgehende Kanten haben können, habe ich mich dafür entschieden, das Anhalten und jede Kante mit einheitlicher Wahrscheinlichkeit zu behandeln. Ich denke, dies wird wahrscheinlich dazu führen, dass potenziell unendliche Begriffe entweder sehr kurz oder sehr lang sind. google "Boltzmann Sampler", wie man das löst (nicht zu verwechseln mit Sampling aus einer Boltzmann-Distribution!), aber die Lösung ist eher mathematisch.

phipsgabler
quelle
5

Julia hat PCRE , was bedeutet, dass seine regulären Ausdrücke weitaus leistungsfähiger sind als echte reguläre Ausdrücke. Und sind in der Tat komplett. Ich vermute, dass es eine Menge interessanter theoretischer Informatik gibt. Ich vermute, dass Ihre Aufgabe für PCRE aufgrund des Halteproblems möglicherweise unmöglich ist . Aber wir können trotzdem ein paar zufällige Zeichenfolgen ausprobieren und diejenigen herauswerfen, die nicht übereinstimmen. Und für einfache Regex geht das einen langen Weg. Es ist jedoch nicht garantiert, eine Antwort zu geben.

Wenn man einen strengeren regulären Ausdruck wünscht , wie die von Automa.jl abgedeckten , gibt es wahrscheinlich etwas Besseres, das getan werden kann, da man die Zustandsmaschine 1 Bit nach dem anderen lösen kann. Hoffentlich kann jemand, der Automa.jl kennt, seine eigene Antwort posten.

Code

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

Demo:

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"
Lyndon White
quelle
Die zahlreichen Implementierungen, die für andere Sprachen gefunden wurden (auch für diejenigen, die PCRE implementieren), lassen mich glauben, dass die Aufgabe nicht unmöglich ist. Ich habe mich nicht mit den Details befasst. Vielleicht verwenden sie eine strengere Version von PCRE. Das Werfen von zufälligen Zeichenfolgen in der Hoffnung, dass eine Übereinstimmung mit der Regex für kleine, einfache Regex in Ordnung ist, aber nicht sehr gut skaliert ... Vielen Dank, dass Sie mich auf Automa hingewiesen haben, da dies genau dem nächsten Schritt meines Problems entspricht. Und vielleicht kann es zwei Fliegen mit einer Klappe schlagen!
Thomas Jalabert
Selbst wenn es nicht unmöglich ist (Problem gleich zu stoppen), sollte es dennoch eine enorme zeitliche Komplexität aufweisen. Sie können jedes Problem als PCRE-Regex implementieren, der nur die Lösung akzeptiert. So können Sie beispielsweise die Verschlüsselung mit öffentlichen Schlüsseln mit einer PCRE unterbrechen, die nur den privaten Schlüssel akzeptiert, und dann nach einem zufälligen Schlüssel fragen. Oder implementieren Sie ein NP-Complete-Problemproblem wie eine Teilmengen-Summe, das akzeptiert Toder davon Fabhängt, ob die Teilmengen-Summe vorhanden ist. Wenn Ihr PCRE-Matching-Regex-Generator in Polynomzeit arbeitet, dann herzlichen Glückwunsch, Sie haben P = NP bewiesen.
Lyndon White
Hmm, vielleicht sind PCRE nicht vollständig abgeschlossen. Ich könnte da einfach falsch liegen. Sie können nur kontextfreien Grammatiken entsprechen. Sie können jedoch einige verrückte Dinge tun, wie die Erkennung von Primzahlen. Defs können also Primzahlen mit Ihrem Zufallsgenerator generieren. Und kann wahrscheinlich Public-Key-Kryptographie brechen.
Lyndon White