Ist es möglich, den Bearbeitungsabstand zwischen einem regulären Ausdruck und einer Zeichenfolge zu berechnen?

Question

Wenn ja, erläutern Sie bitte wie.

Re: was ist Abstand - "Der Abstand zwischen zwei Strings ist definiert als die minimale Anzahl von Änderungen erforderlich, um einen in den anderen zu konvertieren."

Zum Beispiel, XYZ zu XYZ würde 3 Bearbeitungen, also die Zeichenfolge xYZ näher an XYZ und XYZ.

Wenn das Muster [0-9] {3} oder beispielsweise 123 ist, dann wäre a23 näher am Muster als ab3.

Wie können Sie den kürzesten Abstand zwischen einer regulären und einer nicht passenden Zeichenfolge finden?

Oben ist der Damerau–Levenshtein Distanzalgorithmus.

Answer 1

Sie können Finite State Machines verwenden, um dies effizient (dh linear in der Zeit) zu tun . Wenn Sie einen Transducer verwenden, können Sie sogar die Spezifikation der Transformation ziemlich kompakt schreiben und weit nuanciertere Transformationen als einfach einfügen oder löschen - siehe Wikipedia für Finite State Transducer als Ausgangspunkt, und Software wie das FSA-Toolkit oder FSA6 (das hat ein nicht ganz stabiler web-demo) auch. Es gibt viele Bibliotheken für FSA-Manipulation; Ich möchte nicht vorschlagen, dass die vorherigen zwei Ihre einzigen oder besten Optionen sind, nur zwei, von denen ich gehört habe.

Wenn Sie jedoch nur die effiziente, ungefähre Suche wünschen, gibt es eine weniger flexible, aber bereits implementierte Option: TRE, die eine approximate matching function hat, die die Kosten für das Match zurückgibt - dh die Entfernung zu das Spiel, aus deiner Perspektive.

Answer 2

Wenn Sie die Zeichenfolge mit dem kleinsten Levenshtein Abstand zwischen der am nächsten übereinstimmenden Zeichenfolge und einem Beispiel meinen, bin ich ziemlich sicher, dass es getan werden kann, aber Sie müssten die Regex selbst zu einem DFA konvertieren, dann versuchen Sie es zu passen und immer wenn etwas schief geht, nicht-deterministisch weitermachen, als ob es bestanden hätte, und die Anzahlunterschiede im Auge zu behalten. Sie könnten A * Suche oder etwas ähnliches dafür verwenden, es wäre jedoch ziemlich ineffizient (0 (2^n) worst case)