Regulärer Ausdruck, um eine Zeile zu finden, die kein Wort enthält

Question

Ich weiß, dass es möglich ist, ein Wort abzugleichen und dann die Übereinstimmungen mit anderen Tools umzukehren (z. B. grep -v). Ist es jedoch möglich, Zeilen abzugleichen, die kein bestimmtes Wort enthalten, z. B. hede, unter Verwendung eines regulären Ausdrucks?

Eingabe:

hoho
hihi
haha
hede

Code:

grep "" input

Gewünschte Ausgabe:

hoho
hihi
haha

Answer 1

Da niemand sonst eine direkte Antwort auf die gestellte Frage gegeben hat, werde ich es tun.

Die Antwort lautet, dass es mit POSIX grep unmöglich ist, dieses Anfrage wortwörtlich zu erfüllen:

grep "" Eingabe

Der Grund dafür ist, dass POSIX grep ohne Flags nur mit Grundlegende Reguläre Ausdrücke (BREs) arbeiten muss, die einfach nicht leistungsstark genug sind, um diese Aufgabe zu erfüllen, aufgrund des Mangels an Alternation in Teilausdrücken. Die einzige Art von Alternation, die es unterstützt, beinhaltet das Bereitstellen mehrerer regulärer Ausdrücke, die durch Zeilenumbrüche getrennt sind, und das deckt nicht alle regulären Sprachen ab, z.B. es gibt keine endliche Sammlung von BREs, die dieselbe reguläre Sprache wie der erweiterte Reguläre Ausdruck (ERE) ^(ab|cd)*$ abbilden.

Allerdings implementiert GNU grep Erweiterungen, die es ermöglichen. Insbesondere ist \| der Alternationsoperator in der GNU-Implementierung von BREs. Wenn Ihr regulärer Ausdrucksmotor Alternation, Klammern und den Kleene-Stern unterstützt und an den Anfang und das Ende des Strings verankern kann, dann ist das alles, was Sie für diesen Ansatz benötigen. Beachten Sie jedoch, dass negative Mengen [^ ... ] sehr praktisch sind, zusätzlich zu denen, denn ansonsten müssen Sie sie durch einen Ausdruck der Form (a|b|c| ... ) ersetzen, der jeden nicht im Satz enthaltenen Buchstaben auflistet, was äußerst mühsam und übermäßig langwierig ist, insbesondere wenn der gesamte Zeichensatz Unicode ist.

Dank der formalen Sprachtheorie sehen wir, wie ein solcher Ausdruck aussieht. Mit GNU grep wäre die Antwort etwas wie:

grep "^\([^h]\|h\(h\|eh\|edh\)*\([^eh]\|e[^dh]\|ed[^eh]\)\)*\(\|h\(h\|eh\|edh\)*\(\|e\|ed\)\)$" Eingabe

(gefunden mit Grail und einigen weiteren Optimierungen von Hand gemacht).

Sie können auch ein Tool verwenden, das EREs implementiert, wie z.B. egrep, um die Backslashes loszuwerden, oder alternativ das -E Flag an POSIX grep übergeben (obwohl ich den Eindruck hatte, dass die Frage erforderte, jegliche Flags an grep zu vermeiden):

egrep "^([^h]|h(h|eh|edh)*([^eh]|e[^dh]|ed[^eh]))*(|h(h|eh|edh)*(|e|ed))$" Eingabe

Hier ist ein Skript, um es zu testen (beachten Sie, dass es eine Datei testinput.txt im aktuellen Verzeichnis generiert). Mehrere der Ausdrücke, die in anderen Antworten präsentiert wurden, fallen bei diesem Test durch.

#!/bin/bash
REGEX="^\([^h]\|h\(h\|eh\|edh\)*\([^eh]\|e[^dh]\|ed[^eh]\)\)*\(\|h\(h\|eh\|edh\)*\(\|e\|ed\)\)$"

# Die ersten vier Zeilen sind wie im Ursprungsfall.
cat > testinput.txt <

``

In meinem System gibt es aus:

Dateien /dev/fd/63 und /dev/fd/62 sind identisch

wie erwartet.

