自动构建适合字符串集的正则表达式

Question

我们编写了系统来分析来自大型网络的日志消息.系统从许多不同的网络元素中获取日志消息,并通过正则表达式进行分析.例如,用户可能已经编写了两条规则:

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

在这种情况下,只会选择与给定模式匹配的日志.过滤的原因是可能存在大量日志消息,每天最多1 GB.

现在是我问题的主要部分.因为有很多网络元素,以及它们的几种类型,并且它们中的每一个在路径中都有不同的参数...有没有办法自动生成一组以某种方式对日志进行分组的正则表达式？系统可以学习历史数据,例如从上周开始.生成的正则表达式必须非常准确,它应该是用户将这种新规则添加到系统中的提示.

我正在考虑无监督机器学习将输入分成组,然后在每组中找到正确的正则表达式.还有其他方式,可能更快或更好吗？并且,最后但并非最不重要的,如何找到匹配所有组中的所有字符串的正则表达式？(非平凡,所以.*不是答案.)

---

编辑经过一番思考后,我会尝试简化问题.假设我已经分组了日志.我想(最多)找到集合中所有字符串共有的三个最大子串(至少一个).例如:

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 是最长的字符串。s1 (|s1| = n) 有 O(n^2) 个子串，与 m 个其他字符串中的每一个进行比较需要 O(n)...所以我相信渐近复杂度是 O(n^2 * nm）...尽管算法很简单，但这应该是相当容易管理的（毕竟是多项式，而且是二次项）。

转换为例如 C 代码应该很简单......使用带有递减长度循环的滑动窗口来获取 s1 的子字符串，然后使用线性搜索器来查找其他字符串中的匹配项。

我确信有更智能/渐近更好的方法可以做到这一点，但是任何算法都必须查看所有字符串中的所有字符，因此 O(nm)... 可能不完全正确。