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

Question

Je parcours un gros fichier texte et je recherche des lignes qui ne contiennent pas plus de 3 caractères différents (ces caractères peuvent cependant être répétés indéfiniment). Je suppose que le meilleur moyen de le faire serait une sorte d'expression régulière.

Toute aide est appréciée.

(Je vous écris le script en PHP, si cela aide)

Answer 1

Peut-être que ceci fonctionne:

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

Explaination:

/ 
^     #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 ajouté benifit, $matches[1], [2], [3] contiendra les trois caractères que vous voulez. L'expression régulière cherche le premier caractère, puis le stocke et l'associe jusqu'à ce que quelque chose d'autre que ce personnage soit trouvé, l'attrape en tant que second caractère, correspondant autant de fois que possible à ces caractères, attrape le troisième caractère, et correspond tous les trois jusqu'à ce que la correspondance échoue ou la chaîne se termine et le test passe.

EDIT

Cette expression rationnelle sera beaucoup plus rapide en raison de la façon dont le moteur d'analyse et de travaux de traçage, lisez la réponse de bobince pour l'explication:

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

Answer 2

Au risque de se downvoted, je suggère des expressions régulières ne sont pas destinées à gérer cette situation.

Vous pouvez faire correspondre un caractère ou un ensemble de caractères, mais vous ne pouvez pas vous souvenir des caractères d'un ensemble qui ont déjà été trouvés pour exclure ceux d'une autre correspondance. Je suggère que vous mainteniez un jeu de caractères, vous le réinitialisiez avant de commencer avec une nouvelle ligne, et vous y ajoutez des éléments en dépassant la ligne. Dès que le nombre d'éléments dans l'ensemble dépasse 3, vous déposez la ligne actuelle et passez à la suivante.

Answer 3

pour moi - en tant que programmeur avec juste -en dépit de la connaissance de l'expression régulière, cela ne ressemble pas à un problème que vous pouvez résoudre en utilisant Regexp uniquement. Il est plus probable que vous ayez besoin de construire une clé de structure de données hashMap/array: valeur de caractère: comptez et itérez le fichier texte volumineux, en reconstruisant la carte pour chaque ligne. à chaque nouveau caractère, vérifiez si le nombre de caractères déjà rencontré est 2, si c'est le cas, ignorez la ligne en cours.

mais je ne veux pas être surpris si un hacker regexp fou trouve une solution.

Answer 4

Optimisation Regex amusant exercice pour les enfants! Prendre regex de Gnarf comme point de départ:

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

Je remarqué qu'il y * ont été imbriquées et séquentiels s ici, ce qui peut causer beaucoup de retours en arrière. Par exemple, dans 'abcaaax', il essayera de faire correspondre cette dernière chaîne de 'a's comme un simple \ 1 * de longueur 3, un \ 1 * de longueur deux suivi d'un seul \ 1, un \ 1 suivi d'un 2-longueur \ 1 *, ou trois simples \ 1s. Ce problème s'aggrave lorsque vous avez des chaînes plus longues, surtout quand, à cause de la regex, il n'y a rien qui empêche \ 1 d'être le même caractère que \ 2.

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

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

Cela pose toujours un problème car (.)? ne peut rien trouver, et continue avec le reste du match. \1|\2 correspondra toujours à \ 1 même s'il n'y a pas de \ 2 à faire correspondre, ce qui entraînera un retour arrière potentiel en essayant d'introduire les clauses \1|\2 et \1|\2|\3 plus tôt lorsqu'elles ne peuvent pas aboutir à une correspondance. Ceci peut être résolu en déplaçant le ? optionalness autour de l'ensemble des clauses de suivi:

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

C'était deux fois plus vite à nouveau.

Il existe toujours un problème potentiel en ce que l'un des caractères \ 1, \ 2 et \ 3 peut être le même caractère, ce qui peut provoquer plus de retour arrière lorsque l'expression ne correspond pas. Cela arrêterait en utilisant un négatif pour correspondre préanalyse pas 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éatoire, je ne l'ai pas remarqué une importante accélération de cette situation. Votre kilométrage peut varier en PHP en fonction des données de test, mais cela pourrait déjà être suffisant. Possessive-matching (* +) aurait pu aider si c'était disponible ici.

Aucun regex meilleurs résultats que le plus facile à lire autre Python:

len(set(s))<=3 

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

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

Je ne l'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 tout mon temps à jouer avec les regex. Ne perdez pas votre temps, cherchez d'abord des méthodes de cordes simples avant de recourir à regex!