自动生成适合一组字符串的正则表达式

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 ).*?。这似乎是一个更简单的解决方案。

- Archie

---

棘手的问题。鉴于一个由正则表达式领域顶尖专家编写的工具仍需要很多用户交互，这可能相当不容易：请参见 http://www.regexmagic.com - Tim Pietzcker

有一个简单的证明，对于任何有限字符串集合，都存在无限数量的正则表达式可以匹配它们，因此是一个非平凡的任务。 - hamstergene

我相信可能有一些启发式算法可以找到正则表达式。它不必是完整的正则表达式；我认为只要找到一组常见的子字符串，然后用 .*? 连接起来就足够了。 - Archie

这个问题定义得不够清晰。使用正则表达式匹配单词 w1、w2、……、wN，最严格的匹配方式是将它们依次相连，而最宽松的方式则是使用 E*。你想要一个介于两者之间的匹配方式？随你挑选。 - Patrick87

可能是Is it possible for a computer to "learn" a regular expression by user-provided examples?的重复问题。 - Anderson Green

Answer 1

您可以尝试使用此站点提供的工具：http://regex.inginf.units.it/。

该工具能够根据示例自动生成正则表达式，因此非常适合您的用例。 网站上还详细介绍了它的工作原理（基于遗传编程）。

- Marco Mauri

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有O(n^2)个子串（|s1|=n），需要O(n)的时间与其他m个字符串进行比较... 因此渐进复杂度应该是O(n^2 * nm)... 即使算法很朴素，这也应该是相当可管理的（毕竟是多项式，而且是二次的）。

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

我相信有更聪明/渐进更好的方法来完成这个任务，但任何算法都必须查看所有字符串中的所有字符，所以O(nm)...可能并不完全正确。

- Patrick87

---

这里需要解决的问题被称为“正则语言归纳”。(https://en.wikipedia.org/wiki/Induction_of_regular_languages) - Anderson Green

Answer 3

从简单的角度来看，你可以通过使用或（用管道符号|表示）将所有字符串连接起来，为给定的一组字符串构建一个正则表达式模式。如果你想要一个更短、更优化的模式，你可以从这组字符串中创建一个Trie树，然后再构建一个正则表达式。例如，请参考trieregex。

- Mr.

Answer 4

在我看来，你试图做的事情似乎是正则表达式无法完成的。正则表达式只能从输入中识别出标记，仅此而已。其余的程序需要确定输入来源、如何分组以及如何处理获取到的标记。

所以，让我们从头开始。你有一个由各种不同网络位置的日志事件组成的输入流。将其抽象化后，我们得到一个单一的文本流。请参考this website，了解如何使用Python简化方式实现这一点的示例。

既然我们有了文本，我们想要将其分成逻辑组。这就是你的正则表达式所用之处，尽管我们真正应该使用完整的词法分析器。这些标记进入代码的解析器部分。

解析器确定我们收集到的标记应该执行什么操作。现在我们可以先进行一些简单的分析，例如将每个唯一的“名称”标记添加到列表中，并计算出出现次数。如果此数字大于50，则输出该标记。

我在这里略过了细节。主要的是，你需要确定一个用于分词的“语言”。例如，如果你有像这样的日志字符串：ipOfComputer /full/path/to/script.sh args，那么你的分词器需要理解这些部分。

阅读Lex和yacc这本书，它对涉及的各种主题有很好的介绍。请注意，这将独立于用户的正则表达式位。它也会在整个流上执行其操作。该程序的输出将成为添加到配置文件中的简单正则表达式。

- Spencer Rathbun