Alla ricerca di un algoritmo che inverta l'output della funzione sprintf()

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

Domanda

Sto lavorando a un progetto che richiede l'analisi dei file di registro.Sto cercando un algoritmo veloce che accetti messaggi di gruppo come questo:

La temperatura a P1 è 35F.

La temperatura a P1 è 40F.

La temperatura a P3 è 35F.

Il registratore si è fermato.

Il registratore è stato avviato.

La temperatura a P1 è 40F.

e genera qualcosa sotto forma di printf():

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

L'algoritmo deve essere sufficientemente generico da riconoscere quasi tutti i carichi di dati nei gruppi di messaggi.

Ho provato a cercare questo tipo di tecnologia, ma non conosco nemmeno i termini corretti da cercare.

È stato utile?

Soluzione

Panoramica:

UN ingenuo!! L'algoritmo tiene traccia della frequenza delle parole per colonna, dove si può presumere che ogni riga possa essere separata in colonne con un delimitatore.

Ingresso di esempio:

Il cane ha saltato al settimo cielo
Il gatto ha saltato sulla luna
La luna saltò sopra la luna
L'auto ha fatto un salto al settimo cielo

Frequenze:

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}

Potremmo suddividere ulteriormente queste liste di frequenza raggruppandole in base al numero totale di campi, ma in questo esempio semplice e conveniente stiamo lavorando solo con un numero fisso di campi (6).

Il prossimo passo è scorrere le righe che hanno generato questi elenchi di frequenze, quindi prendiamo il primo esempio.

  1. IL:soddisfa alcuni criteri ondulati della mano e l'algoritmo decide che deve essere statico.
  2. cane:non sembra essere statico in base al resto dell'elenco di frequenze e quindi deve essere dinamico rispetto al testo statico.Esaminiamo alcune espressioni regolari predefinite e arriviamo a /[a-z]+/i.
  3. Sopra:stesso accordo del n. 1;è statico, quindi lascialo così com'è.
  4. IL:stesso accordo del n. 1;è statico, quindi lascialo così com'è.
  5. luna:stesso accordo del n. 1;è statico, quindi lascialo così com'è.

Pertanto, semplicemente esaminando la prima riga possiamo mettere insieme la seguente espressione regolare:

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

Considerazioni:

  • Ovviamente si può scegliere di scansionare parte o l'intero documento per il primo passaggio, purché si sia certi che le liste di frequenza costituiranno un campionamento sufficiente dell'intero dato.

  • Falsi positivi possono insinuarsi nei risultati e spetterà all'algoritmo di filtraggio (agitazione della mano) fornire la migliore soglia tra campi statici e dinamici, o qualche post-elaborazione umana.

  • L’idea generale è probabilmente buona, ma l’effettiva implementazione peserà sicuramente sulla velocità e sull’efficienza di questo algoritmo.

Altri suggerimenti

Penso che potresti trascurare e perdere fscanf() e sscanf().Che sono l'opposto di fprintf() e sprintf().

Grazie per gli ottimi suggerimenti.Chris, ha ragione.Sto cercando una soluzione generica per normalizzare qualsiasi tipo di testo.La soluzione del problema si riduce a trovare dinamicamente modelli in due o più stringhe simili.Quasi come prevedere l'elemento successivo di un set, in base ai due precedenti:

1:L'Everest è alto 30.000 piedi

2:Il K2 è alto 28.000 piedi

=> Qual è lo schema?=> Risposta:

[nome] è alto [numero] piedi

Ora il file di testo può contenere milioni di righe e migliaia di motivi.Vorrei analizzare i file molto, molto velocemente, trovare i modelli e raccogliere i set di dati associati a ciascun modello.

Ho pensato di creare alcuni hash semantici di alto livello per rappresentare i modelli nelle stringhe dei messaggi.Vorrei utilizzare un tokenizzatore e assegnare a ciascuno dei tipi di token un "peso" specifico.Quindi raggrupperei gli hash e valuterei la loro somiglianza.Una volta terminato il raggruppamento, raccoglierei i set di dati.

Speravo di non dover reinventare la ruota e di poter riutilizzare qualcosa che è già disponibile.

Klaus

Dipende da cosa stai cercando di fare, se il tuo obiettivo è generare rapidamente input sprintf(), funziona.Se stai cercando di analizzare i dati, forse andrebbero bene anche le espressioni regolari.

Non troverai uno strumento che possa semplicemente ricevere input arbitrari, indovinare quali dati desideri da esso e produrre l'output desiderato.Mi sembra un'intelligenza artificiale forte.

