Abstand zwischen regulärem Ausdruck

Question

Können wir eine Art Abstand zwischen regulären Ausdrücken berechnen?

Die Idee ist es, zu messen, wie zwei reguläre Ausdrücke ähnlich sind.

Answer 1

Es gibt ein paar von Metriken könnten Sie verwenden:

1. Die Länge eines gültigen Spiel. Einige Regexs haben eine feste Größe, einige eine obere Grenze und einige eine untere Grenze. Vergleichen Sie, wie ähnlich ihre Längen oder möglichen Längen sind.

2. Die Zeichen, die übereinstimmen. Jeder reguläre Ausdruck enthält eine Reihe von Zeichen, die eine Übereinstimmung enthalten kann (möglicherweise alle Zeichen). Vergleichen Sie die Menge der enthaltenen Zeichen.

3. Verwenden Sie ein großes Dokument und sehen Sie, wie viele Übereinstimmungen jede Regex macht und wie viele davon identisch sind.

Suchen Sie eine strenge Äquivalenz?

Answer 2

Ich denke zuerst müssen Sie für sich selbst verstehen, wie Sie einen "Unterschied" zwischen zwei Ausdrücken sehen. Definieren Sie im Grunde genommen eine Entfernungsmetrik.

Im allgemeinen Fall wäre es ganz anders zu machen. Je nachdem, was Sie tun müssen, sehen Sie möglicherweise einen anderen Charakter an einer Stelle als einen großen Unterschied. In dem anderen Fall kann das Zulassen einer beliebigen Anzahl von aufeinanderfolgenden, aber gleichen Zeichen keinen großen Unterschied ergeben.

Ich möchte auch betonen, dass normalerweise, wenn sie über Abstandsfunktionen sprechen, sie sie auf ... anwenden, nennen wir sie, Tokens. In unserem Fall Zeichenfolgen. Was Sie tun möchten, ist, diese Methode nicht auf diese Token anzuwenden, sondern auf die Regeln, die eine Vielzahl von Tokens treffen. Ich bin mir nicht ganz sicher, ob das überhaupt Sinn macht.

Dennoch glaube ich, dass wir etwas denken könnten, aber nicht im Allgemeinen, aber für einen bestimmten und ziemlich beschränkten Fall. Hast du ein Beispiel, um uns zu zeigen?

Answer 3

Sie können deterministic finite-state machines für beide regulären Ausdrücke erstellen und die Übergänge vergleichen. Der Unterschied beider Übergänge kann dann verwendet werden, um den Abstand dieser regulären Ausdrücke zu messen.

Answer 4

Wenn Sie zwei reguläre Ausdrücke haben und eine Reihe von Beispieleingaben haben, können Sie versuchen, jede Eingabe für jede Regex abzugleichen. Für jeden Eingang:

• Wenn sie beide übereinstimmen oder beide nicht übereinstimmen, Score 0
• Wenn man Matches und der andere nicht, nicht 1.

Summe dieser Partitur über ein Tor alle Eingaben, und dies wird Ihnen einen 'Abstand' zwischen den regulären Ausdrücken geben. Dies gibt Ihnen eine Vorstellung davon, wie oft sich zwei reguläre Ausdrücke für typische Eingaben unterscheiden. Es ist sehr langsam zu berechnen, wenn Ihr Beispiel-Eingabe-Set groß ist. Es funktioniert überhaupt nicht, wenn beide Regexes für fast alle zufälligen Zeichenfolgen nicht übereinstimmen und Ihre erwartete Eingabe völlig zufällig ist. Zum Beispiel würden die Regex 'sgjlkwren' und die Regex 'ueuuenwbkaalf' wahrscheinlich beide nie übereinstimmen, wenn sie mit zufälligen Eingaben getestet würden, also würde diese Metrik sagen, dass der Abstand zwischen ihnen Null ist. Das könnte oder könnte nicht das sein, was du willst (wahrscheinlich nicht).

Sie können möglicherweise die Struktur der Regex analysieren und voreingestellte Stichproben verwenden, um absichtlich Zeichenfolgen zu treffen, die häufiger übereinstimmen als bei vollständig zufälligen Eingaben. Wenn beispielsweise beide Regex erfordern, dass die Zeichenfolge mit "foo" beginnt, können Sie sicherstellen, dass Ihre Testeingaben auch immer mit foo beginnen, um zu vermeiden, dass Sie Zeit mit Strings verschwenden, von denen Sie wissen, dass sie fehlschlagen.

Also zum Schluss: Wenn Sie nicht eine sehr spezifische Situation mit einer eingeschränkten Eingabesatz und/oder eingeschränkten regulären Ausdruck Sprache haben, würde ich sagen, es ist nicht möglich. Wenn Sie einige Einschränkungen für Ihre Eingabe und den regulären Ausdruck haben, ist dies möglicherweise möglich. Bitte geben Sie an, was diese Einschränkungen sind und vielleicht kann ich mir etwas besseres einfallen lassen.

Answer 5

Ich nehme an, Sie könnten einen Levenshtein Distance zwischen den tatsächlichen Regular Expesssion Strings berechnen. Das ist sicherlich eine Möglichkeit, eine "Entfernung" zwischen zwei verschiedenen Regular Expression-Strings zu messen.

Natürlich ist es möglich, dass hier keine regulären Ausdrücke benötigt werden, und die Berechnung der Levenshtein-Distanz der tatsächlichen "value" -Strings, auf die die regulären Ausdrücke sonst angewendet würden, kann ein besseres Ergebnis liefern.

Answer 6

Es gibt eine Antwort in einer früheren Frage hier auf SO versteckt: Generating strings from regexes. Sie können ein (asymmetrisches) Distanzmaß berechnen, indem Sie Strings mit einem Regex generieren und überprüfen, wie viele davon mit dem anderen Regex übereinstimmen.

Dies kann optimiert werden, indem gemeinsame Präfixe/Suffixe entfernt werden. Z.B. a[0-9]* und a[0-7]* teilen Sie das a Präfix, so können Sie stattdessen den Abstand zwischen [0-9]* und [0-7]* berechnen.