Buscando algoritmo que invierte el sprintf() función de salida

StackOverflow https://stackoverflow.com/questions/9882

Pregunta

Estoy trabajando en un proyecto que requiere el análisis de archivos de registro.Estoy buscando un algoritmo rápido que llevaría a los grupos de mensajes como este:

La temperatura en el P1 es 35F.

La temperatura en el P1 es 40F.

La temperatura a la P3 es 35F.

Registrador de detenido.

Registrador de empezar.

La temperatura en el P1 es 40F.

y pone algo en la forma de un printf():

"The temperature at P%d is %dF.", Int1, Int2" 
{(1,35), (1, 40), (3, 35), (1,40)}

El algoritmo debe ser lo suficientemente genérico para reconocer casi cualquier carga de datos en el mensaje de los grupos.

He intentado buscar este tipo de tecnología, pero aún no sé los términos correctos para la búsqueda.

¿Fue útil?

Solución

Resumen:

Un ingenuo!! el algoritmo realiza un seguimiento de la frecuencia de las palabras en cada columna manera, donde uno puede asumir que cada línea se puede dividir en columnas con un delimitador.

Ejemplo de entrada:

El perro saltó sobre la luna
El gato saltó sobre la luna
La luna saltó sobre la luna
El coche saltó por encima de la luna

Frecuencias:

Column 1: {The: 4}
Column 2: {car: 1, cat: 1, dog: 1, moon: 1}
Column 3: {jumped: 4}
Column 4: {over: 4}
Column 5: {the: 4}
Column 6: {moon: 4}

Podríamos partición de estas listas de frecuencia más por el agrupamiento basado en el número total de campos, pero en este simple y conveniente ejemplo, estamos trabajando solamente con un número fijo de campos (6).

El siguiente paso es para iterar a través de las líneas que generan estas listas de frecuencia, así que vamos a tomar el primer ejemplo.

  1. El:cumple con una mano-ondulado criterios y el algoritmo decide que debe ser estática.
  2. perro:no parece ser estática basada en el resto de la lista de frecuencia, y por lo tanto debe ser dinámico, en contraposición a texto estático.Nos bucle a través de un par de pre-definidas las expresiones regulares y vienen con /[a-z]+/i.
  3. más:mismo como #1;es estático, por lo que es dejarlo como está.
  4. el:mismo como #1;es estático, por lo que es dejarlo como está.
  5. luna:mismo como #1;es estático, por lo que es dejarlo como está.

Por lo tanto, sólo va a través de la primera línea podemos armar la siguiente expresión regular:

/The ([a-z]+?) jumps over the moon/

Consideraciones:

  • Obviamente uno puede elegir para escanear parte o todo el documento para el primer pase, siempre y cuando uno confía en las listas de frecuencia será suficiente muestreo de la totalidad de los datos.

  • Los falsos positivos pueden llegar a los resultados, y será hasta el algoritmo de filtrado (mano saludando) para proporcionar el mejor umbral entre la estática y dinámica de los campos, o a algunos de post-procesamiento.

  • La idea general es probablemente una buena, pero la ejecución real definitivamente va a opinar sobre la velocidad y la eficiencia de este algoritmo.

Otros consejos

Creo que podría ser vistas y se perdió fscanf() y sscanf().Que son lo opuesto de los fprintf() y sprintf().

Gracias por todos los excelentes sugerencias.Chris, está a la derecha.Estoy buscando una solución genérica para la normalización de cualquier tipo de texto.La solución del problema se reduce a dynmamically búsqueda de patrones en dos o más cadenas de caracteres similares.Casi como la predicción de la siguiente elemento en un conjunto, basado en los dos anteriores:

1:El Everest es 30000 pies de altura

2:K2 es de 28000 metros de altura

= > ¿Cuál es el patrón?=> Respuesta:

[nombre] [número] pies de alto

Ahora el archivo de texto puede tener millones de líneas y miles de patrones.Me gustaría analizar los archivos muy, muy rápido, encontrar los patrones y recoger los conjuntos de datos que están asociados con cada patrón.

Pensé acerca de la creación de algunos de alto nivel semántico hashes para representar los patrones en las cadenas de mensaje.Me gustaría utilizar un tokenizer y dar a cada uno de los tipos de tokens un "peso"específico.A continuación, me gustaría grupo de los hashes y la tasa de su similitud.Una vez que la agrupación se hace me gustaría recoger los conjuntos de datos.

Tenía la esperanza de que no tienes que reinventar la rueda y podría reutilizar algo que ya está ahí.

Klaus

Depende de lo que usted está tratando de hacer, si tu objetivo es generar rápidamente sprintf() de entrada, esto funciona.Si usted está tratando de analizar los datos, tal vez expresiones regulares haría demasiado..

No vas a encontrar una herramienta que se puede tomar simplemente arbitraria de entrada, supongo que lo de los datos a partir de ésta, y producir el resultado que usted desea.Que suena como fuerte de la IA para mí.

