Fuzzy Reguläre Ausdrücke

In meiner Arbeit habe ich mit sehr guten Ergebnissen eingesetzt Ungefähre string-matching-algorithmen wie Damerau–Levenshtein-Distanz, um meinen code weniger anfällig für Schreibfehler.

Nun ich habe ein Bedürfnis zu entsprechen Saiten gegen einfache reguläre Ausdrücke wie TV Schedule for \d\d (Jan|Feb|Mar|...). Dies bedeutet, dass der string TV Schedule for 10 Jan sollte 0 zurückgegeben werden, während T Schedule for 10. Jan zurückkehren sollte, 2.

Umgesetzt werden könnte dies durch die Generierung alle Zeichenfolgen in der regex (in diesem Fall 100x12) und finden Sie am besten passt, aber nicht, dass die Naht praktisch.

Haben Sie irgendwelche Ideen, wie man dies effektiv zu tun?

InformationsquelleAutor der Frage Thomas Ahle | 2010-02-28

  1. 20

    Fand ich die TRE-Bibliothekdie scheint, in der Lage sein, genau das zu tun, fuzzy-matching von regulären Ausdrücken. Beispiel: http://hackerboss.com/approximate-regex-matching-in-python/
    Es unterstützt nur die insertion, deletion und substitution aber. Keine Umsetzung. Aber ich denke, das funktioniert ok.

    Ich habe versucht, die begleitenden agrep-tool, mit dem regexp auf die folgende Datei:

    TV Schedule for 10Jan
TVSchedule for Jan 10
T Schedule for 10 Jan 2010
TV Schedule for 10 March
Tv plan for March

    und bekam

    $ agrep -s -E 100 '^TV Schedule for \d\d (Jan|Feb|Mar)$' filename
1:TV Schedule for 10Jan
8:TVSchedule for Jan 10
7:T Schedule for 10 Jan 2010
3:TV Schedule for 10 March
15:Tv plan for March

    Vielen Dank für alle Ihre Vorschläge.

    InformationsquelleAutor der Antwort Thomas Ahle

  2. 4

    Ich gerade das regex - Modul: 'Alternative regulären Ausdruck Modul zu ersetzen, re.' Es bietet die Vertrautheit des re aber enthält Optionen für fuzzy-matching, zusammen mit einigen anderen Verbesserungen auf re.

    Für Windows-Binärdateien finden Sie unter diese Ressource.

    InformationsquelleAutor der Antwort David C

  3. 4

    Siehe auch:Python-regex (neuere version, Okt '14) (Suche nach "fuzzy" im Dokument).

    Wenn Sie nicht gerade ein Python-Mann (nicht ich bin), Sie kompilieren könnte code C (exe/dll). Dann würden Sie in der Lage sein zu verwenden Ihre dll-sogar aus dem guten alten vb6 (und der wie).

    Anderen Bibliotheken, zum von zu wählen:

    • TRE/agrep (klassische, gute, alte und schnell) (suchen Sie nach "agrep performace'), aber Sie brauchen, um zu schreiben POSIX-kompatible regex (search for 'regular-expressions info posix -')
      Natürlich, alle Bibliotheken/Beispiele für die Verwendung von TRE haben diese Einschränkung (Suche nach 'hackerboss Ungefähre regex-matching in python'). Für große Datenmengen: die Suche nach einem "schnell-CUDA-Implementierung des Algorithmus, agrep'.
    • FREJ (Java) - einige (weitere) Einschränkungen (z.B. kein look ahead/look behind)
    • fuzzy-wuzzy (Python-basiert) - einen Blick Wert, nicht getestet...

    Suchen Sie auch:

    • 'Comparison_of_regular_expression_engines'
    • 'regular-expressions.info tools'

    (sorry für nicht in der Lage, post real links)

    InformationsquelleAutor der Antwort Mihail Stanculescu

  4. 3

    Hier ist eine Ressource, auf die Frage, die Sie Fragen. Es ist ein bisschen ein teaser für ein Unternehmen. Mehr nützlich sein könnte dieses Papier. Ich habe gesehen, eine Umsetzung inspiriert durch das Papier, das das tun könnte, fuzzy-Suche, voreingenommen für die spezielle Sprache (z.B. Arabisch vs. Englisch), die auf einen großen Datenbestand.

    Im Allgemeinen, Sie werden nicht in der Lage zu tun, was Sie gefragt haben. Sie können eine regexp-Suche fuzzy-durch ersetzen von Zeichen mit äquivalenz-Klassen, oder Sie können nach einer Datenbank für nahe-Spiele definiert durch die Levenshtein-Distanz. Versuchen, erweitern die (n)DFA hinter einer regexp zu schließen nahe-Spiele, durch die Entfernung würde sich rasch zu unglaublich Komplex.

    InformationsquelleAutor der Antwort bmargulies

  5. 1

    Haben Sie sich überlegt mit einem lexer?

    Hab ich eigentlich noch nie eines benutzt, so kann ich nicht viel helfen, aber es klingt wie es passt!

    InformationsquelleAutor der Antwort Paul Creasey

  6. 0

    Ich begann zu implementieren Sie eine Java-tool namens-präx für die Ungefähre übereinstimmung von regulären Ausdrücken. Das tool legt fest, wie weit ein string s ist aus übereinstimmenden regulären Ausdruck rd.h. wie viele Einfügungen, Löschungen und Substitutionen auf s sind mindestens erforderlich (minimale Kosten), so dass der resultierende string s' akzeptable r. Wenn Ihr interessiert sind, Sie können check out den code aus https://github.com/julianthome/prex. Ich wäre sehr froh um einige Rückmeldungen. Beachten Sie, dass der Ansatz noch ein bisschen langsam, aber ich bin derzeit die einige Heuristiken für die Verbesserung seiner Leistung.

    InformationsquelleAutor der Antwort Julian

Schreibe einen Kommentar