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

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

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

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

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

13.08.2008 14:25:58
10 ОТВЕТОВ
РЕШЕНИЕ

Обзор:

Наивный !! Алгоритм отслеживает частоту слов в каждом столбце, где можно предположить, что каждая строка может быть разделена на столбцы с разделителем.

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

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

Частоты:

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/

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

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

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

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

6
22.08.2008 11:54:38

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

12
13.08.2008 14:28:26

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

2
13.08.2008 15:52:09

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

0
14.08.2008 02:01:34

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

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

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

1
14.08.2008 02:25:16

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

1: Эверест имеет высоту 30000 футов

2: К2 имеет высоту 28000 футов

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

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

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

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

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

Клаус

3
15.08.2008 15:00:43

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

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

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

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

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

Логгер начался.

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

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

1
15.08.2008 15:32:17

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

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

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

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

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

0
15.08.2008 18:01:45

@Anders

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

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

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

0
15.08.2008 18:11:42

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
23.09.2008 04:55:20