La recherche de l'algorithme qui inverse la fonction sprintf() de sortie

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

Question

Je suis en train de travailler sur un projet qui nécessite l'analyse de fichiers journaux.Je suis à la recherche d'un algorithme rapide qui permettrait de prendre les messages des groupes comme ceci:

La température au niveau de P1 est la 35F.

La température à P1 est 40F.

La température au niveau de P3 est 35F.

L'enregistreur est arrêté.

Enregistreur commencé.

La température à P1 est 40F.

et met quelque chose dans la forme d'un printf():

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

L'algorithme doit être suffisamment générique pour reconnaître presque tout de chargement des données dans des groupes de messages.

J'ai essayé de chercher ce genre de technologie, mais je ne sais même pas des termes exacts de la recherche.

Était-ce utile?

La solution

Vue d'ensemble:

Un naïf!! l'algorithme tient compte de la fréquence des mots dans une colonne où l'on peut supposer que chaque ligne peut être divisée en colonnes avec un délimiteur.

Exemple d'entrée:

Le chien a sauté sur la lune
Le chat sauta sur la lune
La lune a sauté par-dessus la lune
La voiture a sauté sur la lune

Fréquences:

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}

Nous pourrions partition de ces listes de fréquence plus par le groupement basé sur le nombre total de champs, mais dans ce simple exemple, nous ne sommes que de travailler avec un nombre fixe de champs (6).

La prochaine étape consiste à parcourir les lignes qui ont engendré ces listes de fréquence, alors prenons le premier exemple.

  1. L':qui répond à une certaine main-ondulés critères et l'algorithme décide qu'il doit être statique.
  2. chien:ne semble pas être statique basée sur le reste de la liste de fréquence, et donc il doit être dynamique, par opposition à un texte statique.Nous bouclons quelques pré-défini d'expressions régulières et de venir avec /[a-z]+/i.
  3. plus:même chose que #1;il est statique, afin de les laisser comme c'est.
  4. l':même chose que #1;il est statique, afin de les laisser comme c'est.
  5. lune:même chose que #1;il est statique, afin de les laisser comme c'est.

Donc, juste de passer au-dessus de la première ligne, nous pouvons mettre ensemble, l'expression régulière suivante:

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

Considérations:

  • Évidemment, on peut choisir de numériser une partie ou la totalité de ce document pour la première passe, tant que l'on est convaincu que les listes de fréquence sera un échantillonnage suffisante de l'ensemble des données.

  • Les faux positifs peuvent se glisser dans les résultats, et il sera à l'algorithme de filtrage (à la main en agitant) afin de fournir le meilleur seuil entre statique et dynamique des champs, ou de l'humain, de post-traitement.

  • Globalement, l'idée est sans doute bonne, mais la mise en œuvre réelle va certainement peser sur la vitesse et l'efficacité de cet algorithme.

Autres conseils

Je pense que vous pourriez être dominant et a raté fscanf() et sscanf().Qui sont à l'opposé de fprintf() et sprintf().

Merci pour toutes les bonnes suggestions.Chris, est droit.Je suis à la recherche d'une solution générique pour normaliser tout type de texte.La solution du problème se résume à dynmamically recherche de modèles dans deux ou plusieurs chaînes similaires.Presque comme la prévision de la prochaine élément dans un ensemble, basé sur les deux précédentes:

1:Everest est 30000 pieds de haut

2:K2 est de 28000 pieds de haut

=> Quel est le modèle?=> Réponse:

[nom] est de [nombre] pieds de haut

Maintenant, le fichier texte peut avoir des millions de lignes, et des milliers de modèles.Je voudrais analyser les fichiers très, très rapide, trouver les tendances et de recueillir les ensembles de données qui sont associées à chaque modèle.

J'ai réfléchi à la création de certains de haut niveau sémantique hachages pour représenter les modèles dans les chaînes de message.Je voudrais utiliser un générateur de jetons et de donner à chacun des jetons types spécifiques "poids".Alors je groupe les hachages et les taux de leur similarité.Une fois le regroupement est fait je voudrais recueillir les ensembles de données.

Je l'espérais, que je n'avais pas à réinventer la roue et pourrait réutiliser quelque chose qui est déjà là.

Klaus

Cela dépend de ce que vous essayez de faire, si votre objectif est de générer rapidement de sprintf() de l'entrée, cela fonctionne.Si vous essayez d'analyser les données, peut-être des expressions régulières ferait trop..

Vous n'allez pas trouver un outil qui peut tout simplement prendre arbitraire d'entrée, de deviner ce que les données que vous voulez à partir d'elle, et de produire le résultat que vous souhaitez.Qui sonne comme une intelligence artificielle efficace pour moi.

