Ich versuche, einen Textclusteralgorithmus zu implementieren. Der Algorithmus gruppiert ähnliche Zeilen von Rohtext, indem er sie durch Regex ersetzt, und aggregiert die Anzahl von Mustern, die zu jedem Regex passen, um eine saubere Zusammenfassung des Eingabetextes bereitzustellen, anstatt sich wiederholende Muster aus dem Eingabetext zu zeigen. Bei diesem Versuch bin ich auf die Notwendigkeit gestoßen, herauszufinden, ob eine Regex eine andere abdeckt.
Nehmen wir an, wir sind nur über reguläre Ausdrücke mit '*' und '+' Wildcards betroffen, dh '*' bedeutet null oder mehr Vorkommen eines Alphabets und '+' bedeutet 1 oder mehr Vorkommen eines Alphabets. Nimm auch an, dass der Zeichensatz ASCII ist.
Zum Beispiel:
%Vor%Im Grunde suche ich nach einer effizienten Implementierung der folgenden Methode, die angibt, ob strA (kann eine Regex enthalten) für strB (enthält möglicherweise eine Regex) abdeckt. Beachten Sie, dass es auch eine Möglichkeit geben sollte, den Regex-Zeichen '*' und '+' in den Eingabezeichenfolgen strA und strB zu entgehen.
Methodensignatur in C ++:
%Vor%Ich denke, dass für die Implementierung ein rekursiver Ansatz erforderlich ist, der ein wenig kompliziert sein kann. Aber ich bin neugierig zu wissen, ob ich vorhandene Implementierungen wiederverwenden kann, anstatt das Rad neu zu erfinden oder ob es andere einfache Möglichkeiten gibt, dies zu tun.
Angesichts der einfachen Regex-Grammatik, die Sie vorschlagen, ist die Lösung ziemlich trivial.
Nehmen Sie Ihr komplexeres Beispiel, A+M+BC* covers AMM+B+C+M+BC*
Sie können es als A{1,}M{1,}B{1,1}C{0,} cover A{1,1}M{2,}B{1,}C{1,}M{1,}B{1,1}C{0,}
Dies führt uns zu der einfachen Regel: R1 deckt R2 ab, wenn alle Symbole in der gleichen Reihenfolge erscheinen, alle unteren Grenzen von R1 kleiner oder gleich denen von R2 sind und die oberen Grenzen von R1 sind mehr oder gleich denen von R2 .
Jetzt gibt es ein kleines Problem mit der einfachen Regel. AB*C deckt AC ab, d. h. es besteht die Möglichkeit, dass ein optionales Symbol in R1 und nicht in R2 angezeigt wird. Sie können das lösen, indem Sie ein {0,0} in R2 einfügen, wenn in R1 ein (optionales) Symbol steht, das nicht in der entsprechenden Position in R2 erscheint. Z.B. AB*C deckt AB{0,0}C ab.
Die Regel "optionales Symbol" ist eine Optimierung. Wenn das Symbol in R1 nicht optional ist, deckt R1 sicher nicht R2 ab. Z.B. AB+C deckt AC nicht ab. Daher muss kein B{0,0} eingefügt werden. Aber wenn Sie das tun, sehen Sie, dass A{1,1}B{1,}C{1,1} nicht A{1,1}B{0,0}C{1,1} abdeckt, da die untere Grenze von R1 für B (1) mehr ist als die R2 untere Grenze für B (0)
In Perl wäre das ziemlich einfach. Der erste Schritt besteht darin, jeden Regex zu normalisieren, indem Sie A+ in AA* , A*A in AA* und A*A* in A* :
Schritt zwei besteht darin, die erste Regex von einer Regex, die den Strings selbst entspricht, in eine Perl-Regex zu konvertieren, die mit den normalisierten Regexen übereinstimmt, die diesen Strings entsprechen; Zum Beispiel wird AA*B in ^AA*\*?B$ konvertiert, was "String-Anfang" bedeutet, gefolgt von A gefolgt von null oder mehr As, optional gefolgt von einem Sternchen gefolgt von B gefolgt von einem String-Ende ":
Schritt drei braucht keine Erklärung:
%Vor% Dies gibt einen wahren Wert für Ihre Fälle # 1-3 zurück. Es gibt jedoch einen falschen Wert für Ihren Fall Nr. 4 zurück, da A+M+BC* nicht für AMM+B+C+M+BC* ?
Beachten Sie, dass es auch eine Möglichkeit geben sollte, den Regex-Zeichen '*' und '+' in den Eingabezeichenfolgen strA und strB zu entgehen.
Ich habe mir im obigen Code keine Gedanken darüber gemacht, aber da Sie sich nur um ASCII sorgen, könnte ein Vorverarbeitungsschritt \* bedeuten * , \+ bedeutet + und \ bedeuten \ , indem sie in einzelne Zeichen außerhalb des ASCII-Bereichs übersetzt werden:
(obwohl das offensichtlich ziemlich haschisch ist).
In C ++ können Sie den gleichen Ansatz verwenden - es gibt Bibliotheken, die alle notwendigen Funktionen von Perl-Regexes implementieren - obwohl es natürlich etwas mehr Arbeit wäre.
Überprüfen Sie diese Perl-Modul-Quelle , aber denken Sie daran, dass dies der Fall wäre funktioniert nicht für alle Regexps (da es das Problem lösen löst.
Tags und Links c++ cluster-analysis regex data-mining