首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >对于给定的代表字符串的有限列表的正则表达式的语法推断?

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

Stack Overflow用户
提问于 2013-03-20 08:10:13
回答 1查看 2.9K关注 0票数 25

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

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

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

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

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

EN

回答 1

Stack Overflow用户

发布于 2013-03-20 21:41:31

我唯一能建议的就是试用一下Nltk (Natural Language Toolkit for Python),看看它是否至少能识别重复出现的模式。

你可以考虑的另一件事是MALLET (基于Java的包,用于统计自然语言处理、文档分类、聚类、主题建模、信息提取等)。

Perl有一种叫做LinkParser的东西,但它似乎要求您提供实际语法的表示形式(另一方面,它附带了大量不同的模型,因此可以硬塞它来帮助您对样本进行排序)。

Gate可能允许您从语料库中的记录子集创建示例,并可能从这些记录中对语法进行逆向工程。

最后,看一看CRAN repository for text-specific packages

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/15512918

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档