La production de quelque chose de ce genre, même juste pour reconnaître les chiffres, devient vraiment poilue.Par exemple, est "123.456" un ou deux numéros?Comment à ce sujet "123,456"?Est "35F" un nombre décimal et un " F " ou est-ce la valeur hexadécimale 0x35F?Vous allez avoir à construire quelque chose qui va analyser la façon dont vous avez besoin.Vous pouvez le faire avec des expressions régulières, ou vous pouvez le faire avec sscanf, ou vous pouvez le faire d'une autre manière, mais vous allez avoir à écrire quelque chose de personnalisé.

Cependant, avec de base des expressions régulières, vous pouvez le faire vous-même.Il ne sera pas de la magie, mais ce n'est pas que beaucoup de travail.Quelque chose comme ceci permettra d'analyser les lignes qui vous intéressent et les 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";

La sortie de cette isL

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

Vous pourriez faire quelque chose de similaire pour chaque type de ligne que vous devez analyser.Vous pouvez même lire ces expressions régulières à partir d'un fichier, au lieu de codage personnalisé à chacun.

Je ne connais pas d'outil spécifique pour le faire.Ce que j'ai fait quand j'ai eu le même problème à résoudre était d'essayer de deviner les expressions régulières pour faire des lignes.

J'ai ensuite traité les dossiers et affiche uniquement les inégalée lignes.Si une ligne est inégalée, cela signifie que le modèle est mauvais et doit être modifié ou un autre modèle doit être ajouté.

Après environ une heure de travail, j'ai réussi à trouver le ~20 modèles pour correspondre à 10000+ lignes.

Dans votre cas, vous pouvez d'abord "deviner" qu'un modèle est "The temperature at P[1-3] is [0-9]{2}F.".Si vous retraiter le fichier de retirer tout contenu de la ligne, il laisse "seulement":

L'enregistreur est arrêté.

Enregistreur commencé.

Vous pouvez ensuite correspondre avec "Logger (.+).".

Vous pouvez ensuite affiner les modèles et à en trouver de nouveaux pour correspondre à l'intégralité de votre journal.

@John:Je pense que la question se rapporte à un algorithme qui fait reconnaît modèles dans des fichiers journaux et automatiquement "devine" approprié chaînes de format et les données le concernant.L' *scanf la famille ne peut pas le faire sur son propre, il ne peut être d'aider à la fois les tendances ont été reconnus dans la première place.

@Derek Parc:Ainsi, même un fort IA ne pouvais pas être sûr qu'il avait le droit de réponse.

Peut-être certains de compression, comme mécanisme pourrait être utilisé:

  1. Trouver les grandes, fréquentes sous-chaînes
  2. Trouver les grandes, fréquentes sous-chaîne de motifs.(c'est à dire[modèle:1] [indésirable] [modèle:2])

Un autre élément à prendre en compte peut-être pour les lignes du groupe par edit-distance.Le regroupement des lignes similaires devraient diviser le problème en un-modèle-par groupe de blocs.

En fait, si vous parvenez à écrire, que le monde entier sache, Je pense que beaucoup d'entre nous aimeraient cet outil!

@Anders

Ainsi, même un fort IA ne pouvais pas être sûr qu'il avait le droit de réponse.

Je pensais que suffisamment forte IA pourrait habituellement trouver la bonne réponse à partir du contexte.par exempleForte de l'IA pourrait reconnaître que les "35F" dans ce contexte à une température et non pas d'un nombre hexadécimal.Il y a certainement des cas où même fort IA serait incapable de répondre.Ceux sont les mêmes cas où une personne serait incapable de répondre, bien que (en supposant que très forte de l'IA).

Bien sûr, il n'a pas vraiment d'importance, puisque nous n'avons pas une IA.:)

http://www.logparser.com transmet à une IIS forum qui semble assez active.C'est le site officiel de Gabriele Giuseppini du "Journal de l'Analyseur boîte à outils".Alors que je n'ai jamais utilisé cet outil, je n'ai ramasser une copie bon marché de la livre chez Amazon Marketplace - aujourd'hui, une copie est aussi bas que $16.Rien ne vaut un mort-arbre-interface pour juste en feuilletant les pages.

Jetant un coup d'oeil à ce forum, je n'avais pas encore entendu parler de "Nouvel outil graphique pour MS Analyseur de Journal, Journal de l'Analyseur de Lézard" à http://www.lizardl.com/.

La question clé est bien sûr de la complexité de votre GRAMMAIRE.Pour utiliser n'importe quel type de connexion de l'analyseur que le terme est couramment utilisé, vous devez savoir exactement ce que vous numérisez, vous pouvez écrire un BNF pour elle.Il y a plusieurs années, j'ai pris un cours basé sur Aho-et-Ullman du Dragon "Livre", et l'a bien compris LALR de la technologie peut vous donner une vitesse optimale, à condition bien sûr que vous avez CFG.

D'autre part, il semble que vous êtes probablement atteint pour quelque chose, AI-like, qui est un ordre de complexité entièrement.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top