Автоматически построенные регулярные выражения, которые соответствуют набору строк

Question

Мы написали систему для анализа сообщений журнала из большой сети.Система берет сообщения журнала из множества различных сетевых элементов и анализирует их с помощью выражений регулярных выражений.Например, пользователь мог написать два правила:

^cron/script\.sh.*
.*script\.sh [0-9]+$

В этом случае будут выбраны только журналы, которые соответствуют заданным шаблонам.Причина фильтрации заключается в том, что в журнале может быть очень много сообщений, до 1 ГБ в день.

Теперь основная часть моего вопроса.Поскольку существует множество сетевых элементов, и их несколько типов, и каждый из них имеет разные параметры пути ... Есть ли способ автоматически генерировать набор регулярных выражений, которые каким-то образом группируют журналы?Система может учиться на исторических данных, например, за последнюю неделю.Сгенерированное регулярное выражение не должно быть очень точным, для пользователя предполагается, что это будет подсказка для добавления такого нового правила в систему.

Я думал о неконтролируемом машинном обучении, чтобы разделить входные данные на группы, а затем в каждой группе найти подходящеерегулярное выражение.Есть ли другой способ, может быть, быстрее или лучше?И, наконец, что не менее важно, как найти регулярное выражение, соответствующее всем строкам в полученной группе?(Нетривиально, поэтому .* не является ответом.)

---

Редактировать Подумав немного, я попытаюсь упростить проблему.Предположим, я уже сгруппировал логи.Я хотел бы найти (самое большее) три самые большие подстроки (хотя бы одну), общие для всех строк в наборе.Например:

Set of strings:
cron/script1.sh -abc 1243 all
cron/script2.sh 1
bin/script1.sh -asdf 15

Obtained groups:
/script
.sh 

Теперь я могу создать простое регулярное выражение, связав эти группы с .*?.В этом примере это будет .*?(/script).*?(\.sh ).*?.Вроде бы более простое решение.

Answer 1

Вы можете попробовать инструмент, размещенный на этом сайте: http://regex.inginf.units.it/

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

Answer 2

ОК, мы попытаемся разбить это на управляемые шаги.

  1. For each substring w in s1, in order of non-increasing length,
  2.  assume w is a substring of the other sM
  3.  for each string of the other sN,
  4.   if w is not a substring of sN, disprove assumption and break
  5.  if the assumption held, save w
  6.  if you've found three w that work, break
  7. You have recorded between 0 and 3 w that work.

Обратите внимание, что не все наборы строк гарантированно имеют общие подстроки (кроме пустой строки).В худшем случае предположим, что s1 - самая длинная строка.Есть O (n ^ 2) подстрок s1 (| s1 | = n), и требуется O (n), чтобы сравнить с каждой из m других строк ... так что асимптотическая сложность, я полагаю, O (n ^ 2)* nm) ... даже если алгоритм наивный, он должен быть довольно управляемым (в конце концов, полиномиальным и квадратичным).

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

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

Answer 3

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

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

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

Парсер определяет, что делать с токенами, которые мы собрали. Теперь, когда мы их анализируем, сначала делаем что-то простое. Например, добавление каждого уникального токена «name» в список с подсчетом вхождений. Если это число больше, чем, скажем, 50, мы выводим токен.

Я замял здесь мелкие детали. Прежде всего вам нужно будет определить «язык» для вашего токенизации. например, если у вас есть такие строки журнала: ipOfComputer /full/path/to/script.sh args, тогда ваш токенизатор должен понимать эти биты.

Прочтите книгу Lex и yacc , чтобы получить отличное представление о различных темах. Обратите внимание, что это не будет зависеть от ваших регулярных выражений. Это также произойдет во всем потоке, делая свое дело. Вывод этой программы станет простым регулярным выражением для добавления в файл конфигурации.