Ищу алгоритм, который отменяет вывод функции sprintf()

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

Вопрос

Я работаю над проектом, который требует синтаксического анализа файлов журналов.Я ищу быстрый алгоритм, который принимал бы групповые сообщения, подобные этому:

Температура при P1 составляет 35F.

Температура при P1 равна 40F.

Температура при P3 составляет 35F.

Лесоруб остановился.

Регистратор запустился.

Температура при P1 равна 40F.

и выдает что-то в виде printf():

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

Алгоритм должен быть достаточно общим, чтобы распознавать практически любую загрузку данных в группах сообщений.

Я пытался найти подобную технологию, но я даже не знаю правильных терминов для поиска.

Это было полезно?

Решение

Обзор:

A naïve!! алгоритм отслеживает частоту слов по столбцам, где можно предположить, что каждая строка может быть разделена на столбцы разделителем.

Пример ввода:

Собака перепрыгнула через луну
Кошка перепрыгнула через луну
Луна перепрыгнула через луну
Машина перепрыгнула через луну

Частоты:

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}

Мы могли бы дополнительно разделить эти списки частот, сгруппировав их на основе общего количества полей, но в этом простом и удобном примере мы работаем только с фиксированным количеством полей (6).

Следующим шагом будет перебор строк, которые сгенерировали эти списки частот, поэтому давайте рассмотрим первый пример.

  1. Тот Самый:соответствует некоторым критериям, заданным вручную, и алгоритм решает, что он должен быть статичным.
  2. собака:не выглядит статичным на основе остальной части списка частот, и, следовательно, он должен быть динамическим в отличие от статического текста.Мы перебираем несколько предопределенных регулярных выражений и получаем /[a-z]+/i.
  3. закончился:та же сделка, что и №1;это статично, так что оставьте как есть.
  4. тот самый:та же сделка, что и №1;это статично, так что оставьте как есть.
  5. луна:та же сделка, что и №1;это статично, так что оставьте как есть.

Таким образом, просто перейдя к первой строке, мы можем составить следующее регулярное выражение:

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

Соображения:

  • Очевидно, что можно выбрать сканирование части или всего документа для первого прохода, если вы уверены, что списки частот будут достаточной выборкой для всех данных.

  • В результаты могут вкрасться ложноположительные результаты, и обеспечить наилучший порог между статическими и динамическими полями будет зависеть от алгоритма фильтрации (взмах руки) или от некоторой постобработки человеком.

  • Общая идея, вероятно, хорошая, но фактическая реализация определенно повлияет на скорость и эффективность этого алгоритма.

Другие советы

Я думаю, вы, возможно, упустили из виду fscanf() и sscanf().Которые являются противоположностью fprintf() и sprintf().

Спасибо за все замечательные предложения.Крис, ты прав.Я ищу общее решение для нормализации любого вида текста.Решение задачи сводится к динамическому нахождению шаблонов в двух или более похожих строках.Почти как предсказание следующего элемента в наборе, основанное на двух предыдущих:

1:Высота Эвереста составляет 30000 футов

2:Высота K2 составляет 28000 футов

=> Что это за закономерность?=> Ответ:

[имя] - это [число] высотой в фут

Теперь текстовый файл может содержать миллионы строк и тысячи шаблонов.Я хотел бы очень, очень быстро проанализировать файлы, найти шаблоны и собрать наборы данных, которые связаны с каждым шаблоном.

Я подумал о создании нескольких высокоуровневых семантических хэшей для представления шаблонов в строках сообщений.Я бы использовал токенизатор и присвоил каждому из типов токенов определенный "вес".Затем я бы сгруппировал хэши и оценил их сходство.Как только группировка будет завершена, я бы собрал наборы данных.

Я надеялся, что мне не придется изобретать велосипед и я смогу повторно использовать то, что уже есть.

Klaus

Это зависит от того, что вы пытаетесь сделать, если ваша цель - быстро сгенерировать входные данные sprintf (), это работает.Если вы пытаетесь проанализировать данные, возможно, регулярные выражения тоже подойдут..

Вы не найдете инструмент, который может просто принимать произвольные входные данные, угадывать, какие данные вы хотите получить из них, и выдавать желаемый результат.По-моему, это звучит как сильный искусственный интеллект.

