Regex für alle 10-Buchstaben-Wörter mit eindeutigen Buchstaben

23

Ich versuche, einen regulären Ausdruck zu schreiben, in dem alle Wörter mit einer Länge von 10 Zeichen angezeigt werden und keiner der Buchstaben wiederholt wird.

Bisher habe ich bekommen

grep --colour -Eow '(\w{10})'

Welches ist der allererste Teil der Frage. Wie würde ich nach der "Einzigartigkeit" suchen? Ich habe wirklich keine Ahnung, ansonsten muss ich Rückverweise verwenden.

Dylan Meeus
quelle
1
Das muss mit einem Regex gemacht werden?
Hauke ​​Laging
Ich übe Regex, also vorzugsweise ja :)
Dylan Meeus
3
Ich glaube nicht, dass Sie dies mit einem regulären Ausdruck im Informatikstil tun können: Was Sie wollen, erfordert eine "Erinnerung" an die vorhergehenden übereinstimmenden Zeichen, und reguläre Ausdrücke haben das einfach nicht. Das heißt, Sie sind möglicherweise in der Lage, dies mit Rückverweisen und den nicht regulären Ausdrücken zu tun, die der PCRE-ähnliche Abgleich bewirken kann.
Bruce Ediger
3
@BruceEdiger Solange die Sprache (26) eine endliche Anzahl von Zeichen und die Zeichenfolge (10) Buchstaben enthält, ist dies durchaus möglich. Es sind nur eine Menge Staaten, aber nichts, was es zu keiner regulären Sprache machen würde.
1
Meinen Sie "Alle englischen Wörter ..."? Wollen Sie die mit Bindestrichen und Apostrophen geschriebenen einschließen oder nicht (Schwiegereltern, nicht)? Meinen Sie, um Wörter wie Café, naiv, Fassade einzuschließen?
Hippietrail

Antworten:

41
grep -Eow '\w{10}' | grep -v '\(.\).*\1'

schließt Wörter mit zwei identischen Zeichen aus.

grep -Eow '\w{10}' | grep -v '\(.\)\1'

schließt diejenigen aus, die sich wiederholende Zeichen haben.

POSIXly:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -xE '.{10}' |
   grep -v '\(.\).*\1'

trsFügt Wörter in eine eigene Zeile ein, indem alle Gleichungen von Nicht-Wort-Zeichen ( cAuslassung von alphanumerischen Zeichen und Unterstrichen) in Zeilenumbrüche umgewandelt werden.

Oder mit einem grep:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -ve '^.\{0,9\}$' -e '.\{11\}' -e '\(.\).*\1'

(Ausgenommen sind Zeilen mit weniger als 10 und mehr als 10 Zeichen sowie Zeilen mit mindestens zweimal vorkommenden Zeichen.)

Mit grepnur einem (GNU grep mit PCRE-Unterstützung oder pcregrep):

grep -Po '\b(?:(\w)(?!\w*\1)){10}\b'

Das heißt, eine Wortgrenze ( \b) gefolgt von einer Folge von 10 Wortzeichen (vorausgesetzt, auf jedes folgt keine Folge von Wortzeichen und sich selbst, unter Verwendung des negativen Look-Ahead-PCRE-Operators (?!...)).

Wir sind froh, dass es hier funktioniert, da nicht viele reguläre Ausdrücke mit Rückverweisen in sich wiederholenden Teilen arbeiten.

Beachten Sie, dass (mit meiner Version von GNU grep mindestens)

grep -Pow '(?:(\w)(?!\w*\1)){10}'

Funktioniert nicht, aber

grep -Pow '(?:(\w)(?!\w*\2)){10}'

does (as echo aa | grep -Pw '(.)\2') was wie ein Bug klingt.

Du möchtest vielleicht:

grep -Po '(*UCP)\b(?:(\w)(?!\w*\1)){10}\b'

wenn Sie wollen , \woder einen \bbeliebigen Buchstaben als Wortbestandteil zu betrachten und nicht nur die ASCII diejenigen in Nicht-ASCII - locales.

Eine andere Alternative:

grep -Po '\b(?!\w*(\w)\w*\1)\w{10}\b'

Dies ist eine Wortgrenze (eine, auf die keine Folge von Wortzeichen folgt, von denen sich eines wiederholt), gefolgt von 10 Wortzeichen.

Dinge, die man möglicherweise im Hinterkopf haben sollte:

  • Der Vergleich unterscheidet zwischen Groß- und Kleinschreibung, so dass Babylonishzum Beispiel eine Übereinstimmung erzielt wird, da alle Zeichen unterschiedlich sind, obwohl es zwei Bs gibt, einen Kleinbuchstaben und einen Großbuchstaben ( -izum Ändern verwenden).
  • für -w, \wund \b, ist ein Wort , einen Buchstabe (ASCII diejenigen nur für GNU grep für jetzt , die [:alpha:]Zeichenklasse in Ihrem Gebietsschema bei Verwendung von -Pund (*UCP)), Dezimalstellen oder Unterstrich .
  • das bedeutet, dass c'est(zwei Wörter gemäß der französischen Definition eines Wortes) oder it's(ein Wort gemäß einigen englischen Definitionen eines Wortes) oder rendez-vous(ein Wort gemäß der französischen Definition eines Wortes) nicht als ein Wort betrachtet werden.
  • Auch (*UCP)wenn Unicode-Kombinationszeichen nicht als Wortbestandteile betrachtet werden, wird téléphone( $'t\u00e9le\u0301phone') als 10 Zeichen betrachtet, von denen eines kein Alpha ist. défavorisé( $'d\u00e9favorise\u0301') würde übereinstimmen, obwohl es zwei éZeichen hat, da dies 10 verschiedene Alpha-Zeichen sind, gefolgt von einem kombinierten Akzent (kein Alpha, daher gibt es eine Wortgrenze zwischen dem eund seinem Akzent).
Stéphane Chazelas
quelle
1
Genial. \wstimmt aber nicht überein -.
Graeme
@Stephane Kannst du eine kurze Erklärung der letzten beiden Ausdrücke posten?
MKC
Manchmal scheinen Lookarounds die Lösung für all die Dinge zu sein, die früher mit RE unmöglich waren.
Barmar
1
@Barmar Mit regulären Ausdrücken sind sie immer noch unmöglich. Ein "regulärer Ausdruck" ist ein mathematisches Konstrukt, das explizit nur bestimmte Konstrukte zulässt, nämlich Literalzeichen, Zeichenklassen und die Operatoren "|", "(...)", "?", "+" Und "*". Ein sogenannter "regulärer Ausdruck", der einen Operator verwendet, der keiner der oben genannten ist, ist eigentlich kein regulärer Ausdruck.
Jules
1
@Jules Dies ist unix.stackexchange.com, nicht math.stackexchange.com. Die mathematischen REs sind in diesem Zusammenhang irrelevant. Wir sprechen über die Arten von REs, die Sie mit grep, PCRE usw. verwenden.
Barmar
12

Okay ... hier ist der umständliche Weg für eine fünfstellige Zeichenfolge:

grep -P '^(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)(?!\1|\2|\3|\4).$'

Weil Sie keinen Rückverweis in einer Zeichenklasse (zB setzen kann [^\1|\2]), müssen Sie ein verwenden negativen Vorgriff - (?!foo). Dies ist eine PCRE-Funktion, daher benötigen Sie den -PSchalter.

Das Muster für eine 10-stellige Zeichenfolge ist natürlich viel länger, aber es gibt eine kürzere Methode, bei der eine Variable verwendet wird, die mit ". *" Im Lookahead übereinstimmt:

grep -P '^(.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!.*\4)(.)(?!.*\5).$'

Nachdem ich Stephane Chazelas 'aufschlussreiche Antwort gelesen hatte, stellte ich fest, dass es für diese Funktion ein ähnliches einfaches Muster gibt, das über greps -vSchalter verwendet werden kann:

    (.).*\1

Da die Prüfung jeweils um ein Zeichen fortgesetzt wird, wird geprüft, ob auf ein bestimmtes Zeichen null oder mehr Zeichen ( .*) folgen, und anschließend wird eine Übereinstimmung für die Rückreferenz gefunden. -vinvertiert und druckt nur Dinge, die diesem Muster nicht entsprechen. Dies macht die Rückverweise nützlicher, da sie nicht mit einer Zeichenklasse negiert werden können.

grep -v '\(.\).*\1'

wird arbeiten, um eine Zeichenfolge beliebiger Länge mit eindeutigen Zeichen zu identifizieren, wobei:

grep -P '(.)(?!.*\1)'

wird nicht, da es jedes Suffix mit eindeutigen Zeichen abgleichen wird (z. B. abcabcpasst wegen abcam Ende und aaaawegen aam Ende - daher jede Zeichenfolge). Dies ist eine Komplikation, die durch Lookarounds mit der Breite Null verursacht wird (sie verbrauchen nichts).

Goldlöckchen
quelle
Gut gemacht! Dies funktioniert jedoch nur in Kombination mit dem im Q.
Graeme
1
Ich glaube, Sie können die erste vereinfachen, wenn Ihre Regex-Engine eine negative Vorschau mit variabler Länge zulässt:(.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!\4).
Christopher Creutzig
@ChristopherCreutzig: Absolut netter Anruf. Ich habe das hinzugefügt.
Goldlöckchen
6

Wenn Sie das Ganze nicht in Regex erledigen müssen, würde ich es in zwei Schritten erledigen: Zuerst alle 10-Buchstaben-Wörter abgleichen und dann nach Eindeutigkeit filtern. Der kürzeste Weg, wie ich das machen kann, ist in Perl:

perl -nle 'MATCH:while(/\W(\w{10})\W/g){
             undef %seen;
             for(split//,$1){next MATCH if ++$seen{$_} > 1}
             print
           }' your_file

Beachten Sie die zusätzlichen \WAnker, um sicherzustellen, dass nur Wörter mit einer Länge von genau 10 Zeichen übereinstimmen.

