Dans RegEx, comment trouvez-vous une ligne qui ne contient pas plus de 3 caractères uniques?

Question

Je parcours en boucle un fichier texte volumineux et je recherche des lignes ne contenant pas plus de 3 caractères différents (ces caractères peuvent toutefois être répétés indéfiniment). Je suppose que la meilleure façon de procéder serait une sorte d’expression régulière.

Toute aide est appréciée.

(J'écris le script en PHP, si cela peut vous aider)

Answer 1

Cela fonctionnera peut-être:

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

Explication:

/
 ^                 #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 avantage supplémentaire, $ match [1], [2], [3] contiendra les trois caractères souhaités. L’expression régulière recherche le premier caractère, puis le stocke et la fait correspondre jusqu’à ce qu’elle soit trouvée, attrape celui-ci en tant que deuxième caractère, correspondant à l’un ou l’autre de ces caractères autant de fois que possible, capture le troisième caractère et fait correspondre les trois jusqu'à ce que la correspondance échoue ou que la chaîne se termine et que le test soit réussi.

MODIFIER

Cette expression rationnelle sera beaucoup plus rapide en raison du fonctionnement du moteur d'analyse syntaxique et du retour arrière, lisez la réponse de bobince pour l'explication suivante:

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

Answer 2

Optimisation Regex: un exercice amusant pour les enfants! En prenant la regex de gnarf comme point de départ:

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

J'ai remarqué qu'il y avait des * imbriqués et séquentiels ici, ce qui peut causer beaucoup de retours en arrière. Par exemple, dans 'abcaaax', il essaiera de faire correspondre la dernière chaîne de 'a' sous la forme d'un seul \ 1 * de longueur 3, un \ 1 * de longueur deux suivi d'un seul \ 1, un \ 1 suivi d'un 2-longueur \ 1 * ou trois \ 1 à une seule correspondance. Ce problème s’aggrave beaucoup lorsque vous avez de longues chaînes, en particulier lorsque rien n’empêche \ 1 d’être le même caractère que \ 2.

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

Cela a été deux fois plus rapide que l'original, à tester sur le matcher PCRE de Python. (C'est plus rapide que de l'installer en PHP, désolé.)

Cela a toujours un problème en ce que (.)? ne peut correspondre à rien, puis continue avec le reste de la correspondance. \ 1 | \ 2 correspondra toujours à \ 1 même s'il n'y a pas de correspondance avec \ 2, ce qui risque de provoquer un retour en arrière tentant d'introduire le \ 1 | \ 2 et le \ 1 | \ 2 | \ 3 plus tôt lorsqu'elles ne peuvent pas donner lieu à une correspondance. Cela peut être résolu en déplaçant l'option ? autour de l'ensemble des clauses de fin:

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

C'était encore deux fois plus vite.

Il existe toujours un problème potentiel: l'un des \ 1, \ 2 et \ 3 peut être le même caractère, ce qui peut entraîner davantage de retours en arrière lorsque l'expression ne correspond pas. Cela l'arrêterait en utilisant une anticipation négative pour ne pas faire correspondre un caractère précédent:

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

Cependant, en Python avec mes données de test aléatoires, je n’ai pas remarqué une accélération significative de cette situation. Votre kilométrage peut varier en PHP en fonction des données de test, mais il pourrait déjà être suffisant. Une correspondance possessive (* +) aurait peut-être été utile si cela était disponible ici.

Aucune expression rationnelle n'a donné de meilleurs résultats que l'alternative Python plus facile à lire:

len(set(s))<=3

La méthode analogue en PHP serait probablement avec count_chars :

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

Je n'ai pas testé la vitesse, mais je m'attendrais beaucoup à ce que ce soit plus rapide que regex, en plus d'être beaucoup, beaucoup plus agréable à lire.

Donc fondamentalement, je viens de perdre totalement mon temps à jouer avec les regex. Ne perdez pas votre temps, cherchez d’abord des méthodes de chaîne simples avant de recourir à regex!

Answer 3

Au risque d’être victime d’un vote négatif, je suggérerai que les expressions régulières ne soient pas conçues pour gérer cette situation.

Vous pouvez faire correspondre un caractère ou un ensemble de caractères, mais vous ne pouvez pas lui rappeler quels caractères d'un ensemble ont déjà été trouvés pour exclure ceux d'une correspondance ultérieure.

Je vous suggère de conserver un jeu de caractères, de le réinitialiser avant de commencer avec une nouvelle ligne et d'y ajouter des éléments en le parcourant. Dès que le nombre d'éléments dans l'ensemble dépasse 3, vous supprimez la ligne en cours et passez à la suivante.

Answer 4

Pour moi, en tant que programmeur possédant une connaissance assez bonne de l’expression régulière, cela ne ressemble pas à un problème que vous pouvez résoudre en utilisant uniquement Regexp.

Plus probablement, vous aurez besoin de construire une clé de structure de données hashMap / array: caractère valeur: compter et itérer le fichier texte volumineux, reconstruisant la carte pour chaque ligne. à chaque nouveau caractère, vérifiez si le nombre de caractères déjà rencontré est égal à 2, si tel est le cas, ignorez la ligne actuelle.

mais je souhaite être surpris si un pirate informatique expert en expressions rationnelles parvient à une solution.