La producción de algo como esto, aunque sólo sea para reconocer los números, se pone muy peludo.Por ejemplo, es "123.456" un número o dos?Cómo acerca de este "123,456"?Es "35F" un número decimal y una "F", o sea que es el valor hexadecimal 0x35F?Vas a tener que construir algo que va a analizar en la manera que usted necesita.Usted puede hacer esto con expresiones regulares, o usted puede hacerlo con sscanf, o usted puede hacer de alguna otra forma, pero vas a tener que escribir algo personalizado.

Sin embargo, básica de las expresiones regulares, usted puede hacerlo usted mismo.No será la magia, pero no se que es mucho trabajo.Algo como esto se analizar las líneas que usted está interesado en consolidar (Perl):

my @vals = ();
while (defined(my $line = <>))
{
    if ($line =~ /The temperature at P(\d*) is (\d*)F./)
    {
        push(@vals, "($1,$2)");
    }
}
print "The temperature at P%d is %dF. {";
for (my $i = 0; $i < @vals; $i++)
{
    print $vals[$i];
    if ($i < @vals - 1)
    {
        print ",";
    }
}
print "}\n";

La salida de este isL

The temperature at P%d is %dF. {(1,35),(1,40),(3,35),(1,40)}

Se podría hacer algo similar para cada tipo de línea es necesario analizar.Incluso se podría leer estas expresiones regulares de un archivo, en lugar de la codificación personalizada de cada uno.

No sé de ningún tipo de herramienta para hacer eso.Lo que yo hice cuando tuve un problema similar para resolver estaba tratando de adivinar expresiones regulares para que coincida con las líneas.

I luego se procesan los archivos y sólo se muestra el inigualable líneas.Si una línea es incomparable, significa que el patrón está mal y debe ser ajustado o de otro patrón debe ser añadido.

Después de alrededor de una hora de trabajo, he logrado encontrar el ~20 patrones para que coincida con 10000+ líneas.

En su caso, en primer lugar puede "adivinar" que un patrón es la "The temperature at P[1-3] is [0-9]{2}F.".Si se vuelve a procesar el archivo de la eliminación de cualquier igualado línea, deja "solo":

Registrador de detenido.

Registrador de empezar.

Que a continuación, puede coincidir con "Logger (.+).".

Usted puede refinar los patrones y buscar otros nuevos para que coincida con su registro entero.

@Juan:Creo que la pregunta se refiere a un algoritmo que realmente reconoce patrones en archivos de registro y automáticamente se "supone" apropiado cadenas de formato y datos de él.El *scanf la familia no puede hacerlo por su propia cuenta, sólo puede ser de ayuda una vez que los patrones han sido reconocidos en el primer lugar.

@Derek Parque:Así, incluso un fuerte AI no podía estar seguro de que tenía la respuesta correcta.

Tal vez algunos de compresión-como mecanismo podría ser utilizado:

  1. Encontrar grandes, frecuentes subcadenas
  2. Encontrar grandes, frecuentes subcadena patrones.(es decir,[patrón:1] [basura] [patrón:2])

Otro elemento a tener en cuenta podría ser el grupo de líneas por edición de distancia.La agrupación de líneas similares deberían dividir el problema en un patrón por el grupo de fragmentos.

En realidad, si te las arreglas para escribir esto, deje que todo el mundo se entere, Creo que muchos de nosotros nos gustaría que esta herramienta!

@Anders

Así, incluso un fuerte AI no podía estar seguro de que tenía la respuesta correcta.

Yo estaba pensando en que es lo suficientemente fuerte AI podría generalmente averiguar la respuesta correcta a partir del contexto.por ejemplo,Fuerte de la IA podría reconocer que "35F" en este contexto es la temperatura y no un número hexadecimal.Definitivamente, hay casos donde incluso fuerte de la IA sería incapaz de responder.Esos son los casos donde un humano sería incapaz de responder, a pesar de que (suponiendo que muy fuerte de la IA).

Por supuesto, realmente no importa, ya que no tenemos fuerte de la IA.:)

http://www.logparser.com reenvía a un IIS en el foro de que parece bastante activa.Este es el sitio oficial de Gabriele Josefinos del "Analizador de Registro de herramientas".Aunque nunca he utilizado este instrumento, me hizo recoger una copia barata de el libro de Amazon Marketplace - hoy una copia es tan bajo como $16.Nada mejor que un muerto-árbol-interfaz para sólo pasar las páginas.

Echando un vistazo a este foro, yo no había oído hablar de la "Nueva interfaz gráfica de usuario de la herramienta de MS de Registro de Analizador, Analizador de Registro Lagarto" en http://www.lizardl.com/.

La cuestión fundamental del curso es la complejidad de su GRAMÁTICA.El uso de cualquier tipo de registro-analizador como el término es comúnmente utilizado, usted necesita saber exactamente lo que va a escanear para, usted puede escribir una BNF para él.Hace muchos años hice un curso basado en el Aho-y-Ullman Dragón "Libro", y el bien entendido LALR la tecnología puede dar una velocidad óptima, siempre por supuesto que usted tiene que CFG.

Por otro lado parece que usted posiblemente alcanzar algo AI-like, que es de un orden diferente de complejidad en su totalidad.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top