Procurando um algoritmo que reverta a saída da função sprintf()

Question

Estou trabalhando em um projeto que requer análise de arquivos de log.Estou procurando um algoritmo rápido que receba mensagens de grupos como esta:

A temperatura em P1 é 35F.

A temperatura em P1 é 40F.

A temperatura em P3 é 35F.

O registrador parou.

Registrador iniciado.

A temperatura em P1 é 40F.

e lança algo na forma de printf():

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

O algoritmo precisa ser genérico o suficiente para reconhecer quase qualquer carga de dados em grupos de mensagens.

Tentei pesquisar esse tipo de tecnologia, mas nem sei os termos corretos para pesquisar.

Answer 1

Visão geral:

A ingênuo!! O algoritmo rastreia a frequência das palavras por coluna, onde se pode assumir que cada linha pode ser separada em colunas com um delimitador.

Exemplo de entrada:

O cachorro pulou na lua
O gato pulou na lua
A lua saltou sobre a lua
O carro saltou sobre a lua

Frequências:

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}

Poderíamos particionar ainda mais essas listas de frequência agrupando-as com base no número total de campos, mas neste exemplo simples e conveniente, estamos trabalhando apenas com um número fixo de campos (6).

O próximo passo é iterar pelas linhas que geraram essas listas de frequência, então vamos dar o primeiro exemplo.

1. O:atende a alguns critérios manuais e o algoritmo decide que deve ser estático.
2. cachorro:não parece ser estático com base no restante da lista de frequências e, portanto, deve ser dinâmico em oposição ao texto estático.Percorremos algumas expressões regulares predefinidas e chegamos a /[a-z]+/i.
3. sobre:mesma oferta do nº 1;é estático, então deixe como está.
4. o:mesma oferta do nº 1;é estático, então deixe como está.
5. lua:mesma oferta do nº 1;é estático, então deixe como está.

Assim, apenas repassando a primeira linha podemos montar a seguinte expressão regular:

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

Considerações:

• Obviamente, pode-se optar por digitalizar parte ou todo o documento na primeira passagem, desde que se tenha certeza de que as listas de frequência serão uma amostragem suficiente de todos os dados.

• Falsos positivos podem aparecer nos resultados, e caberá ao algoritmo de filtragem (acenar com a mão) fornecer o melhor limite entre campos estáticos e dinâmicos, ou algum pós-processamento humano.

• A ideia geral é provavelmente boa, mas a implementação real certamente influenciará a velocidade e a eficiência desse algoritmo.

Answer 2

Acho que você pode estar esquecendo e esquecendo fscanf() e sscanf().Que são o oposto de fprintf() e sprintf().

Answer 3

Obrigado por todas as ótimas sugestões.Cris, está certo.Estou procurando uma solução genérica para normalizar qualquer tipo de texto.A solução do problema se resume em encontrar padrões dinamicamente em duas ou mais strings semelhantes.Quase como prever o próximo elemento de um conjunto, com base nos dois anteriores:

1:Everest tem 30.000 pés de altura

2:K2 tem 28.000 pés de altura

=> Qual é o padrão?=> Resposta:

[nome] tem [número] pés de altura

Agora o arquivo de texto pode ter milhões de linhas e milhares de padrões.Gostaria de analisar os arquivos muito, muito rapidamente, encontrar os padrões e coletar os conjuntos de dados associados a cada padrão.

Pensei em criar alguns hashes semânticos de alto nível para representar os padrões nas cadeias de mensagens.Eu usaria um tokenizer e daria a cada um dos tipos de tokens um "peso" específico.Então eu agruparia os hashes e avaliaria sua similaridade.Assim que o agrupamento estiver concluído, eu coletaria os conjuntos de dados.

Eu esperava não ter que reinventar a roda e poder reutilizar algo que já existe.

Klaus

Answer 4

Depende do que você está tentando fazer, se seu objetivo é gerar rapidamente a entrada sprintf(), isso funciona.Se você estiver tentando analisar dados, talvez expressões regulares também funcionem.

Answer 5

Você não encontrará uma ferramenta que possa simplesmente receber entradas arbitrárias, adivinhar quais dados você deseja e produzir a saída desejada.Isso me parece uma IA forte.

