Ste*_*Lin 21 regex language-agnostic grammar automata dfa
我正在分析一个大型公共数据集,其中包含大量冗长的人类可读字符串,这些字符串是由一些常规(在形式语言理论意义上)语法明确生成的.
一个接一个地查看这些字符串集来查看模式并不太难; 不幸的是,大约有24,000个这些独特的字符串分为33个类别和1714个子类别,因此手动执行此操作有点痛苦.
基本上,我正在寻找一个现有的算法(最好使用现有的参考实现)来获取任意的字符串列表,并尝试推断一些可用于生成的正则表达式的最小化(对于一些合理的最小化定义)它们(即从该语法生成的语言中推导出一组有限字符串中的常规语法).
我已经考虑过重复贪婪最长的常见子串消除,但这只是到目前为止,因为除了完全匹配之外它不会崩溃,所以不会检测到,例如,在特定位置的变化数字串的常见模式语法.
暴力强迫任何不会脱离常见子串消除的东西是可能的,但可能在计算上不可行.(另外,我想过这个问题,有可能是一个"阶段排序"和/或子淘汰"当地最低"的问题,因为你可能会做出最终迫使最终语法贪婪的字符串匹配要少压缩/即使它看起来是最好的减少最小).
Ste*_*Lin 21
是的,事实证明这确实存在; 所需要的是学术上称为DFA学习算法的例子,其中的例子包括:
上面的源代码是libalf,一个C++中的开源自动机学习算法框架; 至少其中一些算法的描述可以在本教科书中找到.在gitoolbox for MATLAB 中也有语法推理算法(包括DFA学习)的实现.
由于这个问题以前出现过,而且过去没有得到满意的答复,我正在评估这些算法,并将更新更多关于它们有用的信息,除非在该领域有更多专业知识的人先做(是优选的).
注意:我现在接受我自己的答案,但如果有人可以提供答案,我很乐意接受更好的答案.
进一步说明:我决定采用自定义代码的路线,因为使用通用算法对我正在使用的数据来说有点过分.我将这个答案留在这里以防其他人需要它,并且如果我做过评估,我会更新.