Создание чего-то подобного, даже просто для распознавания чисел, становится по-настоящему сложным делом.Например, "123.456" - это одно число или два?Как насчет этого "123 456"?Является ли "35F" десятичным числом и "F" или это шестнадцатеричное значение 0x35F?Вам нужно будет создать что-то, что будет анализировать так, как вам нужно.Вы можете сделать это с помощью регулярных выражений, или вы можете сделать это с помощью sscanf, или вы можете сделать это каким-то другим способом, но вам придется написать что-то индивидуальное.

Однако с помощью базовых регулярных выражений вы можете сделать это самостоятельно.Это не будет волшебством, но и работы не так уж много.Что-то вроде этого проанализирует интересующие вас строки и объединит их (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";

Вывод из этого isL

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

Вы могли бы сделать что-то подобное для каждого типа строки, которую вам нужно проанализировать.Вы даже могли бы прочитать эти регулярные выражения из файла, вместо того чтобы специально кодировать каждое из них.

Я не знаю какого-либо конкретного инструмента для этого.То, что я делал, когда мне приходилось решать подобную проблему, - пытался подобрать регулярные выражения для соответствия строкам.

Затем я обработал файлы и отобразил только несогласованные строки.Если строка не совпадает, это означает, что шаблон неправильный и его следует изменить или добавить другой шаблон.

Примерно через час работы мне удалось найти ~ 20 шаблонов, соответствующих более чем 10000 строкам.

В вашем случае вы можете сначала "догадаться", что один шаблон является "The temperature at P[1-3] is [0-9]{2}F.".Если вы повторно обработаете файл, удалив любую совпадающую строку, останется "только":

Лесоруб остановился.

Регистратор запустился.

Который затем вы можете сопоставить с "Logger (.+).".

Затем вы можете усовершенствовать шаблоны и найти новые, соответствующие всему вашему журналу.

@Джон:Я думаю, что вопрос относится к алгоритму, который фактически распознает шаблоны в файлах журналов и автоматически "угадывает" соответствующие строки формата и данные для него.Тот Самый *scanf семья не может сделать это сама, она может помочь только после того, как паттерны будут распознаны с самого начала.

@Дерек Парк:Что ж, даже сильный искусственный интеллект не мог быть уверен, что у него есть правильный ответ.

Возможно, можно было бы использовать какой-нибудь механизм, подобный сжатию:

  1. Поиск больших, частых подстрок
  2. Найдите большие, частые шаблоны подстрок.(т.е.[шаблон:1] [мусор] [шаблон:2])

Другим пунктом, который следует рассмотреть, может быть группировка строк по редактировать-расстояние.Группировка похожих строк должна разбить проблему на фрагменты по одному шаблону на группу.

На самом деле, если вам удастся написать это, пусть весь мир узнает, Я думаю, многим из нас понравился бы этот инструмент!

@Андерс

Что ж, даже сильный искусственный интеллект не мог быть уверен, что у него есть правильный ответ.

Я думал, что достаточно сильный искусственный интеллект мог бы обычно определите правильный ответ из контекста.например ,Сильный искусственный интеллект мог бы распознать, что "35F" в данном контексте - это температура, а не шестнадцатеричное число.Определенно, есть случаи, когда даже сильный искусственный интеллект не смог бы ответить.Это те же самые случаи, когда человек не смог бы ответить, хотя (предполагая очень сильный искусственный интеллект).

Конечно, на самом деле это не имеет значения, поскольку у нас нет сильного искусственного интеллекта.:)

http://www.logparser.com перенаправляет на форум IIS, который кажется довольно активным.Это официальный сайт "Инструментария для анализа журналов" Габриэле Джузеппини.Хотя я никогда на самом деле не пользовался этим инструментом, я купил дешевый экземпляр книги на Amazon Marketplace - сегодня экземпляр стоит всего 16 долларов.Ничто не сравнится с интерфейсом мертвого дерева для простого перелистывания страниц.

Заглянув на этот форум, я ранее не слышал о "Новом графическом инструменте для MS Log Parser, Log Parser Lizard" на http://www.lizardl.com/.

Ключевой проблемой, конечно, является сложность вашей ГРАММАТИКИ.Чтобы использовать любой тип анализатора журналов в том виде, в каком этот термин обычно используется, вам нужно точно знать, что вы сканируете, вы можете написать для этого BNF.Много лет назад я прослушал курс, основанный на "Книге дракона" Ахо и Ульмана, и досконально изученная технология LALR может обеспечить вам оптимальную скорость, при условии, конечно, что у вас есть этот CFG.

С другой стороны, кажется, что вы, возможно, стремитесь к чему-то похожему на искусственный интеллект, что представляет собой совершенно другой порядок сложности.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top