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

EN

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

一个接一个地查看这些字符串的集合并不难看出模式；不幸的是，大约有24,000个这样的独特字符串被分成33个类别和1714个子类别，所以手动完成这项工作有点痛苦。

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

我曾考虑过重复进行贪婪的最长公共子字符串消除，但这只能做到这一点，因为它不会折叠除了精确匹配之外的任何东西，所以不会检测到，比如说，在语法中的特定位置上变化的数字字符串的常见模式。

暴力强制任何不属于公共子串消除的东西都是可能的，但在计算上可能是不可行的。(此外，我考虑过这个问题，子字符串消除可能存在“阶段排序”和/或“局部最小值”问题，因为您可能会进行贪婪的子字符串匹配，最终迫使最终语法压缩/最小化，即使它最初看起来是最好的缩减)。