Ändern Sie den String so, dass er dem Regex entspricht

Question

Ist es möglich (oder warum nicht möglich), den Eingabestring in einen String umzuwandeln, der dem Regex mit der geringsten Levenshtein-Distanz entspricht?

d.h. Wenn 1234 der String ist und ^([0-9]{6})$ der Regex ist, brauche ich eine Ausgabe wie 123412 (der Ausgabestring entspricht dem Regex und ist 2 Entfernungen vom Originalstring entfernt, es könnte andere Strings geben, aber das erste Ergebnis wird gemacht).

Wie mache ich das? (kein Brute-Force...)

Bearbeiten:

In anderen Möglichkeiten, kann ich nur die Levenshtein-Distanz erhalten? (ohne passenden String...)

oder welche anderen Informationen kann der Regex außer boolen (Übereinstimmung oder Nicht-Übereinstimmung) geben?

Answer 1

Wenn Sie über endlichen Automaten Bescheid wissen, könnten Sie einen konstruieren, der Ihren Regex repräsentiert (es gibt Bibliotheken, die das tun). Dann führen Sie ihn mit Ihrem String (1234) aus und landen in einem bestimmten Zustand. Von diesem Zustand aus führen Sie eine Breitensuche durch, bis Sie einen akzeptierenden Zustand erreichen. Während Sie suchen, behalten Sie im Auge, über welche Übergänge (Zeichen) Sie laufen. Und die Zeichen geben Ihnen die kürzeste (oder eine davon) Zeichenkette, die Ihrem Regex entspricht.

Hinzugefügter Link: Sie können auf http://www.brics.dk/automaton/ schauen, das ist eine Automaten-Bibliothek, implementiert an der Aarhus Universität (BSD-Lizenz)

Aktualisierung: Ich habe das, wonach Sie suchen, mit der obigen Automatenimplementierung erstellt. Zunächst die Klasse ExtendedOperations, die sich im gleichen Paket wie die anderen Automatenklassen befindet, weil ich auf einige Methoden zugreifen musste.

package dk.brics.automaton;

public class ExtendedOperations {
    //Entnommen aus Automaton.run und modifiziert, um nur den Zustand anstatt der Akzeptanz (bool) zurückzugeben
    static State endState(String s, Automaton a)
    {
        if (!a.deterministic) a.determinize();

        State p = a.initial;
        for (int i = 0; i < s.length(); i++) {
            p = p.step(s.charAt(i));
            if (q == null) return null;
        }
        return p;
    }

    public static String getShortestCompletion(Automaton a, String partlyInput)
    {
        State e = endState(partlyInput, a);

        if (e == null) return null;

        return BasicOperations.getShortestExample(e, true);
    }
}

Zweitens ein kleines Testbeispiel:

package subsetautomaton;

import dk.brics.automaton.*;

public class Main {
    public static void main(String[] args) {
        RegExp re = new RegExp("[a-zA-Z0-9._%+-]+\\@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,6}");
        Automaton a = re.toAutomaton();

        System.out.println(ExtendedOperations.getShortestCompletion(a, "a"));
    }
}

Das Beispiel ist ein einfacher regulärer Ausdruck für eine E-Mail-Adresse. Beachten Sie, dass ^ im regulären Ausdruck implizit ist und dasselbe gilt für $. Zweitens wird @ mit \ maskiert, da es in dieser Implementierung 'beliebige Zeichenkette' bedeutet.

Das Ergebnis des obigen Beispiels lautet: @-.AA