Ищем алгоритм, который обращает вывод функции sprintf () - PullRequest
5 голосов
/ 13 августа 2008

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

Температура на 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)}

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

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

Ответы [ 10 ]

12 голосов
/ 13 августа 2008

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

6 голосов
/ 15 августа 2008

Обзор:

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. dog : не выглядит статичным, основываясь на остальной части списка частот, и поэтому должно быть динамическим, а не статическим текстом. Мы перебираем несколько предопределенных регулярных выражений и получаем /[a-z]+/i.
  3. свыше : та же сделка, что и # 1; это статично, поэтому оставьте как есть.
  4. the : та же сделка, что и # 1; это статично, поэтому оставьте как есть.
  5. луна : то же самое, что и # 1; это статично, так что оставьте как есть.

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

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

Вопросы:

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

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

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

3 голосов
/ 15 августа 2008

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

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

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

=> Что такое шаблон? => Ответ:

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

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

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

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

Klaus

2 голосов
/ 13 августа 2008

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

1 голос
/ 15 августа 2008

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

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

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

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

Регистратор остановлен.

Регистратор запущен.

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

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

1 голос
/ 14 августа 2008

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

Создание чего-то подобного, даже для распознавания чисел, становится поистине волосатым. Например "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)}

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

0 голосов
/ 23 сентября 2008

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

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

Ключевым вопросом, конечно же, является сложность вашей грамматики. Чтобы использовать любой вид лог-парсера в качестве термина, который обычно используется, вам нужно точно знать, для чего вы сканируете, вы можете написать для него BNF. Много лет назад я прошел курс, основанный на «Книге Дракона» Ахо-и-Уллмана, и тщательно изученная технология LALR может дать вам оптимальную скорость при условии, конечно, что у вас есть этот CFG.

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

0 голосов
/ 15 августа 2008

@ Anders

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

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

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

0 голосов
/ 15 августа 2008

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

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

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

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

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

0 голосов
/ 14 августа 2008

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

...