tre
TRE 0.9.0
Dieses Projekt sucht nach Betreuer. Für den Anfang gibt es einige Anfragen, die auf die Überprüfung warten.
Lassen Sie es mich unter [email protected] wissen, wenn Sie sich steigern möchten!
TRE ist eine leichte, robuste und effiziente POSIX -konforme Regexp -Bibliothek mit einigen aufregenden Funktionen wie ungefähren (Fuzzy) Matching.
Der in TRE verwendete passende Algorithmus verwendet die lineare schlimmste Zeit in der Länge des durchsuchenden Textes und die quadratische Schlimmstezeit in der Länge des verwendeten regulären Expression.
Mit anderen Worten, die zeitliche Komplexität des Algorithmus ist o (m^2n), wobei m die Länge des regulären Ausdrucks und n die Länge des Textes ist. Der verwendete Raum ist auch quadratisch auf der Länge des Regex, hängt jedoch nicht von der durchsuchten Zeichenfolge ab. Dieses quadratische Verhalten tritt nur in pathologischen Fällen auf, die in der Praxis wahrscheinlich sehr selten sind.
Hier erfahren Sie, wie man mit diesem Code arbeitet.
Sie benötigen die folgenden Tools, die auf Ihrem System installiert sind:
Bereiten Sie zuerst den Baum vor. Wechseln Sie zur Wurzel des Quellverzeichnisses und laufen Sie
./utils/autogen.sh
Dadurch werden verschiedene Dinge mit den Voraussetzungen regeneriert, damit Sie einen baubaren Baum haben.
Danach können Sie das Konfigurationsskript ausführen und Tre wie gewohnt erstellen:
./configure
make
make check
make install
In einem vorbereiteten Baum erstellt dieser Befehl einen Quellcode -Tarball:
./configure && make dist
Alternativ können Sie rennen
./utils/build-sources.sh
Dies erstellt die Quellcodepakete und stellt sie in das dist -Unterverzeichnis. Dieses Skript braucht einen funktionierenden zip -Befehl.
Tre ist nicht nur ein weiterer Regexp -Matcher. TRE verfügt über einige Funktionen, die in den meisten freien POSIX -kompatiblen Implementierungen nicht vorhanden sind. Die meisten dieser Funktionen sind auch in nicht freien Implementierungen nicht vorhanden.
Das ungefähre Muster -Matching ermöglicht die ungefähre Übereinstimmung, dh die Übereinstimmungen in der Nähe des durchsuchten Musters unter einem Maß der Nähe. TRE verwendet das Bearbeitungsdistanzmaß (auch als Levenshtein-Distanz bezeichnet), in dem Zeichen eingefügt, gelöscht oder im durchsuchten Text ersetzt werden können, um eine genaue Übereinstimmung zu erhalten.
Jede Einfügung, Löschung oder Substitution fügt die Entfernung oder Kosten des Spiels hinzu. Tre kann die Übereinstimmungen melden, die eine Kosten niedriger als ein bestimmter Schwellenwert haben. Tre kann auch verwendet werden, um nach Übereinstimmungen mit den niedrigsten Kosten zu suchen.
TRE enthält eine Version des Agrep -Befehlszeilenwerkzeugs (ungefähre GREP) für ungefähre Regexp -Übereinstimmung im Stil von Grep. Im Gegensatz zu anderen AGREP-Implementierungen (wie die von Sun Wu und Udi Manber von der University of Arizona) ermöglicht Tre Agrerp vollständige Regexps jeglicher Länge, einer beliebigen Anzahl von Fehlern und ungleichmäßigen Kosten für Insertion, Löschung und Substitution.
POSIX definiert das Verhalten von Regexp -Funktionen genau. Tre versucht, sich diesen Spezifikationen so streng wie möglich anzupassen. TRE gibt beispielsweise immer die richtigen Übereinstimmungen für Subpattern zurück. Sehr wenige andere Implementierungen tun dies richtig. Tatsächlich sind die einzigen anderen Implementierungen neben Tre, die mir der (frei oder nicht) bewusst bin, die es richtig machen, von Tom Lord, Regex ++ von John Maddock und der AT & T Ast Regex von Glenn Fowler und Doug McIlroy.
Das Standard-Tre versucht, sich an die IEEE STD 1003.1-2001 oder die offene Gruppenbasisspezifikationen 6, die allgemein als „POSIX“ bezeichnet wird, ist. Die relevanten Teile sind die Basisspezifikationen zu regulären Ausdrücken (und der Begründung) und der Beschreibung der regcomp() -API.
Eine hervorragende Umfrage zu POSIX Regexp -Mattern finden Sie in den Testregex -Seiten von Glenn Fowler von AT & T Labs Research.
Aufgrund des in TRE verwendeten passenden Algorithmus ist die maximale Zeit, die von einem regexec() -Anruf verbraucht wird, immer direkt proportional zur Länge der durchsuchten Zeichenfolge. Es gibt eine Ausnahme: Wenn Rückenreferenzen verwendet werden, kann die Übereinstimmung Zeit in Anspruch nehmen, die exponentiell mit der Länge der Zeichenfolge wächst. Dies liegt daran, dass die Rückzugreferenzen ein NP -volles Problem darstellen und mit ziemlicher Sicherheit eine exponentielle Zeit erfordert, um im schlimmsten Fall übereinzustimmen.
Ein regexec() -Anruf weist niemals Speicher vom Heap zu. TRE verteilt den gesamten Speicher, den es während eines regcomp() -Anrufs benötigt, und einen temporären Arbeitsbereich aus dem Stapelrahmen für die Dauer des regexec() -Anrufs. Die Menge an vorübergehenden Platz ist während des Matchings konstant und hängt nicht von der durchsuchten Zeichenfolge ab. Für Regexps mit angemessener Größe benötigt TRE während des regcomp() -Anrufs weniger als 20.000 ein dynamisch zugewiesenes Speicher, weniger als 20.000 für den kompilierten Musterpuffer und weniger als zwei Kilobyten temporärer Arbeitsbereich aus dem Stackrahmen während eines regexec() -Anrufs. Es gibt keinen Zeit- / Gedächtnis -Kompromiss. TRE ist auch kleiner Codegröße; Statisch mit TRE erhöht die ausführbare Größe von weniger als 30.000 (GCC-3,2, x86, GNU/Linux).
TRE unterstützt Multibyte -Charakter -Sets. Dies ermöglicht es, Regexps nahtlos mit beispielsweise japanische Orte zu verwenden. TRE bietet auch eine breite API mit Charakter.
TRE liefert APIs, die binäre Zero -Zeichen sowohl in Regexps als auch in durchsuchten Zeichenfolgen ermöglichen. Die Standard -API kann beispielsweise nicht leicht verwendet werden, um nach druckbaren Wörtern aus binären Daten zu suchen (obwohl sie bei einigem Hacking möglich ist). Die Suche nach Mustern, die binäre Nullen enthalten, ist mit der Standard -API überhaupt nicht möglich.
Tre ist vollständig sicher. Alle exportierten Funktionen sind wieder eingetreten, und ein einzelnes zusammengestelltes Regexp-Objekt kann gleichzeitig in mehreren Kontexten verwendet werden. zB in main() und einem Signalhandler oder in vielen Fäden einer multitHhread -Anwendung.
TRE ist über mehrere Plattformen hinweg tragbar. Im Folgenden finden Sie eine Tabelle mit Plattformen und Compilern, die zum Entwicklung und Testen von TRE verwendet wurden:
| Plattform | Compiler |
|---|---|
| FreeBSD 14.1 | Klang 18 |
| Ubuntu 22.04 | GCC 11 |
| macOS 14.6 | Klang 14 |
| Windows 11 | Microsoft Visual Studio 2022 |
TRE sollte ohne Änderungen auf den meisten modernen POSIX-ähnlichen Plattformen kompilieren und mit einer gehosteten C-Implementierung auf jeder Plattform leicht tragbar sein.
Abhängig von der Plattform müssen Sie möglicherweise Libutf8 installieren, um einen breiten Charakter- und Multibyte -Charakter -Set -Support zu erhalten.
TRE wird unter einer Lizenz veröffentlicht, die im Wesentlichen mit der in NetBSBD verwendeten Lizenz im BSD-Stil „2 Klausel“ entspricht. Weitere Informationen finden Sie in der Dateilizenz.
Derzeit gibt es zwei Funktionen, die sich auf Sammelelemente beziehen, die bei einer 100% igen POSIX -Konformität fehlen. Diese sind:
Unterstützung für die Sammlung von Elementen (z. B. [[.<X>.]] , Wobei <X> ein Sammelelement ist). Es ist nicht möglich, multi-charakteristische Sammelelemente portabel zu unterstützen, da POSIX keinen Weg definiert, um festzustellen, ob eine Zeichensequenz ein Multi-Charakter-Sammelelement ist oder nicht.
Unterstützung <X> Äquivalenzklassen, z [[=<X>=]] Eine Äquivalenzklasse entspricht jedem Zeichen, das das gleiche primäre Kollationsgewicht wie <X> hat. Auch hier bietet POSIX keinen tragbaren Mechanismus zur Bestimmung des Primärkollationsgewichts eines Sammelelements.
Beachten Sie, dass auch andere tragbare REGEXP -Implementierungen auch die Sammlung von Elementen unterstützen. Die einzige Ausnahme ist Regex ++, die mit einer eigenen Datenbank für die Sammlung von Elementen für verschiedene Orte ausgestattet ist. Die Unterstützung für Sammlung von Elementen und Äquivalenzklassen wurde nicht weit verbreitet und steht derzeit nicht sehr hoch auf der TODO -Liste.
Dies sind andere Funktionen, die ich jetzt bald umsetzen möchte:
Alle fehlenden GNU -Erweiterungen, die in GNU Regex aktiviert sind, wie [[:<:]] und [[:>:]] .
Ein REG_SHORTEST regexec() Flag für die Rückgabe des kürzesten Spiels anstelle des längsten Spiels.
Perl-kompatible Syntax:
[:^class:] passt alles andere als die Charaktere in der Klasse. Beachten Sie, dass [^[:class:]] bereits funktioniert, dies wäre nur eine Komfort -Kurzform.
A Match erst zu Beginn der String.
Z übereinstimmen nur am Ende der String oder vor Newline am Ende.
z übereinstimmen nur am Ende der String.
l Kleinbuchstaben Nächster Char (denken Sie an VI).
u Großbuchstaben Nächster Char (denken Sie an VI).
L Kleinbuchstaben bis E (denken Sie an VI).
U Großbuchstaben bis E (denken Sie an VI).
(?=pattern) Null-Breiten-positive Look-Ahead-Behauptungen.
(?!pattern) Null-Breiten-Negativ-Look-Ahead-Behauptungen.
(?<=pattern) Null-Breiten-positive Aussehensaussagen.
(?<!pattern) Null-Breiten-negative Aussichtspunkte.
Dokumentation insbesondere include/tre/tre.h die nicht standardmäßigen Merkmale von TRE, wie z. Könnte einige zusätzliche Hinweise liefern, wenn Sie mit C -Quellcode vertraut sind.
