Suche nach einem Algorithmus, der die Ausgabe der Funktion sprintf() umkehrt

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

Frage

Ich arbeite an einem Projekt, das das Parsen von Protokolldateien erfordert.Ich suche nach einem schnellen Algorithmus, der Gruppennachrichten wie diese entgegennimmt:

Die Temperatur an P1 beträgt 35F.

Die Temperatur an P1 beträgt 40F.

Die Temperatur bei P3 beträgt 35F.

Logger gestoppt.

Logger gestartet.

Die Temperatur an P1 beträgt 40F.

und gibt etwas in Form eines printf() aus:

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

Der Algorithmus muss generisch genug sein, um nahezu jede Datenlast in Nachrichtengruppen zu erkennen.

Ich habe versucht, nach dieser Art von Technologie zu suchen, kenne aber nicht einmal die richtigen Begriffe, nach denen ich suchen soll.

War es hilfreich?

Lösung

Überblick:

A naiv!! Der Algorithmus verfolgt die Häufigkeit von Wörtern spaltenweise, wobei man davon ausgehen kann, dass jede Zeile mit einem Trennzeichen in Spalten unterteilt werden kann.

Beispieleingabe:

Der Hund sprang über den Mond
Die Katze sprang über den Mond
Der Mond sprang über den Mond
Das Auto sprang über den Mond

Frequenzen:

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}

Wir könnten diese Häufigkeitslisten weiter unterteilen, indem wir sie basierend auf der Gesamtzahl der Felder gruppieren, aber in diesem einfachen und praktischen Beispiel arbeiten wir nur mit einer festen Anzahl von Feldern (6).

Der nächste Schritt besteht darin, die Zeilen zu durchlaufen, die diese Häufigkeitslisten generiert haben. Nehmen wir also das erste Beispiel.

  1. Der:erfüllt einige Handwellenkriterien und der Algorithmus entscheidet, dass es statisch sein muss.
  2. Hund:scheint im Vergleich zum Rest der Häufigkeitsliste nicht statisch zu sein und muss daher im Gegensatz zu statischem Text dynamisch sein.Wir durchlaufen ein paar vordefinierte reguläre Ausdrücke und kommen zu dem Ergebnis /[a-z]+/i.
  3. über:gleiches Angebot wie Nr. 1;Es ist statisch, also lassen Sie es so wie es ist.
  4. Die:gleiches Angebot wie Nr. 1;Es ist statisch, also lassen Sie es so wie es ist.
  5. Mond:gleiches Angebot wie Nr. 1;Es ist statisch, also lassen Sie es so wie es ist.

Wenn wir also die erste Zeile durchgehen, können wir den folgenden regulären Ausdruck zusammenstellen:

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

Überlegungen:

  • Natürlich kann man beim ersten Durchgang wählen, ob man einen Teil oder das ganze Dokument scannen möchte, solange man sicher ist, dass die Häufigkeitslisten eine ausreichende Stichprobe der gesamten Daten darstellen.

  • In den Ergebnissen können sich falsch positive Ergebnisse einschleichen, und es liegt am Filteralgorithmus (Handbewegung), den besten Schwellenwert zwischen statischen und dynamischen Feldern bereitzustellen, oder an einer menschlichen Nachbearbeitung.

  • Die Gesamtidee ist wahrscheinlich gut, aber die tatsächliche Implementierung wird sich definitiv auf die Geschwindigkeit und Effizienz dieses Algorithmus auswirken.

Andere Tipps

Ich denke, Sie haben möglicherweise fscanf() und sscanf() übersehen und übersehen.Welche sind das Gegenteil von fprintf() und sprintf().

Vielen Dank für all die tollen Vorschläge.Chris, hat recht.Ich suche nach einer generischen Lösung zum Normalisieren jeglicher Art von Text.Die Lösung des Problems besteht darin, dynamisch Muster in zwei oder mehr ähnlichen Strings zu finden.Fast so, als würde man das nächste Element in einer Menge vorhersagen, basierend auf den beiden vorherigen:

1:Der Everest ist 30.000 Fuß hoch

2:K2 ist 28.000 Fuß hoch

=> Was ist das Muster?=> Antwort:

[Name] ist [Nummer] Fuß hoch

Jetzt kann die Textdatei Millionen von Zeilen und Tausende von Mustern enthalten.Ich möchte die Dateien sehr, sehr schnell analysieren, die Muster finden und die Datensätze sammeln, die jedem Muster zugeordnet sind.

Ich habe darüber nachgedacht, einige semantische Hashes auf hoher Ebene zu erstellen, um die Muster in den Nachrichtenzeichenfolgen darzustellen.Ich würde einen Tokenizer verwenden und jedem Tokentyp ein bestimmtes „Gewicht“ zuweisen.Dann würde ich die Hashes gruppieren und ihre Ähnlichkeit bewerten.Sobald die Gruppierung abgeschlossen ist, würde ich die Datensätze sammeln.

Ich hatte gehofft, dass ich das Rad nicht neu erfinden muss und etwas wiederverwenden könnte, was es bereits gibt.

Klaus

Es hängt davon ab, was Sie tun möchten. Wenn Ihr Ziel darin besteht, schnell sprintf()-Eingaben zu generieren, funktioniert dies.Wenn Sie versuchen, Daten zu analysieren, reichen möglicherweise auch reguläre Ausdrücke aus.

Sie werden kein Tool finden, das einfach beliebige Eingaben entgegennimmt, daraus errät, welche Daten Sie benötigen, und die gewünschte Ausgabe erzeugt.Das klingt für mich nach starker KI.

