Laden...

Mustererkennung bei Zeichenketten und Ableitung von Templates

Erstellt von telnet vor 12 Jahren Letzter Beitrag vor 12 Jahren 1.548 Views
T
telnet Themenstarter:in
327 Beiträge seit 2006
vor 12 Jahren
Mustererkennung bei Zeichenketten und Ableitung von Templates

Hallo,

ich stehe aktuell vor der Aufgabe, dass eine Anwendung eine große Anzahl an Zeichenketten bekommen und diese möglichst platzsparend abspeichern soll.

Die Anwendung selbst ist ein einfacher Windows-Service, die Daten werden in einer SQL-Server Datenbank gespeichert.

Die Zeichenketten, die beim Service eintreffen, können n unterschiedlichen Mustern folgen, z.B.:

Nachricht: XXX: 21
Systemnachricht: 16
...

Viele Nachrichten sind dabei gleich aufgebaut, d.h. Sie haben feste Bestandsteile in einer festen Reihenfolge, wobei zwischen die festen auch variable Bestandsteile eingestreut sind.

Was ich jetzt gerne erreichen würde wäre, die variablen Bestandteile zu erkennen. Damit könnte ich den "festen Teil" in einer Tabelle als Template speichern und in der eigentlichen Eingangstabelle würde dann nur das Template referenziert + die variablen Werte abgelegt.

Gibt es hierfür so was wie ein "Entwurfsmuster" oder eine allgemeine herangehensweise? Hat jemand evtl. einen Ansatz, wie man da am geschicktesten rangeht? Danke!

G
538 Beiträge seit 2008
vor 12 Jahren

Ich weiß nun nicht, ob der Client schon fest definiert ist, aber ich kann dir zumindest sagen, wie der SQL-Server das Regelt:

Und zwar hat jede Meldung eine Nummer - hinter den Nummern versteckt sich eine Einfacher Format-String und dann wird der Formatstring ausgewertet und die {0} werden ersetzt durch die übergebenen Parameter.

Genau das kannst du auch tun.
Übermittle die Nachricht als Formatstring (oder nur eine NAchrichtennummer) und den variablen Inhalt als array oder Liste.
Dann kannst du einfach die gesamte Meldung erzeugen und außerdem Feststellen, ob du die Meldung schon kennst und referenzieren kannst.

Der Vorteil der Klugheit liegt darin, dass man sich dumm stellen kann - umgekehrt ist das schon schwieriger (K. Tucholsky)
Das Problem mit Internet-Zitaten ist, dass sie oftmals zu unrecht als authentisch angenommen werden. (K. Adenauer)

T
telnet Themenstarter:in
327 Beiträge seit 2006
vor 12 Jahren

An so was in der Richtung hatte ich auch schon gedacht. Das Problem ist: Wie erkenne ich automatisch die Formatstrings, wenn ich sie nicht vordefinieren kann und will, weil sie sich ständig ändern können bzw. nicht meiner Kontrolle unterliegen? Die zu speichernden Nachrichten kommen aus einem Drittsystem und werden nicht vom Anwender des Programms verwaltet....

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo telnet,

ich glaube eine wirklich korrekte Erkennung der verwendeten Formatstrings ist nicht möglich, nicht mal für einen Menschen. Wenn der Computer einem Menschen nahe kommen soll, wäre wohl KI nötig. Ein Mensch könnte z.B. erkennen oder doch zumindest stark vermuten, dass bei den Ausgaben

2011-11-18 10:00: Application "Test" started 2011-11-18 10:16: Application "Test" started 2011-11-18 10:27: Application "Test" started

der Formatstring

{0}: Application "{1}" started

lautet und nicht etwa

2011-11-18 10:{0}: Application "Test" started

Aber vielleicht ist der Formatstring auch

{0}: {1}

wer soll das mit Sicherheit sagen?

Wenn es dir aber nur um die Datenkompression geht und nicht darum, exakt die relevanten variablen Teile zu extrahieren, kann man sicher was machen. Trivial ist das sicher nicht, aber hier mal die Richtung, die ich einschlagen würde. Die kannst die vorhanden Ausgaben paarweise mit Longest common subsequence vergleichen und dann schauen bzw. dann nach und nach herausfinden, welche Strings sich ähneln und welches die gemeinsamen und welches die variablen Teile sind.

Es reicht jedoch nicht, dass einmal zu tun, sondern das muss zumindest in Abständen wiederholt werden. Denn sonst erkennst du für das obige Beispiel nach ein paar mehr Beispielen vielleicht den Formatstring

2011-{0}: Application "{1}" started

der dann aber nach dem Jahreswechsel nicht mehr passt.

herbivore

6.911 Beiträge seit 2009
vor 12 Jahren

Hallo telnet,

wie auch herbivore glaube ich nicht an eine vollautomatische und korrekte Erkennung des Musters bzw. dessen Herleitung.

Ein Ansatz in Richtung KI wäre die Verwendung eines Hidden Markov Model.
Für eine grobe Unterteilung in "Gruppen" eignet sich mMn die Damerau–Levenshtein distance, von der aus dann das HMM erstellt werden kann.

Die Frage ist auch obs komplett vollautomatisch geschehen soll od. (von Zeit zu Zeit) ein Mensch eingreifen kann. Wenn es also möglich ist, dass ein Mensch eingreift so könnte dieser nachdem genügend großen Gruppen erstellt wurden das Format-Muster (für string.Format) erzeugen. Weiters könnte auch gleich (für jede Gruppe) ein Regex-Muster erstellt werden mit dem dann treffergenauer die Zuordnung zur Gruppe ermittelt werden kann.

Den Teil des menschlichen Eingreifen kannst auch gut mit herbivores Vorschlag kombinieren.

BTW: in der Literatur muss sich dazu ja was finden lassen, denn ich kann mir nicht vorstellen dass dies noch nie (wissenschaftlich) behandelt wurde. Suche mal nach "template inferring", "template detection", usw.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"