In RegEx, come si trova una riga che non contiene più di 3 caratteri univoci?

Question

Sto cercando un file di testo di grandi dimensioni e sto cercando linee che non contengano più di 3 caratteri diversi (questi caratteri, tuttavia, possono essere ripetuti indefinitamente). Presumo che il modo migliore per farlo sia una sorta di espressione regolare.

Tutto l'aiuto è apprezzato.

(Sto scrivendo la sceneggiatura in PHP, se questo aiuta)

Answer 1

Forse questo funzionerà:

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

Spiegazione:

/
 ^                 #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 benifit aggiunto, $ match [1], [2], [3] conterrà i tre caratteri desiderati. L'espressione regolare cerca il primo carattere, quindi lo memorizza e lo abbina fino a quando non viene trovato qualcosa di diverso da quel personaggio, lo rileva come secondo carattere, abbinando uno di quei personaggi quante più volte possibile, cattura il terzo carattere e corrisponde a tutti e tre fino a quando la corrispondenza ha esito negativo o la stringa termina e il test ha esito positivo.

Modifica

Questa regexp sarà molto più veloce a causa del funzionamento del motore di analisi e del backtracking, leggi la risposta di Bobince per la spiegazione:

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

Answer 2

Esercizio di divertimento per l'ottimizzazione Regex per i bambini! Prendendo la regex di gnarf come punto di partenza:

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

Ho notato che c'erano nidificati e sequenziali * s qui, che possono causare molti backtracking. Ad esempio in 'abcaaax' proverà a far corrispondere l'ultima stringa di 'a's come un singolo \ 1 * di lunghezza 3, un \ 1 * di lunghezza due seguito da un singolo \ 1, a \ 1 seguito da un 2-lunghezza \ 1 * o tre single-match \ 1s. Questo problema peggiora molto quando hai stringhe più lunghe, specialmente quando a causa della regex non c'è nulla che impedisce a \ 1 di avere lo stesso carattere di \ 2.

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

Questo è stato due volte più veloce dell'originale, testato sul matcher PCRE di Python. (È più veloce che configurarlo in PHP, scusa.)

Questo ha ancora un problema in quanto (.)? non può eguagliare nulla, e quindi andare avanti con il resto della partita. \ 1 | \ 2 continuerà a corrispondere a \ 1 anche se non esiste \ 2 da abbinare, con conseguente potenziale backtracking nel tentativo di introdurre \ 1 | \ 2 e \ 1 | \ 2 | \ 3 in precedenza quando non sono in grado di generare una corrispondenza. Ciò può essere risolto spostando il ? facoltativo su tutte le clausole finali:

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

Questo è stato di nuovo due volte più veloce.

Esiste ancora un potenziale problema in quanto uno qualsiasi di \ 1, \ 2 e \ 3 può avere lo stesso carattere, causando potenzialmente più backtracking quando l'espressione non corrisponde. Questo lo fermerebbe usando uno sguardo negativo per non corrispondere a un personaggio precedente:

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

Tuttavia in Python con i miei dati di test casuali non ho notato un significativo aumento di velocità da questo. Il tuo chilometraggio può variare in PHP in base ai dati del test, ma potrebbe essere già abbastanza buono. Possessive-matching (* +) potrebbe essere d'aiuto se questo fosse disponibile qui.

Nessun regex ha funzionato meglio dell'alternativa Python più facile da leggere:

len(set(s))<=3

Il metodo analogo in PHP sarebbe probabilmente con count_chars :

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

Non ho testato la velocità ma mi aspetterei molto che questo sia più veloce di regex, oltre ad essere molto, molto più bello da leggere.

Quindi, in pratica, ho semplicemente sprecato il mio tempo a giocherellare con le regex. Non perdere tempo, cerca i semplici metodi di stringa prima di ricorrere a regex!

Answer 3

A rischio di essere retrocesso, suggerirò che le espressioni regolari non sono pensate per gestire questa situazione.

Puoi abbinare un personaggio o un set di personaggi, ma non puoi fargli ricordare quali personaggi di un set sono già stati trovati per escluderli da ulteriori match.

Ti suggerisco di mantenere un set di caratteri, di ripristinarlo prima di iniziare con una nuova linea e di aggiungere lì elementi mentre si passa sopra la linea. Non appena il conteggio degli elementi nel set supera 3, si rilascia la riga corrente e si passa al successivo.

Answer 4

per me - come programmatore con una conoscenza delle espressioni regolari abbastanza equa, questo non sembra un problema che puoi risolvere usando solo Regexp.

è più probabile che sia necessario creare una chiave per la struttura dei dati hashMap / array: valore carattere: contare e iterare il file di testo di grandi dimensioni, ricostruendo la mappa per ogni riga. ad ogni nuovo personaggio controlla se il conteggio dei personaggi già incontrati è 2, in tal caso, salta la riga corrente.

ma vorrei essere sorpreso se un pazzo hacker regexp troverà una soluzione.