Produzir algo assim, mesmo que apenas para reconhecer números, fica muito complicado.Por exemplo, "123.456" é um número ou dois?Que tal este “123.456”?"35F" é um número decimal e um 'F' ou é o valor hexadecimal 0x35F?Você terá que construir algo que será analisado da maneira que você precisa.Você pode fazer isso com expressões regulares ou com sscanf, ou você pode fazer isso de outra maneira, mas terá que escrever algo personalizado.

No entanto, com expressões regulares básicas, você pode fazer isso sozinho.Não será mágica, mas não dá muito trabalho.Algo assim irá analisar as linhas de seu interesse e consolidá-las (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";

A saída disso éL

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

Você poderia fazer algo semelhante para cada tipo de linha que precisa analisar.Você pode até ler essas expressões regulares em um arquivo, em vez de codificar cada uma delas de forma personalizada.

Answer 6

Não conheço nenhuma ferramenta específica para fazer isso.O que fiz quando tive um problema semelhante para resolver foi tentar adivinhar expressões regulares para corresponder às linhas.

Em seguida, processei os arquivos e exibi apenas as linhas sem correspondência.Se uma linha não corresponder, significa que o padrão está errado e deve ser ajustado ou outro padrão deve ser adicionado.

Depois de cerca de uma hora de trabalho, consegui encontrar cerca de 20 padrões que correspondiam a mais de 10.000 linhas.

No seu caso, você pode primeiro "adivinhar" que um padrão é "The temperature at P[1-3] is [0-9]{2}F.".Se você reprocessar o arquivo removendo qualquer linha correspondente, restará "apenas":

O registrador parou.

Registrador iniciado.

Com o qual você pode combinar "Logger (.+).".

Você pode então refinar os padrões e encontrar novos que correspondam a todo o seu registro.

Answer 7

@John:Acho que a questão está relacionada a um algoritmo que realmente reconhece padrões em arquivos de log e "adivinha" automaticamente strings e dados de formato apropriados para ele.O *scanf a família não pode fazer isso sozinha; ela só pode ajudar quando os padrões forem reconhecidos em primeiro lugar.

Answer 8

@Derek Parque:Bem, mesmo uma IA forte não poderia ter certeza de ter a resposta certa.

Talvez algum mecanismo semelhante à compressão pudesse ser usado:

2. Encontre substrings grandes e frequentes
3. Encontre padrões de substring grandes e frequentes.(ou seja,[padrão:1] [lixo] [padrão:2])

Outro item a considerar pode ser agrupar linhas por distância de edição.O agrupamento de linhas semelhantes deve dividir o problema em partes de um padrão por grupo.

Na verdade, se você conseguir escrever isso, deixe o mundo inteiro saber, acho que muitos de nós gostaríamos dessa ferramenta!

Answer 9

@Anders

Bem, mesmo uma IA forte não poderia ter certeza de ter a resposta certa.

Eu estava pensando que uma IA suficientemente forte poderia geralmente descobrir a resposta certa a partir do contexto.por exemplo.A IA forte poderia reconhecer que “35F” neste contexto é uma temperatura e não um número hexadecimal.Definitivamente, há casos em que mesmo uma IA forte seria incapaz de responder.Esses são os mesmos casos em que um humano seria incapaz de responder (assumindo muito IA forte).

Claro, isso realmente não importa, já que não temos uma IA forte.:)

Answer 10

http://www.logparser.com encaminha para um fórum do IIS que parece bastante ativo.Este é o site oficial do "Log Parser Toolkit" de Gabriele Giuseppini.Embora eu nunca tenha usado essa ferramenta, comprei uma cópia barata do livro no Amazon Marketplace - hoje uma cópia custa apenas US$ 16.Nada se compara a uma interface de árvore morta apenas para folhear as páginas.

Olhando para este fórum, eu não tinha ouvido falar anteriormente sobre a "Nova ferramenta GUI para MS Log Parser, Log Parser Lizard" em http://www.lizardl.com/.

A questão principal, claro, é a complexidade da sua GRAMÁTICA.Para usar qualquer tipo de analisador de log, como o termo é comumente usado, você precisa saber exatamente o que está procurando, você pode escrever um BNF para isso.Muitos anos atrás, fiz um curso baseado no "Livro do Dragão" de Aho-and-Ullman, e a tecnologia LALR totalmente compreendida pode fornecer a velocidade ideal, desde que você tenha esse CFG.

Por outro lado, parece que você está buscando algo semelhante à IA, que é uma ordem de complexidade totalmente diferente.