regex - 对于给定的有限代表字符串列表，正则表达式的语法推理？

Question

我正在分析一个大型公共(public)数据集，其中包含许多详细的人类可读字符串，这些字符串显然是由某些常规(在形式语言理论意义上)语法生成的。

逐一查看这些字符串集以了解其中的模式并不难；不幸的是，大约有 24,000 个独特的字符串被分为 33 个类别和 1714 个子类别，因此手动执行此操作有点痛苦。

基本上，我正在寻找一种现有的算法(最好使用现有的引用实现)来获取任意字符串列表，并尝试推断出一些最小的(对于最小)跨越正则表达式集的一些合理定义，可用于生成它们(即从该语法生成​​的语言的有限字符串集中推断正则语法)。

我考虑过重复进行贪婪的最长公共(public)子串消除，但这只能到此为止，因为它不会崩溃除了精确匹配之外的任何内容，因此不会检测到特定的不同数字字符串的常见模式在语法中的位置。

暴力破解任何不属于公共(public)子串消除范围的东西都是可能的，但在计算上可能不可行。 (此外，我已经考虑过，子字符串消除可能存在“阶段排序”和/或“局部最小值”问题，因为您可能会进行贪婪的子字符串匹配，最终迫使最终语法压缩得更少/最小，尽管它最初似乎是最好的减少)。

Answer 1

是的，事实证明这确实存在；所需要的是学术上所谓的DFA 学习算法，其示例包括:

• Angluin 的 L*
• L*(向列中添加反例)
• 卡恩斯/瓦齐拉尼
• 里维斯特/夏 PIL
• 荷兰*
• 常规正负推理 (RPNI)
• DeLeTe2
• Biermann 和 Feldman 算法
• Biermann & Feldman 算法(使用 SAT 求解)

上述来源为libalf ，一个开源的C++自动机学习算法框架；至少其中一些算法的描述可以在 this textbook 中找到。等。 gitoolbox中也有语法推理算法(包括DFA学习)的实现对于 MATLAB。

自 this question has come up before并且过去没有得到令人满意的答案，我正在评估这些算法，并将更新更多关于它们有多有用的信息，除非在该领域具有更多专业知识的人首先这样做(这是更好的选择)。

_{注意:我现在接受我自己的答案，但如果有人可以提供更好的答案，我会很乐意接受。}

_{进一步说明:我决定采用使用自定义代码的路线，因为使用通用算法对于我正在使用的数据来说有点矫枉过正。我将这个答案留在这里，以防其他人需要它，并且如果我评估这些答案，我会更新。}