我正在分析一个大型公共数据集,其中包含大量冗长的人类可读字符串,这些字符串显然是由一些常规(在形式语言理论意义上)语法生成的。
一个接一个地查看这些字符串的集合并不难看出模式;不幸的是,大约有24,000个这样的独特字符串被分成33个类别和1714个子类别,所以手动完成这项工作有点痛苦。
基本上,我正在寻找一个现有的算法(最好有一个现有的参考实现)来获取任意的字符串列表,并尝试来推断出一些可以用来生成它们的最小(对于最小的合理定义)生成正则表达式的集合(即,从由该语法生成的语言的有限字符串集合中推断出一个正则语法)。
我曾考虑过重复进行贪婪的最长公共子字符串消除,但这只能做到这一点,因为它不会折叠除了精确匹配之外的任何东西,所以不会检测到,比如说,在语法中的特定位置上变化的数字字符串的常见模式。
暴力强制任何不属于公共子串消除的东西都是可能的,但在计算上可能是不可行的。(此外,我考虑过这个问题,子字符串消除可能存在“阶段排序”和/或“局部最小值”问题,因为您可能会进行贪婪的子字符串匹配,最终迫使最终语法压缩/最小化,即使它最初看起来是最好的缩减)。
发布于 2013-03-20 21:41:31
我唯一能建议的就是试用一下Nltk (Natural Language Toolkit for Python),看看它是否至少能识别重复出现的模式。
你可以考虑的另一件事是MALLET (基于Java的包,用于统计自然语言处理、文档分类、聚类、主题建模、信息提取等)。
Perl有一种叫做LinkParser的东西,但它似乎要求您提供实际语法的表示形式(另一方面,它附带了大量不同的模型,因此可以硬塞它来帮助您对样本进行排序)。
Gate可能允许您从语料库中的记录子集创建示例,并可能从这些记录中对语法进行逆向工程。
https://stackoverflow.com/questions/15512918
复制相似问题