Produrre qualcosa del genere, anche solo per riconoscere i numeri, diventa davvero complicato.Ad esempio, "123.456" è uno o due numeri?Che ne dici di questo "123.456"?"35F" è un numero decimale e una "F" o è il valore esadecimale 0x35F?Dovrai costruire qualcosa che analizzerà nel modo di cui hai bisogno.Puoi farlo con le espressioni regolari oppure puoi farlo con sscanf, oppure puoi farlo in un altro modo, ma dovrai scrivere qualcosa di personalizzato.

Tuttavia, con le espressioni regolari di base, puoi farlo da solo.Non sarà magia, ma non è tanto lavoro.Qualcosa di simile analizzerà le righe che ti interessano e le consoliderà (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";

L'output di questo èL

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

Potresti fare qualcosa di simile per ogni tipo di linea che devi analizzare.Potresti anche leggere queste espressioni regolari da un file, invece di codificarle individualmente.

Non conosco nessuno strumento specifico per farlo.Ciò che ho fatto quando ho avuto un problema simile da risolvere è stato provare a indovinare le espressioni regolari per far corrispondere le righe.

Ho quindi elaborato i file e visualizzato solo le righe senza corrispondenze.Se una linea non corrisponde, significa che il modello è sbagliato e deve essere modificato o deve essere aggiunto un altro modello.

Dopo circa un'ora di lavoro, sono riuscito a trovare circa 20 modelli che corrispondessero a oltre 10.000 righe.

Nel tuo caso, puoi prima "indovinare" quale modello è "The temperature at P[1-3] is [0-9]{2}F.".Se rielaborate il file rimuovendo qualsiasi riga corrispondente, lascia "solo":

Il registratore si è fermato.

Il registratore è stato avviato.

Con cui puoi poi abbinarlo "Logger (.+).".

È quindi possibile perfezionare i modelli e trovarne di nuovi da abbinare all'intero registro.

@John:Penso che la domanda si riferisca a un algoritmo che riconosce effettivamente i modelli nei file di registro e "indovina" automaticamente le stringhe di formato e i dati appropriati.IL *scanf la famiglia non può farlo da sola, può essere d'aiuto solo una volta che i modelli sono stati riconosciuti in primo luogo.

@Derek Park:Ebbene, anche un'intelligenza artificiale forte non poteva essere sicura di avere la risposta giusta.

Forse potrebbe essere utilizzato un meccanismo simile alla compressione:

  1. Trova sottostringhe grandi e frequenti
  2. Trova modelli di sottostringhe grandi e frequenti.(cioè.[modello:1] [spazzatura] [modello:2])

Un altro elemento da considerare potrebbe essere quello di raggruppare le linee in base a modifica-distanza.Raggruppare linee simili dovrebbe dividere il problema in blocchi di un modello per gruppo.

In realtà, se riesci a scrivere questo, farlo sapere al mondo intero, Penso che molti di noi vorrebbero questo strumento!

@Anders

Ebbene, anche un'intelligenza artificiale forte non poteva essere sicura di avere la risposta giusta.

Pensavo che un'intelligenza artificiale sufficientemente forte potesse farlo Generalmente capire la risposta giusta dal contesto.per esempio.Un'intelligenza artificiale forte potrebbe riconoscere che "35F" in questo contesto è una temperatura e non un numero esadecimale.Ci sono sicuramente casi in cui anche un’intelligenza artificiale forte non sarebbe in grado di rispondere.Questi sono gli stessi casi in cui un essere umano non sarebbe in grado di rispondere (assumendo molto IA forte).

Ovviamente non ha molta importanza, dato che non abbiamo un'intelligenza artificiale forte.:)

http://www.logparser.com inoltra a un forum IIS che sembra abbastanza attivo.Questo è il sito ufficiale del "Log Parser Toolkit" di Gabriele Giuseppini.Anche se non ho mai utilizzato questo strumento, ho preso una copia economica del libro da Amazon Marketplace: oggi una copia costa solo $ 16.Niente batte un'interfaccia ad albero morto per semplicemente sfogliare le pagine.

Dando un'occhiata a questo forum, non avevo mai sentito parlare del "Nuovo strumento GUI per MS Log Parser, Log Parser Lizard" su http://www.lizardl.com/.

La questione chiave ovviamente è la complessità della tua GRAMMATICA.Per utilizzare qualsiasi tipo di log-parser come viene comunemente usato il termine, devi sapere esattamente cosa stai cercando e puoi scrivere un BNF per esso.Molti anni fa ho seguito un corso basato sul "Libro del Drago" di Aho e Ullman, e la tecnologia LALR completamente compresa può darti una velocità ottimale, a condizione ovviamente che tu abbia quel CFG.

D'altra parte sembra che tu stia probabilmente cercando qualcosa di simile all'intelligenza artificiale, che è un ordine di complessità completamente diverso.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top