generación de la secuencia con expresiones regulares como criterios

Question

Me pregunto carnero es factible implementar una reunión óptima Clase generador de cadena de los siguientes requisitos del segundo pensamiento:

---

• criterios de generación utilizando regex
• Lexicographical order enumeración .
• Conde propetry
• acceso indexado

no me siento cómodo con expresiones regulares: no puedo subir con una pieza de partida de código, sino que sólo piensa de una implementación ingenua usando un TList como una clase base y usar un filtro (Regex) contra una cadena generada por "fuerza bruta".

¿Cuáles son las otras alternativas óptimas?

---

• Orden: En primer lugar por la longitud (más corta primero), entonces lexicográficamente.
• Especificación del rango de caracteres que se utilizarán en la generación: todas las combinaciones imprimibles o posibles de [A-Z], [a-z], números, símbolos especiales y eventualmente espacio (¿expresiones regulares?).
• Longitud de cadena limitada con un mínimo/máximo determinado.
• espacio de búsqueda restringida con límites: (? Expresiones regulares) Iniciar cadena de una cadena End, con posibilidad de filtrado

---

Última edición

Para empezar, reformuló la cabecera usando regex como en lugar de regex.

Estoy considerando a revisar el primer requisito ya que es una puerta abierta que puede conducir a problema intratable.

Necesito sugerencias y ayuda para la redacción correcta.

Segunda necesidad de pensamiento editar. Todavía abierto a la sugerencia de refinamiento.

Answer 1

me gustaría hacer esto mediante la construcción del mínimo Deterministic Finite Automaton para el idioma.Si está empezando con una expresión regular, esto se puede hacer automáticamente mediante la construcción de Thompson seguida de la construcción del subconjunto y la minimización. Ver this description por ejemplo.

Con un DFA en la mano, se puede usar algo como esto algoritmo:

Let P = { < START, [""] > } be a set of pairs <State, list of strings> 
for n = 0, 1, ... Max 
    Let P' = {} be a new set 
    while P is not empty 
    Remove the pair <s, L> from P 
    For each transition s -- c --> t in alpha order of c 
     if t is an accepting state, 
      output l + c for each string l in L 
     put <t, L + c> in P' (** i.e. append c to each string in L) 
    end 
    Set P = P' 
end 

Tenga en cuenta que el paso marcado ** necesidades para ser verdad inserción del equipo, como duplicados pueden surgir fácilmente.

Este es un algoritmo central. P puede crecer exponencialmente con la longitud de salida, pero este es solo el precio de rastrear todas las posibilidades para una cadena de salida futura. Las restricciones de orden/tamaño/espacio que mencionó pueden garantizarse manteniendo el orden ordenado en las listas L y cortando la búsqueda cuando se alcanzan los límites de recursos.

Editar

Aquí está un ejemplo de Java juguete donde he duro codificado para la DFA simples literales de punto flotante binario con signo menos opcional. Esto utiliza un esquema ligeramente diferente al pseudocódigo anterior para obtener un orden de salida ordenado estricto y acomodar rangos de caracteres.

import java.util.Comparator; 
import java.util.TreeSet; 

public class Test{ 

    public static class DFA { 

     public static class Transition { 

      final int to; 
      final char lo, hi; // Character range. 

      public Transition(int to, char lo, char hi) { 
       this.to = to; 
       this.lo = lo; 
       this.hi = hi; 
      } 

      public Transition(int to, char ch) { 
       this(to, ch, ch); 
      } 
     } 

     // transitions[i] is a vector of transitions from state i. 
     final Transition [] [] transitions; 

     // accepting[i] is true iff state i is accepting 
     final boolean [] accepting; 

     // Make a fresh immutable DFA. 
     public DFA(Transition [] [] transitions, boolean [] accepting) { 
      this.transitions = transitions; 
      this.accepting = accepting; 
     } 

     // A pair is a DFA state number and the input string read to get there. 
     private static class Pair { 
      final int at; 
      final String s; 

      Pair(int at, String s) { 
       this.at = at; 
       this.s = s; 
      } 
     } 

     // Compare pairs ignoring `at` states, since 
     // they are equal iff the strings are equal. 
     private Comparator<Pair> emitOrder = new Comparator<Pair>() { 
      @Override 
      public int compare(Pair a, Pair b) { 
       return a.s.compareTo(b.s); 
      } 
     }; 

