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

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

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

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

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

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

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

• 安格鲁因 L*
• L*（向列中添加反例）
• 卡恩斯/瓦齐拉尼
• 里维斯特/夏皮尔
• NL*
• 正负推理（RPNI）
• DeLeTe2
• Biermann & Feldman 算法
• Biermann & Feldman 算法（使用 SAT 求解）

上述内容的来源是libalf http://libalf.informatik.rwth-aachen.de/，一个开源的C++自动机学习算法框架；至少其中一些算法的描述可以在这本教科书 https://rads.stackoverflow.com/amzn/click/com/0521763169等。还有语法推理算法（包括DFA学习）的实现吉工具箱 https://code.google.com/p/gitoolbox/对于 MATLAB。

Since 这个问题以前曾出现过 https://stackoverflow.com/questions/5958483/grammar-inference-library并且过去没有得到令人满意的答案，我正在评估这些算法，并将更新更多关于它们有多有用的信息，除非在该领域具有更多专业知识的人首先这样做（这是更好的选择）。

_{NOTE: I am accepting my own answer for now but will gladly accept a better one if someone can provide one.}

_{FURTHER NOTE: I've decided to go with the route of using custom code, since using a generic algorithm turns out to be a bit overkill for the data I'm working with. I'm leaving this answer here in case someone else needs it, and will update if I ever do evaluate these.}