我正在分析一个大型公共数据集,其中包含大量冗长的人类可读字符串,这些字符串是由一些常规(在形式语言理论意义上)语法明确生成的.
一个接一个地查看这些字符串集来查看模式并不太难; 不幸的是,大约有24,000个这些独特的字符串分为33个类别和1714个子类别,因此手动执行此操作有点痛苦.
基本上,我正在寻找一个现有的算法(最好使用现有的参考实现)来获取任意的字符串列表,并尝试推断一些可用于生成的正则表达式的最小化(对于一些合理的最小化定义)它们(即从该语法生成的语言中推导出一组有限字符串中的常规语法).
我已经考虑过重复贪婪最长的常见子串消除,但这只是到目前为止,因为除了完全匹配之外它不会崩溃,所以不会检测到,例如,在特定位置的变化数字串的常见模式语法.
暴力强迫任何不会脱离常见子串消除的东西是可能的,但可能在计算上不可行.(另外,我想过这个问题,有可能是一个"阶段排序"和/或子淘汰"当地最低"的问题,因为你可能会做出最终迫使最终语法贪婪的字符串匹配要少压缩/即使它看起来是最好的减少最小).
用于从一组被认为是由通用语法生成的示例中进行常规或上下文无关语法推理的最佳（或任何）开源库是什么？我更喜欢 Java、Python 或 Ruby 的优秀库，但乞丐当然不能挑剔。
我做了一些谷歌搜索，但找不到任何实际的实现，尽管我确实找到了很多有趣的参考资料。 这个库看起来很有趣，但我找不到可以在任何地方下载的地方。
编辑（2011-11-14）：为了清楚起见（虽然我不确定你们是如何误解的），问题是关于语法推理，而不是语法生成或解析。换句话说，给定一组符合未知语法的字符串，找到它们都满足的最严格的语法。