Fuzzy Reguläre Ausdrücke

In meiner Arbeit habe ich mit guten Ergebnissen ungefähre String-Matching-Algorithmen wie Damerau-Levenshtein verwendet, um meinen Code weniger anfällig für Rechtschreibfehler zu machen.Fuzzy Reguläre Ausdrücke

Jetzt muss ich Zeichenfolgen mit einfachen regulären Ausdrücken wie TV Schedule for \d\d (Jan|Feb|Mar|...) übereinstimmen. Dies bedeutet, dass die Zeichenfolge TV Schedule for 10 Jan zurückgeben sollte 0, während T Schedule for 10. Jan 2.

zurückkehren soll dies durch die Generierung alle Strings in der Regex (in diesem Fall 100x12) und finden Sie die beste Übereinstimmung getan werden könnte, aber das praktisch keine Naht.

Haben Sie Ideen, wie Sie das effektiv machen können?

Quelle

2010-02-28 Thomas Ahle

Ich fand die TRE library, die Nähte in der Lage, genau Fuzzy-Matching von regulären Ausdrücken zu tun. Beispiel: http://hackerboss.com/approximate-regex-matching-in-python/ Es unterstützt nur Einfügen, Löschen und Ersetzen obwohl. Keine Umsetzung. Aber ich denke, das funktioniert gut.

versuchte ich das begleitende agrep Werkzeug mit dem regulären Ausdruck 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 eine Menge

$ 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 Ihre schlägt.

Quelle

2010-03-04 10:54:24

Haben Sie darüber nachgedacht, eine lexer zu verwenden?

Ich habe noch nie eine benutzt, also kann ich nicht viel helfen, aber es klingt wie es passt!

Quelle

2010-02-28 16:18:47

Ich denke, Lexer sind mehr zum Tokenizing als zum Matching. Wenn ich meine Zeichenfolge aufspalte, kann ich keine Zeichen erkennen, die von einem Token zu einem anderen verschoben wurden. –

Möglicherweise müssen Sie Ihr Problem als Lexing/Parsing-Problem und nicht als einfachen regulären Ausdruck definieren. Dann könntest du die Levenshtein-Distanz auf den einzelnen Wertmarken verwenden. – Avi

Ich verstehe. Aber der Lexer-Link, den Sie gesendet haben, ist ziemlich deterministisch. Was wäre, wenn statt "TV-Spielplan für 10 Jan" 'TV-Plan für Jan 10' eintreffen würde? Dieser sollte einen Abstand von 2 haben, da zwei Zeichen transponiert wurden. Vielleicht könnte der Lexer Teilstrings identifizieren, die wie Zahlen oder Monate aussehen, aber dann würde "TV-Plan für Jan 10" oder "TV-Plan für 10 Jan 2010" Probleme bereiten .. –

Here ist eine Ressource zu der Frage, die Sie stellen möchten. Es ist ein bisschen ein Teaser für eine Firma. Nützlicher könnte this paper sein. Ich habe eine von der Arbeit inspirierte Implementierung gesehen, die eine unscharfe Suche nach einer speziellen Sprache (z. B. Arabisch vs. Englisch) in einem großen Datensatz durchführen kann.

Im Allgemeinen werden Sie nicht in der Lage sein zu tun, worum Sie gebeten haben. Sie können eine Regexp-Suche unscharf machen, indem Sie Zeichen durch Äquivalenzklassen ersetzen, oder Sie können in einer Datenbank nach Beinahe-Übereinstimmungen suchen, die durch die Levenshtein-Distanz definiert sind. Der Versuch, das (n) DFA hinter einem Regexp zu erweitern, um Beinahe-Übereinstimmungen nach Entfernung einzubeziehen, würde schnell unmöglich werden.

Quelle

2010-02-28 16:33:06 bmargulies

Der erste scheint auf Standard-Näherungs-String-Matching zu sein? Der zweite scheint auf unscharfen Nachschlagen in einem Wörterbuch zu sein. Das könnte wahrscheinlich verwendet werden, um die Regex als ein fictionary Wörterbuch zu denken? –

Ich verwende einfach die regex module: 'Alternative Regular Expression-Modul, um zu ersetzen.' Es bietet die Vertrautheit von re, enthält jedoch Optionen für die Fuzzy-Anpassung sowie mehrere andere Verbesserungen an re.

Für Windows-Binärdateien siehe this resource.

Quelle

2013-04-12 15:46:39

Siehe auch: Die Python regex (newer version, Oct '14) (suchen Sie im Dokument nach "unscharf").

Wenn Sie kein Python-Typ sind (weder ich noch), Sie could compile Ihren Code zu C (exe/dll). Dann könntest du deine dll sogar aus gutem alten vb6 (und ähnlichem) benutzen.

Andere Bibliotheken zur Auswahl:

TRE/agrep ('klassische, gut, alt und schnell) (Suche nach 'agrep Performace'), aber Sie müssen POSIX kompatibel regex (Suche schreiben für 'reguläre Ausdrücke info posix') Natürlich haben alle Bibliotheken/Beispiele, die TRE verwenden, diese Einschränkung (nach 'hackerboss approximate regex matching in python' suchen). Für massive Daten: Suchen Sie nach 'Eine schnelle CUDA-Implementierung eines Agrep-Algorithmus'.
FREJ (Java) - einige (mehr) Einschränkungen (zum Beispiel nicht nach vorne schauen/Blick hinter)
Fuzzy-wuzzy (Python-basierte) - lohnt einen Blick auf, nicht getestet ...

Suche auch für:

'Comparison_of_regular_expression_engines'
'regular-expressions.info Tools'

(sorry für echte Links nicht in der Lage sein, schreiben)

Quelle

2014-10-26 23:23:53

ich ein Java-Tool namens prex für ungefähre reguläre Ausdrücke implementieren gestartet. Das Werkzeug wird bestimmt, wie weit ein String s aus ist ein regulärer Ausdruck r passenden, dh wie viele Insertionen, Deletionen und Substitutionen an s mindestens erforderlich (minimum cost), so dass die resultierenden Zeichenfolge s' ist akzeptabel von r. Wenn Sie interessiert sind, können Sie den Code von https://github.com/julianthome/prex überprüfen. Ich wäre sehr glücklich, ein Feedback zu bekommen. Beachten Sie, dass der Ansatz immer noch ein bisschen langsam ist, aber ich nehme derzeit einige Heuristiken zur Verbesserung seiner Leistung auf.

Quelle

2016-09-18 12:36:36 Julian

Antwort

Verwandte Themen