Für diejenigen, die sich für die Details interessieren, besteht die Technik darin, den regulären Ausdruck, der das Wort abgleicht, in einen endlichen Automaten umzuwandeln, dann den Automaten umzukehren, indem jeder Akzeptanzzustand in Nicht-Akzeptanz und umgekehrt geändert wird, und dann den resultierenden FA wieder in einen regulären Ausdruck umzuwandeln.

Wie von allen bemerkt wurde, ist der reguläre Ausdruck wesentlich einfacher, wenn Ihr regulärer Ausdrucksmotor Negative Lookaheads unterstützt. Zum Beispiel mit GNU grep:

grep -P '^((?!hede).)*$' Eingabe

Dieser Ansatz hat jedoch den Nachteil, dass er einen regelbasierten regulären Ausdrucksmotor erfordert. Dies macht ihn in Installationen ungeeignet, die sichere reguläre Ausdrucksmotoren wie RE2 verwenden, was ein Grund ist, den generierten Ansatz in bestimmten Situationen vorzuziehen.

Unter Verwendung von Kendall Hopkins' hervorragender FormalTheory Bibliothek, die in PHP geschrieben ist und eine Funktionalität ähnlich wie Grail bietet, und einem von mir geschriebenen Vereinfacher, konnte ich einen Online-Generator für negative reguläre Ausdrücke erstellen, basierend auf einer Eingabephase (nur alphanumerische und Leerzeichenzeichen werden derzeit unterstützt, und die Länge ist begrenzt): http://www.formauri.es/personal/pgimeno/misc/non-match-regex/

Für hede gibt es als Ausgabe:

^([^h]|h(h|e(h|dh))*([^eh]|e([^dh]|d[^eh])))*(h(h|e(h|dh))*(ed?)?)?$

das äquivalent zu dem oben genannten ist.

``

Answer 2

Nicht Regex, aber ich habe es logisch und nützlich gefunden, serielle Greps mit Pipe zu verwenden, um Störgeräusche zu eliminieren.

Zum Beispiel, suchen Sie eine Apache-Konfigurationsdatei ohne alle Kommentare-

grep -v '\#' /opt/lampp/etc/httpd.conf      # gibt alle Zeilen ohne Kommentar aus

und

grep -v '\#' /opt/lampp/etc/httpd.conf |  grep -i dir

Die Logik der seriellen Greps ist (kein Kommentar) und (passt zu dir)

Answer 3

Mit diesem Ansatz vermeiden Sie es, einen Ausblick an jeder Position zu testen:

/^(?:[^h]+|h++(?!ede))*+$/

entspricht (für .net):

^(?>(?:[^h]+|h+(?!ede))*)$

Alte Antwort:

/^(?>[^h]+|h+(?!ede))*$/

Answer 4

Das oben genannte (?:(?!hede).)* ist großartig, weil es verankert werden kann.

^(?:(?!hede).)*$               # Eine Zeile ohne hede

foo(?:(?!hede).)*bar           # foo gefolgt von bar, ohne hede dazwischen

Aber das Folgende würde in diesem Fall ausreichen:

^(?!.*hede)                    # Eine Zeile ohne hede

Diese Vereinfachung ist bereit, "UND"-Klauseln hinzuzufügen:

^(?!.*hede)(?=.*foo)(?=.*bar)   # Eine Zeile mit foo und bar, aber ohne hede
^(?!.*hede)(?=.*foo).*bar       # Das Gleiche

Answer 5

Eine meiner Meinung nach lesbarere Variante der Top-Antwort:

^(?!.*hede)

Grundsätzlich bedeutet dies "Übereinstimmen am Anfang der Zeile, wenn und nur wenn es kein 'hede' darin gibt" - die Anforderung wurde also fast direkt in Regex übersetzt.

Natürlich ist es möglich, mehrere Fehleranforderungen zu haben:

^(?!.*(hede|hodo|hada))

Details: Das ^ Anker stellt sicher, dass der Regex-Engine nicht versucht, die Übereinstimmung an jeder Position im String erneut zu finden, was zu einer Übereinstimmung bei jedem String führen würde.

Der ^ Anker am Anfang soll den Anfang der Zeile darstellen. Das grep-Tool überprüft jede Zeile nacheinander, in Kontexten, in denen mit einem mehrzeiligen String gearbeitet wird, kann die "m" Flagge verwendet werden:

/^(?!.*hede)/m # JavaScript-Syntax

oder

(?m)^(?!.*hede) # Inline-Flagge