So etwas zu produzieren, auch nur um Zahlen zu erkennen, wird wirklich haarsträubend.Ist „123.456“ beispielsweise eine oder zwei Zahlen?Wie wäre es mit dieser „123.456“?Ist „35F“ eine Dezimalzahl und ein „F“ oder handelt es sich um den Hexadezimalwert 0x35F?Sie müssen etwas erstellen, das die Analyse auf die von Ihnen benötigte Weise durchführt.Sie können dies mit regulären Ausdrücken oder mit tun sscanf, oder Sie können es auf andere Weise tun, aber Sie müssen etwas Benutzerdefiniertes schreiben.

Mit einfachen regulären Ausdrücken können Sie dies jedoch selbst tun.Es wird keine Zauberei sein, aber es ist auch nicht so viel Arbeit.So etwas analysiert die Zeilen, an denen Sie interessiert sind, und konsolidiert sie (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";

Die Ausgabe davon istL

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

Sie könnten für jeden Zeilentyp, den Sie analysieren müssen, etwas Ähnliches tun.Sie könnten diese regulären Ausdrücke sogar aus einer Datei lesen, anstatt jeden einzelnen individuell zu codieren.

Ich kenne kein spezielles Tool dafür.Als ich ein ähnliches Problem zu lösen hatte, habe ich versucht, reguläre Ausdrücke zu erraten, um Zeilen zuzuordnen.

Anschließend habe ich die Dateien verarbeitet und nur die nicht übereinstimmenden Zeilen angezeigt.Wenn eine Linie nicht übereinstimmt, bedeutet dies, dass das Muster falsch ist und angepasst oder ein anderes Muster hinzugefügt werden sollte.

Nach etwa einer Stunde Arbeit gelang es mir, die etwa 20 Muster zu finden, die zu mehr als 10.000 Linien passen.

In Ihrem Fall können Sie zunächst „erraten“, dass es sich um ein Muster handelt "The temperature at P[1-3] is [0-9]{2}F.".Wenn Sie die Datei erneut verarbeiten und alle übereinstimmenden Zeilen entfernen, bleibt „nur“ übrig:

Logger gestoppt.

Logger gestartet.

Womit Sie dann zuordnen können "Logger (.+).".

Anschließend können Sie die Muster verfeinern und neue finden, die zu Ihrem gesamten Protokoll passen.

@John:Ich denke, dass sich die Frage auf einen Algorithmus bezieht, der tatsächlich Muster in Protokolldateien erkennt und automatisch geeignete Formatzeichenfolgen und Daten dafür „errät“.Der *scanf Die Familie kann das nicht alleine schaffen, sie kann nur dann helfen, wenn die Muster erst einmal erkannt wurden.

@Derek Park:Nun, selbst eine starke KI konnte nicht sicher sein, dass sie die richtige Antwort hatte.

Möglicherweise könnte ein kompressionsähnlicher Mechanismus verwendet werden:

  1. Finden Sie große, häufige Teilzeichenfolgen
  2. Finden Sie große, häufige Teilzeichenfolgenmuster.(d. h.[Muster:1] [Müll] [Muster:2])

Ein weiterer zu berücksichtigender Punkt könnte darin bestehen, Zeilen nach zu gruppieren Bearbeitungsentfernung.Durch das Gruppieren ähnlicher Zeilen sollte das Problem in Blöcke mit einem Muster pro Gruppe aufgeteilt werden.

Eigentlich, wenn Sie es schaffen, das zu schreiben, lass es die ganze Welt wissen, Ich denke, viele von uns würden dieses Tool mögen!

@Anders

Nun, selbst eine starke KI konnte nicht sicher sein, dass sie die richtige Antwort hatte.

Ich dachte, dass eine ausreichend starke KI das könnte normalerweise Finden Sie die richtige Antwort aus dem Kontext heraus.z.B.Eine starke KI könnte erkennen, dass „35F“ in diesem Zusammenhang eine Temperatur und keine Hexzahl ist.Es gibt definitiv Fälle, in denen selbst eine starke KI nicht in der Lage wäre, eine Antwort zu geben.Dies sind jedoch die gleichen Fälle, in denen ein Mensch nicht in der Lage wäre zu antworten (vorausgesetzt). sehr starke KI).

Das spielt natürlich keine Rolle, da wir keine starke KI haben.:) :)

http://www.logparser.com Weiterleitung zu einem IIS-Forum, das ziemlich aktiv zu sein scheint.Dies ist die offizielle Seite für Gabriele Giuseppinis „Log Parser Toolkit“.Obwohl ich dieses Tool noch nie verwendet habe, habe ich mir doch ein günstiges Exemplar des Buches auf dem Amazon Marketplace besorgt – heute kostet ein Exemplar nur 16 US-Dollar.Es gibt nichts Besseres als eine Dead-Tree-Schnittstelle zum einfachen Durchblättern von Seiten.

Als ich mir dieses Forum ansah, hatte ich zuvor noch nichts von dem „neuen GUI-Tool für MS Log Parser, Log Parser Lizard“ gehört http://www.lizardl.com/.

Das Hauptproblem ist natürlich die Komplexität Ihrer GRAMMATIK.Um irgendeine Art von Log-Parser zu verwenden, wie der Begriff allgemein verwendet wird, müssen Sie genau wissen, wonach Sie suchen. Sie können eine BNF dafür schreiben.Vor vielen Jahren habe ich einen Kurs belegt, der auf Aho-and-Ullmans „Dragon Book“ basiert, und die gründlich verstandene LALR-Technologie kann Ihnen optimale Geschwindigkeit bieten, vorausgesetzt natürlich, Sie haben das CFG.

Andererseits scheint es, dass Sie möglicherweise nach etwas KI-ähnlichem greifen, was eine völlig andere Komplexitätsstufe darstellt.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top