In RegEx, wie finden Sie eine Linie, die nicht mehr als 3 eindeutige Zeichen enthält?

Question

ich durch eine große Textdatei und im am Looping für Linien suchen, der nicht mehr als 3 verschiedene Zeichen enthalten (diese Zeichen kann jedoch wiederholt auf unbestimmte Zeit werden). Ich bin der beste Weg, vorausgesetzt, dies zu tun wäre, eine Art von regulärem Ausdruck sein.

Alle Hilfe ist willkommen.

(ich das Skript in PHP zu schreiben, wenn das hilft)

Answer 1

Vielleicht ist dies funktioniert:

preg_match("/^(.)\\1*(.)?(?:\\1*\\2*)*(.)?(?:\\1*\\2*\\3*)*$/", $string, $matches);
// aaaaa:Pass
// abababcaaabac:Pass
// aaadsdsdads:Pass
// aasasasassa:Pass
// aasdasdsadfasf:Fail

Explaination:

/
 ^                 #start of string
 (.)               #match any character in group 1
 \\1*              #match whatever group 1 was 0 or more times
 (.)?              #match any character in group 2 (optional)
 (?:\\1*\\2*)*     #match group 1 or 2, 0 or more times, 0 or more times 
                   #(non-capture group)
 (.)?              #match any character in group 3 (optional)
 (?:\\1*\\2*\\3*)* #match group 1, 2 or 3, 0 or more times, 0 or more times
                   #(non-capture group)
 $                 #end of string
/

Ein weiterer benifit, $matches[1], [2], [3] die drei Zeichen enthalten, werden Sie wollen. Der reguläre Ausdruck sucht nach dem ersten Zeichen, speichert ihn dann und paßt es, bis etwas anderes als das Zeichen gefunden wird, fängt das als zweites Zeichen, passend zu einem dieses Zeichen so oft wie sie kann, das dritte Zeichen fängt, und Spiele alle drei bis das Spiel ausfällt oder die Zeichenfolge endet und der Test bestanden wird.

Bearbeiten

Dieses regexp wird viel schneller sein, weil die Art, wie die Parsing-Engine und Rückzieher funktionieren, bobince Antwort für die Erklärung lesen:

/^(.)\\1*(?:(.)(?:\\1|\\2)*(?:(.)(?:\\1|\\2|\\3)*)?)?$/

Answer 2

Regex Optimierung Spaß Zeit Übung für Kinder! Unter gnarf regex als Ausgangspunkt:

^(.)\1*(.)?(?:\1*\2*)*(.)?(?:\1*\2*\3*)*$

bemerkte ich, dass es wurden verschachtelt und sequentielle * s hier, was eine Menge Rückzieher verursachen können. Zum Beispiel in ‚abcaaax‘ wird es versuchen, die letzten Zeichenfolge Übereinstimmen von ‚der als Einzel \ 1 * der Länge 3, einen \ 1 * der Länge zwei, gefolgt von einem einzigen \ 1, a \ 1, gefolgt von einer 2-Länge \ 1 * oder drei Einzelspiel \ 1s. Das Problem wird noch schlimmer, wenn Sie längere Strings haben, vor allem, wenn auf Grund der regex stoppen nichts \ 1 davon, dass das gleiche Zeichen wie \ 2.

^(.)\1*(.)?(?:\1|\2)*(.)?(?:\1|\2|\3)*$

Dies war mehr als doppelt so schnell wie das Original, Test auf Python PCRE Matcher. (Es ist schneller, als es nach oben in PHP Einstellung, sorry.)

Das hat immer noch das Problem, dass (.)? kann nichts übereinstimmt, und dann mit dem Rest des Spiels weitermachen. \1|\2 noch \ 1 auch passen, wenn es keine \ 2 zu entsprechen ist, in potenziellen Rückzieher resultierende versuchen, die \1|\2 und \1|\2|\3 Klauseln früher einzuführen, wenn sie nicht in einem Spiel führen kann. Dies kann durch Bewegen des ? optionalness um die Gesamtheit der hinteren Klauseln gelöst werden:

^(.)\1*(?:(.)(?:\1|\2)*(?:(.)(?:\1|\2|\3)*)?)?$

Das war doppelt so schnell wieder.

Es gibt immer noch ein mögliches Problem, dass jeder \ 1, \ 2 und \ 3 kann das gleiche Zeichen sein, möglicherweise mehr Rückzieher zu verursachen, wenn der Ausdruck nicht übereinstimmt. Dies würde aufhört es durch eine negative Vorschau mit keinem vorherigen Zeichen zu finden:

^(.)\1*(?:(?!\1)(.)(?:\1|\2)*(?:(?!\1|\2)(.)(?:\1|\2|\3)*)?)?$

Doch in Python mit meinen zufälligen Testdaten habe ich keine signifikante Beschleunigung von dieser Bekanntmachung. Ihre Laufleistung in PHP abhängig von Testdaten können variieren, aber es könnte schon genug gut sein. Possessive-Matching (* +) könnte dazu beigetragen haben, wenn diese hier zur Verfügung steht.

No regex besser als die leichter zu lesen Python Alternative:

len(set(s))<=3

Die analoge Methode in PHP wäre wahrscheinlich mit count_chars :

strlen(count_chars($s, 3))<=3

ich die Geschwindigkeit nicht getestet, aber ich würde erwarten, dass sehr viel dies als Regex schneller sein, abgesehen davon, dass viel, viel schöner zu lesen.

Also im Grunde ich einfach total verschwendet meine Zeit mit Regexes Hantieren. Vergeuden Sie nicht Ihre Zeit, suchen Sie nach einfachen String-Methoden zuerst, bevor man auf regex!

Answer 3

Auf die Gefahr von Downvoted bekommen, werde ich reguläre Ausdrücke deuten darauf hin, nicht mit dieser Situation umgehen soll.

Sie können ein Zeichen oder eine Reihe von Zeichen übereinstimmen, aber man kann es nicht haben erinnern, welche Zeichen eines Satzes bereits gefunden worden, die aus weiteren Spiel ausgeschlossen werden sollen.

Ich schlage vor, Sie einen Zeichensatz beibehalten, können Sie es zurücksetzen, bevor Sie mit einer neuen Zeile beginnen, und Sie es Elemente hinzufügen, während über die Linie gehen. Sobald die Anzahl der Elemente in dem Satz 3 überschreitet, fallen Sie die aktuelle Zeile und gehen Sie zum nächsten.

Answer 4

für mich -. Als Programmierer mit fair genug regulären Ausdruck Wissen klingt dies nicht ein Problem wie die Sie Regexp mit solve kann nur

wahrscheinlicher, benötigen Sie einen Hashmap / Array-Datenstruktur Schlüssel bauen: Zeichenwert: zählen und die große Textdatei durchlaufen, für jede Zeile die Karte neu zu erstellen. bei jedem neuen Charakter prüfen, ob die bereits angetroffenen Zeichenzahl 2 ist, wenn ja, aktuelle Zeile überspringen.

aber im scharfen überrascht werden, wenn man verrückt regexp Hacker mit einer Lösung kommen wird.