正则表达式 – 给定有限列表的代表性字符串的正则表达式的语法推
|
我正在分析一个大量的公开数据集，其中包含许多详细的人类可读的字符串，这些字符串由一些常规(正式语言理论意义上的)语法产生。
仔细观察这些字符串是不是太难看了，不幸的是，这些独特的字符串中有大约24,000个分为33个类别和1714个子类别，所以手动执行有点痛苦。 基本上，我正在寻找一个现有的算法(最好用现有的参考实现)来获取一个任意的字符串列表，并尝试推断一些可用于生成的正则表达式的最小值(对于一些合理的最小定义)他们(即从该语法产生的语言从有限的一组字符串推断出正则语法)。 我已经考虑过反复贪婪最长的常见子字符串消除，但是只有这么远，因为它不会崩溃任何东西，但完全匹配，所以不会检测到，在一个特定的位置上变化的数字字符串的共同模式语法。 强制强制任何不会脱离常见子字符串消除的内容是可能的，但可能在计算上是不可行的。 (此外，我已经考虑过了，可能有一个“相序”和/或“本地最小”问题与子字符串消除，因为你可能会做一个贪婪的子串匹配，最终强制最终的语法被压缩/尽管它最初似乎是最好的减少)。
是的，事实证明这确实存在;所需要的是在学术上被称为DFA学习算法的知识，其示例包括：
> Angluin的L * 以上的源代码是libalf，C中的开源自动机学习算法框架;至少有一些这些算法的描述可以在this textbook中找到。在gitoolbox中还有用于MATLAB的语法推理算法(包括DFA学习)的实现。 自07年以来，过去并没有得到令人满意的回答，我正在评估这些算法，并将更新有关它们有用的更多信息，除非在该地区具有更多专业知识的人才是首选(最好的)。 注意：我现在接受我自己的答案，但如果有人可以提供一个，我会乐意接受一个更好的答案。 另外注意：我决定使用自定义代码的路由，因为使用通用算法对我正在使用的数据来说有点过分。我在这里留下这个答案，以防其他人需要它，如果我做了这些评估，将会更新。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |