Regex para todas las palabras de 10 letras, con letras únicas

23

Estoy tratando de escribir una expresión regular que muestre todas las palabras que tengan 10 caracteres de longitud, y ninguna de las letras se repita.

Hasta ahora, tengo

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

Cuál es la primera parte de la pregunta. ¿Cómo haría para verificar la "singularidad"? Realmente no tengo ni idea, aparte de eso necesito usar referencias anteriores.

Dylan Meeus
fuente
1
Esto debe hacerse con una expresión regular?
Hauke ​​Laging
Estoy practicando regex, así que preferiblemente sí :)
Dylan Meeus
3
No creo que pueda hacer esto con una expresión regular de estilo informático: lo que desea requiere "memoria" de lo que son los caracteres coincidentes anteriores, y las expresiones regulares simplemente no tienen eso. Dicho esto, es posible que pueda hacerlo con referencias anteriores y las cosas de expresión no regular que puede hacer la coincidencia de estilo PCRE.
Bruce Ediger
3
@BruceEdiger siempre que haya un número finito de caracteres en el idioma (26) y letras en la cadena (10), es bastante posible hacerlo. Son solo muchos estados, pero nada que lo convierta en un idioma normal.
1
¿Quieres decir "Todas las palabras en inglés ..."? ¿Quiere incluir aquellos deletreados con guiones y apóstrofes o no (suegros, no)? ¿Quieres incluir palabras como café, ingenuo, fachada?
hippietrail

Respuestas:

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

excluye palabras que tienen dos caracteres idénticos.

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

excluye los que tienen caracteres repetidos.

POSIXY:

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

trcoloca las palabras en su propia línea al convertir cualquier ssecuencia de caracteres que no sean palabras ( ccomplemento de alfanumérico y guión bajo) en un carácter de nueva línea.

O con uno grep:

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

(excluya líneas de menos de 10 y más de 10 caracteres y aquellas con un carácter que aparezca al menos dos veces).

Con uno grepsolo (GNU grep con soporte PCRE o pcregrep):

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

Es decir, un límite de palabra ( \b) seguido de una secuencia de 10 caracteres de palabra (siempre que cada uno no sea seguido por una secuencia de caracteres de palabra y ellos mismos, utilizando el operador PCRE de vista previa negativo (?!...)).

Tenemos suerte de que funcione aquí, ya que no muchos motores regexp funcionan con referencias inversas dentro de las partes repetidas.

Tenga en cuenta que (con mi versión de GNU grep al menos)

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

No funciona pero

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

does (as echo aa | grep -Pw '(.)\2') que suena como un error.

Es posible que desee:

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

si desea \wo \bconsiderar cualquier letra como un componente de palabra y no solo las ASCII en configuraciones regionales no ASCII.

Otra alternativa:

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

Ese es un límite de palabras (uno que no es seguido por una secuencia de caracteres de palabras, una de las cuales se repite) seguido de 10 caracteres de palabras.

Cosas que posiblemente tenga en mente:

  • La comparación Babylonishdistingue entre mayúsculas y minúsculas, por lo que, por ejemplo, coincidiría, ya que todos los caracteres son diferentes a pesar de que hay dos Bs, una minúscula y una mayúscula (use -ipara cambiar eso).
  • para -w, \wy \b, una palabra es una letra (ASCII solo para GNU grep por ahora , la [:alpha:]clase de caracteres en su localidad si usa -Py (*UCP)), dígitos decimales o guiones bajos .
  • eso significa que c'est(dos palabras según la definición francesa de una palabra) o it's(una palabra según algunas definiciones inglesas de una palabra) o rendez-vous(una palabra según la definición francesa de una palabra) no se consideran una palabra.
  • Incluso con (*UCP), los caracteres de combinación Unicode no se consideran componentes de palabras, por lo que téléphone( $'t\u00e9le\u0301phone') se considera como 10 caracteres, uno de los cuales no es alfa. défavorisé( $'d\u00e9favorise\u0301') coincidiría aunque tenga dos éporque son 10 caracteres alfabéticos diferentes seguidos de una combinación de acento agudo (no alfa, por lo que hay un límite de palabras entre el ey su acento).
Stéphane Chazelas
fuente
1
Increíble. \waunque no coincide -.
Graeme
@Stephane ¿Puedes publicar una breve explicación de las últimas dos expresiones?
mkc
A veces parece que las búsquedas son la solución a todas las cosas que solían ser imposibles con RE.
Barmar
1
@Barmar siguen siendo imposibles con las expresiones regulares. Una "Expresión regular" es una construcción matemática que solo permite explícitamente ciertas construcciones, a saber, caracteres literales, clases de caracteres y los operadores '|', '(...)', '?', '+' Y '*'. Cualquier llamada "expresión regular" que utiliza un operador que no es uno de los anteriores no es en realidad una expresión regular.
Jules
1
@Jules Esto es unix.stackexchange.com, no math.stackexchange.com. Los RE matemáticos son irrelevantes en este contexto, estamos hablando de los tipos de RE que usa con grep, PCRE, etc.
Barmar
12

De acuerdo ... aquí está la manera torpe para una cadena de cinco caracteres:

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

Debido a que no puede poner una referencia inversa en una clase de caracteres (por ejemplo [^\1|\2]), debe usar una vista previa negativa - (?!foo). Esta es una función PCRE, por lo que necesita el -Pinterruptor.

