Generando la expresión regular más corta para que coincida con una lista de palabras arbitraria

Question

Espero que alguien sepa de una secuencia de comandos que puede tomar una lista de palabras arbitraria y generó la expresión regular más corta que podría coincidir exactamente (y nada más).

Por ejemplo, supongamos que mi lista es

1231 
1233 
1234 
1236 
1238 
1247 
1256 
1258 
1259 

A continuación, la salida debe ser:

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

Answer 1

Usted es probablemente mejor de ahorro de toda la lista, o si usted desea conseguir la suposición, cree un Trie:

1231 
1234 
1247 

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

Ahora cuando se toma una comprobación de cadenas si alcanza un nodo de hoja. Lo hace, es válido.

Si tiene cadenas superpuestas de longitud variable (por ejemplo, 123 y 1234) necesitará marcar algunos nodos como posibles terminales.

---

También puede utilizar el trie para generar la expresión regular si realmente te gusta la idea de expresiones regulares:

1. nodos desde la raíz hasta la primera ramificación son fijos (por ejemplo: 12)

2. Ramas crean |: (por ejemplo: 12(3|4)

3. Los nodos hoja generan un carácter c Lass (o carácter individual) que sigue al nodo padre: (por ejemplo 12(3[14]|47))

esto podría no generar la expresión regular más corto, para hacer que se le podría algún trabajo extra:

1. " compacto" rangos de si los encuentra (por ejemplo [12345] convierte [1-4])

2. Añadir cuantificadores de elementos repetidos (por ejemplo: [1234][1234] convierte [1234]{2}

3. ???

Realmente no creo que valga la pena generar la expresión regular.

Answer 2

Esto es lo que se me ocurrió (JavaScript). Convirtió una lista de 20,000 números de 6 dígitos en una expresión regular de 60,000 caracteres. Comparado con una construcción ingenua (word1 | word2 | ...), eso es casi un 60% de "compresión" por cantidad de caracteres.

Dejo la pregunta abierta, ya que aún hay mucho margen de mejora y estoy esperando que haya una herramienta mejor.

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()); 

Usando

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

Aquí está la salida:

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

Answer 3

Este proyecto genera una expresión regular de una lista de palabras dadas: https://github.com/bwagner/wordhierarchy

Casi hace lo mismo que el above JavaScript solution, pero evita ciertos paréntesis superfluos. Solo utiliza "|", el grupo que no captura "(?:)" y la opción "?". Hay margen de mejora cuando hay una fila de caracteres individuales: En lugar de p. Ej. (?:3|8|1|6|4) podría generar [38164].

La expresión regular generada podría adaptarse fácilmente a otros dialectos de expresiones regulares.

Ejemplo de uso:

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

Esta es una entrada antigua, pero en beneficio de los mismos que encuentra a través de búsquedas en la web como lo hice, no es un módulo de Perl que hace esto, llamado Regexp::Optimizer, aquí: http://search.cpan.org/~dankogai/Regexp-Optimizer-0.23/lib/Regexp/Optimizer.pm

Toma una expresión regular como entrada, que puede consistir simplemente en la lista de cadenas de entrada separadas con |, y genera una expresión regular óptima.

Por ejemplo, este comando de la línea de Perl:

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

genera esta salida:

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

(suponiendo que haya instalado Regex::Optimizer), que coincide con las expectativas de la OP bastante bien.

He aquí otro ejemplo:

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

Y la salida:

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

Por comparación, una versión basada en trie óptima sería la salida 3(14|24|34|574|84). En la salida anterior, también puede buscar y reemplazar (?: y (?^: con sólo ( y eliminar paréntesis redundantes, para obtener esto:

3([1238]|57)4