     // Emit all strings accepted by the DFA of given max length. 
     // Output is in sorted order. 
     void emit(int maxLength) { 
      TreeSet<Pair> pairs = new TreeSet<Pair>(emitOrder); 
      pairs.add(new Pair(0, "")); 
      for (int len = 0; len <= maxLength; ++len) { 
       TreeSet<Pair> newPairs = new TreeSet<Pair>(emitOrder); 
       while (!pairs.isEmpty()) { 
        Pair pair = pairs.pollFirst(); 
        for (Transition x : transitions[pair.at]) { 
         for (char ch = x.lo; ch <= x.hi; ch++) { 
          String s = pair.s + ch; 
          if (newPairs.add(new Pair(x.to, s)) && accepting[x.to]) { 
           System.out.println(s); 
          } 
         } 
        } 
       } 
       pairs = newPairs; 
      } 
     } 
    } 

    // Emit with a little DFA for floating point numbers. 
    public void run() { 
     DFA.Transition [] [] transitions = { 
      { // From 0 
       new DFA.Transition(1, '-'), 
       new DFA.Transition(2, '.'), 
       new DFA.Transition(3, '0', '1'), 
      }, 
      { // From 1 
       new DFA.Transition(2, '.'), 
       new DFA.Transition(3, '0', '1'), 
      }, 
      { // From 2 
       new DFA.Transition(4, '0', '1'), 
      }, 
      { // From 3 
       new DFA.Transition(3, '0', '1'), 
       new DFA.Transition(4, '.'), 
      }, 
      { // From 4 
       new DFA.Transition(4, '0', '1'), 
      } 
     }; 
     boolean [] accepting = { false, false, false, true, true }; 
     new DFA(transitions, accepting).emit(4); 
    } 

    public static void main (String [] args) { 
     new Test().run(); 
    } 
} 

Answer 2

vieja pregunta, pero nadie ha respondido, la recompensa sigue activo y ya tengo una solución preparada, así que aquí es una respuesta posible:

una vez me escribió una little program que hace esto.Sin embargo, es en C++/Qt (aunque escribo casi todos mis programas en Delphi, que uno se encuentra en C++), no es compatible con Unicode y no hace ninguna orden garantiza

Funciona de la siguiente manera:

1. Todo? {} + * |() los operadores se expanden (hasta un límite máximo), de modo que solo quedan las clases de caracteres y las referencias posteriores.

   p. Ej. [a-c]+|t*|([x-z]){2}foo\1|(a|b)(t|u) se convierte en [a-c]|[a-c][a-c]|[a-c][a-c][a-c]|[a-c][a-c][a-c][a-c]||t|tt|tt|ttt|ttt|([x-z][x-z])foo\1|at|au|bt|bu

   (el | en esta última expresión son sólo notación, el programa guarda cada subregex alternativa en una lista)

2. referencias hacia atrás a varios caracteres se sustituyen por referencias hacia atrás a caracteres individuales.

   p. Ej. la expresión anterior se convierte en [a-c]|[a-c][a-c]|[a-c][a-c][a-c]|[a-c][a-c][a-c][a-c]||t|tt|tt|ttt|ttt|([x-z])([x-z])foo\1\2|at|au|bt|bu

   Ahora cada subregio alternativo corresponde a una cadena de longitud fija.

3. Para cada una de las alternativas, se imprimen todas las combinaciones de recoger personajes de las clases:

   por ejemplo la expresión anterior se convierte en a|b|c|aa|ba|..|cc|aaa|baa|...|ccc|aaaa|...|cccc||t|tt|tt|ttt|ttt|xxfooxx|yxfooyx|...|zzfoozz|at|au|bt|bu

Probablemente puede añadir garantías de orden shortlex de la siguiente manera:

1. Ordenar los personajes de las clases alfabéticamente

2. Ordenar las alternativas obtenidas en la etapa 2 arriba para longitud

   (hay muchos alternan tantes, pero por lo general su recuento es insignificante en comparación con el recuento de cadenas resultantes)

3. Ordenar/cambio de las clases de personajes y referencias hacia atrás, de modo que cada punto de referencia hacia atrás

4. enumerar las posibles cadenas de una sola fijo la alternativa de longitud como antes, pero comienza en la última clase de caracteres, en lugar de la primera para obtener un orden alfabético.

   (esto no funciona, si había alguna referencias hacia atrás apuntando hacia delante)

5. Si hay varias alternativas de la misma longitud, enumerarlos en "paralelo", compara sus cadenas actuales e imprimir el alfabéticamente más bajo . (es decir, combine las listas ya ordenadas para cada alternativa.)

   Esto se puede optimizar, p. mediante la detección de prefijos distintos y clases de caracteres seguros en el sufijo que se pueden enumerar sin afectar el orden. (Por ejemplo, un [a-z] | B [a-z] tiene prefijos distintos y la [a-z] se pueden enumerar sin ningún tipo de comparaciones)