Joseph R.
quelle
Vielen Dank, aber ich möchte es als Regex-Oneliner :)
Dylan Meeus
4

Andere haben vorgeschlagen, dass dies ohne verschiedene Erweiterungen bestimmter regulärer Expressionssysteme, die tatsächlich nicht regulär sind, nicht möglich ist. Da die gewünschte Sprache jedoch endlich ist, ist sie eindeutig regelmäßig. Für 3 Buchstaben aus einem 4-Buchstaben-Alphabet wäre es einfach:

(abc|abd|acb|acd|bac|bad|bcd|bdc|cab|cad|cbd|cdb|dab|dac|dbc|dcb)

Offensichtlich gerät dies mit mehr Buchstaben und größeren Buchstaben in Eile außer Kontrolle. :-)

R ..
quelle
Ich musste dem zustimmen, weil es tatsächlich eine Antwort ist, die funktionieren würde. Obwohl es vielleicht die am wenigsten effiziente Art und Weise ist, wie jemals jemand Regex geschrieben hat: P
Dylan Meeus
4

Option --perl-regexp(short -P) von GNU grepverwendet leistungsfähigere reguläre Ausdrücke, die Vorausschau-Muster enthalten. Das folgende Muster sucht nach jedem Buchstaben, den dieser Buchstabe im Rest des Wortes nicht enthält:

grep -Pow '((\w)(?!\w*\g{-1})){10}'

Das Laufzeitverhalten ist jedoch ziemlich schlecht, da \w*es eine nahezu unendliche Länge haben kann. Es kann begrenzt werden \w{,8}, aber das prüft auch über das Wortlimit von 10 Buchstaben. Daher überprüft das folgende Muster zuerst die korrekte Wortlänge:

grep -Pow '(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}'

Als Testdatei habe ich eine große ≈ 500 MB-Datei verwendet:

  • Erstes Muster: ≈ 43 s
  • Letztes Muster: ≈ 15 s

Aktualisieren:

Ich konnte keine signifikante Änderung im Laufzeitverhalten für einen nicht gierigen Operator ( \w*?) oder einen besitzergreifenden Operator ( (...){10}+) finden. Ein kleines bisschen schneller scheint die Alternative zu sein -w:

grep -Po '\b(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}\b'

Ein Update von grep von Version 2.13 auf 2.18 war viel effektiver. Die Testdatei dauerte nur ca. 6 s.

Heiko Oberdiek
quelle
Die Leistung hängt stark von der Art der Daten ab. Bei meinen Tests stellte ich fest, dass die Verwendung von nicht gierigen Operatoren ( \w{,8}?) für eine Art von Eingabe hilfreich war (wenn auch nicht sehr bedeutend). Gute Verwendung \g{-1}, um den GNU-Grep-Bug zu umgehen.
Stéphane Chazelas
@StephaneChazelas: Danke für das Feedback. Ich hatte auch nicht gierige und besitzergreifende Operatoren ausprobiert und habe keine signifikante Änderung im Laufzeitverhalten (Version 2.13) gefunden. Version 2.18 ist viel schneller und ich konnte zumindest eine kleine Verbesserung feststellen. Der GNU-Grep-Bug ist in beiden Versionen vorhanden. Auf jeden Fall bevorzuge ich den relativen Bezug \g{-1}, weil dadurch das Muster von der Position unabhängiger wird. In dieser Form kann es als Teil eines größeren Musters verwendet werden.
Heiko Oberdiek
0

Eine Perl-Lösung:

perl -lne 'print if (!/(.)(?=$1)/g && /^\w{10}$/)' file

aber es funktioniert nicht mit

perl -lne 'print if (!/(.)(?=\1)/g && /^\w{10}$/)' file

oder

perl -lne 'print if ( /(.)(?!$1)/g && /^\w{10}$/)' file

getestet mit perl v5.14.2 und v5.18.2


quelle
Die erste und dritte Zeile tun nichts, die zweite Zeile gibt eine Zeile mit 10 oder mehr Zeichen aus, wobei nicht mehr als 2 aufeinanderfolgende Leerzeichen verwendet werden dürfen. pastebin.com/eEDcy02D
Manatwork
Es ist wahrscheinlich die Perl-Version. Getestet mit v5.14.2 und v5.18.2
Ich habe sie mit v5.14.1 unter Linux und v5.14.2 unter Cygwin ausprobiert. Beide haben sich wie im Pastebin-Beispiel verhalten, das ich zuvor verlinkt habe.
Manatwork
Die erste Zeile funktioniert für mich mit den angegebenen Versionen von Perl. die beiden letzteren sollten funktionieren, da sie gleich sind, aber nicht. Ich stelle oft fest, dass einige gierige Ausdrücke sehr experimentell sind.
Erneut mit Ihren neuesten Updates getestet. Nur der 2. gibt richtig aus. (Das Wort muss jedoch allein in einer Zeile stehen, während es sich um übereinstimmende Wörter und nicht um ganze Zeilen handelt.)
manatwork