El patrón para una cadena de 10 caracteres será mucho más largo, por supuesto, pero hay un método más corto que usa una coincidencia de longitud variable ('. *') En la búsqueda anticipada:

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

Después de leer la respuesta esclarecedora de Stephane Chazelas, me di cuenta de que hay un patrón simple similar para esto que se puede usar a través del -vinterruptor de grep :

    (.).*\1

Dado que la verificación continúa un carácter a la vez, esto verá si algún carácter seguido es seguido por cero o más caracteres ( .*) y luego una coincidencia para la referencia inversa. -vinvierte, imprime solo cosas que no coinciden con este patrón Esto hace que las referencias posteriores sean más útiles, ya que no se pueden negar con una clase de caracteres y significativamente:

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

funcionará para identificar una cadena de cualquier longitud con caracteres únicos, mientras que:

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

no lo hará, ya que coincidirá con cualquier sufijo con caracteres únicos (por ejemplo, abcabccoincide por abcel final y aaaapor ael final, por lo tanto, cualquier cadena). Esta es una complicación causada por las miradas de ancho cero (no consumen nada).

encerrada dorada
fuente
¡Bien hecho! Sin embargo, esto solo funcionará en combinación con el de la Q.
Graeme
1
Creo que puede simplificar el primero si su motor regex permite anticipación negativa de longitud variable:(.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!\4).
Christopher Creutzig
@ChristopherCreutzig: Absolutamente, buena llamada. He añadido eso.
Ricitos
6

Si no necesita hacer todo en regex, lo haría en dos pasos: primero haga coincidir todas las palabras de 10 letras, luego filtrelas por su singularidad. La forma más corta que sé cómo hacer esto es en Perl:

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

Tenga en cuenta las \Wanclas adicionales para asegurarse de que solo las palabras que tengan exactamente 10 caracteres de longitud coincidan.

Joseph R.
fuente
Gracias, pero me gustaría como un regex oneliner :)
Dylan Meeus
4

Otros han sugerido que esto no es posible sin varias extensiones a ciertos sistemas de expresión regular que de hecho no son regulares. Sin embargo, dado que el idioma que desea hacer coincidir es finito, es claramente regular. Para 3 letras de un alfabeto de 4 letras, sería fácil:

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

Obviamente, esto se sale de control con más letras y alfabetos más grandes. :-)

R ..
fuente
Tuve que votar esto porque en realidad es una respuesta que funcionaría. Aunque en realidad podría ser la forma menos eficiente que alguien haya escrito regex: P
Dylan Meeus
4

La opción --perl-regexp(breve -P) de GNU greputiliza expresiones regulares más potentes que incluyen patrones de anticipación. El siguiente patrón busca cada letra que esta letra no aparece en el resto de la palabra:

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

Sin embargo, el comportamiento en tiempo de ejecución es bastante malo, ya que \w*puede tener una longitud casi infinita. Puede limitarse a \w{,8}, pero eso también verifica más allá del límite de palabras de 10 letras. Por lo tanto, el siguiente patrón primero verifica la longitud de palabra correcta:

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

Como archivo de prueba, he usado un archivo grande de ≈ 500 MB:

  • Primer patrón: ≈ 43 s
  • Último patrón: ≈ 15 s

Actualizar:

No pude encontrar un cambio significativo en el comportamiento en tiempo de ejecución para un operador no codicioso ( \w*?) o un operador posesivo ( (...){10}+). Un poco más rápido parece el reemplazo de la opción -w:

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

Una actualización de grep de la versión 2.13 a 2.18 fue mucho más efectiva. El archivo de prueba solo tomó ≈ 6 s.

Heiko Oberdiek
fuente
El rendimiento dependerá mucho de la naturaleza de los datos. Al hacer pruebas en la mía, descubrí que el uso de operadores no codiciosos ( \w{,8}?) ayudó para algún tipo de entrada (aunque no de manera muy significativa). Buen uso de \g{-1}para evitar el error grep de GNU.
Stéphane Chazelas
@StephaneChazelas: Gracias por los comentarios. También probé operadores no codiciosos y posesivos y no encontré un cambio significativo en el comportamiento del tiempo de ejecución (versión 2.13). La versión 2.18 es mucho más rápida y pude ver al menos una pequeña mejora. El error grep de GNU está presente en ambas versiones. De todos modos, prefiero la referencia relativa \g{-1}, porque hace que el patrón sea más independiente de la ubicación. De esta forma, se puede usar como parte de un patrón más grande.
Heiko Oberdiek
0

Una solución de Perl:

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

pero no funciona con

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

o

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

probado con perl v5.14.2 y v5.18.2


fuente
El primero y el tercero no hacen nada, el segundo genera cualquier línea de 10 o más caracteres, con no más de 2 espacios consecutivos. pastebin.com/eEDcy02D
manatwork
Es probablemente la versión perl. probado con v5.14.2 y v5.18.2
Los probé con v5.14.1 en Linux y v5.14.2 en Cygwin. Ambos se comportaron como en la muestra de pastebin que vinculé anteriormente.
manatwork
la primera línea me funciona con las versiones destacadas de perl. los dos últimos deberían funcionar, porque son los mismos re, pero no lo hicieron. Tenga en cuenta a menudo que algunas expresiones codiciosas son altamente experimentales.
Probado de nuevo con tus últimas actualizaciones. Solo el segundo sale correctamente. (Sin embargo, la palabra debe estar solo en una línea, mientras que la pregunta es acerca de palabras coincidentes, no líneas enteras.)
manatwork