En RegEx, ¿cómo encuentra una línea que no contenga más de 3 caracteres únicos?

Question

Estoy recorriendo un archivo de texto grande y busco líneas que no contengan más de 3 caracteres diferentes (sin embargo, esos caracteres pueden repetirse indefinidamente). Supongo que la mejor manera de hacer esto sería algún tipo de expresión regular.

Se agradece toda la ayuda.

(Estoy escribiendo el script en PHP, si eso ayuda)

Answer 1

Quizás esto funcione:

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

Explicación:

/
 ^                 #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
/

Un beneficio adicional, $ coincide [1], [2], [3] contendrá los tres caracteres que desee. La expresión regular busca el primer carácter, luego lo almacena y lo empareja hasta que se encuentra algo diferente a ese carácter, lo atrapa como un segundo carácter, coincide con cualquiera de esos caracteres tantas veces como sea posible, atrapa el tercer carácter y coincide con los tres hasta que la coincidencia falla o la cadena termina y la prueba pasa.

EDIT

Esta expresión regular será mucho más rápida debido a la forma en que funciona el motor de análisis y el retroceso, lea la respuesta de bobince para la explicación:

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

Answer 2

Regex optimización ejercicio divertido tiempo para niños! Tomando la expresión regular de gnarf como punto de partida:

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

Noté que había * s anidados y secuenciales aquí, lo que puede causar mucho retroceso. Por ejemplo, en 'abcaaax' intentará hacer coincidir la última cadena de 'a' como un solo \ 1 * de longitud 3, un \ 1 * de longitud dos seguido de un solo \ 1, a \ 1 seguido de un 2 de longitud \ 1 *, o tres \ 1s de una sola coincidencia. Ese problema empeora mucho cuando tienes cadenas más largas, especialmente cuando debido a la expresión regular no hay nada que impida que \ 1 sea el mismo carácter que \ 2.

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

Esto fue más del doble de rápido que el original, probando en el emparejador PCRE de Python. (Es más rápido que configurarlo en PHP, lo siento).

Esto todavía tiene un problema porque (.)? no puede coincidir con nada y luego continuar con el resto de la coincidencia. \ 1 | \ 2 seguirá coincidiendo con \ 1 incluso si no hay \ 2 para coincidir, lo que puede dar lugar a un posible retroceso al intentar introducir el \ 1 | \ 2 y \ 1 | \ 2 | \ 3 cláusulas anteriores cuando no pueden dar lugar a una coincidencia. Esto se puede resolver moviendo la opcionalidad ? alrededor de todas las cláusulas finales:

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

Esto fue dos veces más rápido nuevamente.

Todavía existe un problema potencial en el sentido de que cualquiera de \ 1, \ 2 y \ 3 puede ser el mismo carácter, lo que puede causar más retroceso cuando la expresión no coincide. Esto lo detendría al usar un lookahead negativo para no coincidir con un carácter anterior:

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

Sin embargo, en Python con mis datos de prueba aleatorios no noté una aceleración significativa de esto. Su kilometraje puede variar en PHP dependiendo de los datos de prueba, pero ya puede ser lo suficientemente bueno. La coincidencia posesiva (* +) podría haber ayudado si estuviera disponible aquí.

Ninguna expresión regular se desempeñó mejor que la alternativa Python más fácil de leer:

len(set(s))<=3

El método análogo en PHP probablemente sería con count_chars :

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

No he probado la velocidad, pero espero que sea más rápido que la expresión regular, además de ser mucho, mucho más agradable de leer.

Entonces, básicamente, perdí totalmente mi tiempo jugando con expresiones regulares. ¡No pierdas tu tiempo, busca métodos de cadena simples antes de recurrir a la expresión regular!

Answer 3

A riesgo de ser rechazado, sugeriré que las expresiones regulares no están destinadas a manejar esta situación.

Puede hacer coincidir un carácter o un conjunto de caracteres, pero no puede hacer que recuerde qué caracteres de un conjunto ya se han encontrado para excluirlos de una coincidencia posterior.

Te sugiero que mantengas un conjunto de caracteres, lo reinicies antes de comenzar con una nueva línea y agregues elementos al pasar por la línea. Tan pronto como el recuento de elementos en el conjunto excede 3, suelta la línea actual y pasa a la siguiente.

Answer 4

para mí: como programador con un conocimiento de expresión regular bastante adecuado, esto no parece un problema que pueda resolver utilizando Regexp únicamente.

es más probable que necesite construir una clave de estructura de datos hashMap / array: valor de carácter: cuente e itere el archivo de texto grande, reconstruyendo el mapa para cada línea. en cada nuevo carácter verifique si el recuento de caracteres ya encontrado es 2, en caso afirmativo, omita la línea actual.

pero estoy ansioso por ser sorprendido si un hacker loco regexp encontrará una solución.