Generazione della regex più breve per abbinare un elenco di parole arbitrarie

Question

Spero che qualcuno possa sapere di uno script che può prendere un elenco di parole arbitrarie e generare la regex più breve che potrebbe corrispondere esattamente a quella lista (e nient'altro).

Ad esempio, supponiamo che la mia lista è

1231 
1233 
1234 
1236 
1238 
1247 
1256 
1258 
1259 

L'uscita dovrebbe essere:

12(3[13468]|47|5[589]) 

Answer 1

si sono probabilmente meglio risparmiare l'intero elenco, o se si vuole ottenere l'immaginazione, creare un Trie:

1231 
1234 
1247 

    1 
    | 
    2 
/\ 
    3 4 
/\ \ 
1 4 7 

Ora, quando si prende un assegno stringa se raggiunge un nodo foglia. Lo fa, è valido.

Se si dispone di stringhe sovrapposte di lunghezza variabile (ad esempio: 123 e 1234) è necessario contrassegnare alcuni nodi come possibilmente un terminale.

---

È inoltre possibile utilizzare il trie per generare la regex se vi piace l'idea regex:

1. nodi dalla radice alla prima ramificazione sono fissi (ad esempio: 12)

2. rami creano |: (ad esempio: 12(3|4)

3. nodi foglia generano un carattere c lass (o singolo carattere) che segue il nodo padre: (es 12(3[14]|47))

questo potrebbe non generare la regex più breve, di fare che ti potrebbe po 'di lavoro in più:

1. " Compact" varia se li trovate (ad esempio [12345] diventa [1-4])

2. Aggiungi quantificatori per gli elementi ripetuti (ad esempio: [1234][1234] diventa [1234]{2}

3. ???

Realmente non penso che valga la pena generare la regex.

Answer 2

Ecco cosa mi è venuto in mente (JavaScript). Ha trasformato una lista di 20.000 numeri a 6 cifre in un'espressione regolare di 60.000 caratteri. Rispetto ad una costruzione ingenua (word1 | word2 | ...), questa è quasi il 60% di "compressione" per numero di caratteri.

Sto lasciando aperta la domanda, poiché c'è ancora molto spazio per migliorare e spero che possa esserci uno strumento migliore.

var list = new listChar(""); 

function listChar(s, p) { 
    this.char = s; 
    this.depth = 0; 
    this.parent = p; 
    this.add = function(n) { 
     if (!this.subList) { 
      this.subList = {}; 
      this.increaseDepth(); 
     } 
     if (!this.subList[n]) { 
      this.subList[n] = new listChar(n, this); 
     } 
     return this.subList[n]; 
    } 
    this.toString = function() { 
     var ret = ""; 
     var subVals = []; 
     if (this.depth >=1) { 
      for (var i in this.subList) { 
       subVals[subVals.length] = this.subList[i].toString(); 
      } 
     } 
     if (this.depth === 1 && subVals.length > 1) { 
      ret = "[" + subVals.join("") + "]"; 
     } else if (this.depth === 1 && subVals.length === 1) { 
      ret = subVals[0]; 
     } else if (this.depth > 1) { 
      ret = "(" + subVals.join("|") + ")"; 
     } 
     return this.char + ret; 
    } 
    this.increaseDepth = function() { 
     this.depth++; 
     if (this.parent) { 
      this.parent.increaseDepth(); 
     } 
    } 
} 

function wordList(input) { 
    var listStep = list; 
    while (input.length > 0) { 
     var c = input.charAt(0); 
     listStep = listStep.add(c); 
     input = input.substring(1); 
    } 
} 
words = [/* WORDS GO HERE*/]; 
for (var i = 0; i < words.length; i++) { 
    wordList(words[i]); 
} 

document.write(list.toString()); 

Utilizzando

words = ["1231","1233","1234","1236","1238","1247","1256","1258","1259"]; 

ecco l'output:

(1(2(3[13468]|47|5[689]))) 

Answer 3

Questo progetto genera un'espressione regolare da una data lista di parole: https://github.com/bwagner/wordhierarchy

E 'quasi fa la stessa cosa come il above JavaScript solution, ma evita alcune parentesi superflue. Utilizza solo "|", gruppo non acquisibile "(?:)" e l'opzione "?". C'è spazio per miglioramenti quando c'è una fila di singoli caratteri: Invece di ad es. (?:3|8|1|6|4) potrebbe generare [38164].

La regexp generata può essere facilmente adattata ad altri dialetti regexp.

utilizzo Esempio:

java -jar dist/wordhierarchy.jar 1231 1233 1234 1236 1238 1247 1256 1258 1259 
-> 12(?:5(?:6|9|8)|47|3(?:3|8|1|6|4)) 

Answer 4

questo è un vecchio post, ma a beneficio di coloro che trovando attraverso ricerche sul Web come ho fatto io, v'è un modulo Perl che fa questo, chiamato Regexp::Optimizer, qui: http://search.cpan.org/~dankogai/Regexp-Optimizer-0.23/lib/Regexp/Optimizer.pm

Prende una espressione regolare come input, che può consistere solo dell'elenco di stringhe di input separate con | e genera un'espressione regolare ottimale.

Ad esempio, questo Perl riga di comando:

perl -mRegexp::Optimizer -e "print Regexp::Optimizer->new->optimize(qr/1231|1233|1234|1236|1238|1247|1256|1258|1259/)" 

genera questo output:

(?^:(?^:12(?:3[13468]|5[689]|47))) 

(ammesso che abbiate installato Regex::Optimizer), che corrisponde aspettativa del PO abbastanza bene.

Ecco un altro esempio:

perl -mRegexp::Optimizer -e "print Regexp::Optimizer->new->optimize(qr/314|324|334|3574|384/)" 

E l'output:

(?^:(?^:3(?:[1238]|57)4)) 

Per confronto, una versione basata su trie ottimale sarebbe uscita 3(14|24|34|574|84). In uscita di cui sopra, è anche possibile cercare e sostituire (?: e (?^: con appena ( ed eliminare parentesi ridondanti, per ottenere questo:

3([1238]|57)4