相关疑难解决方法(0)

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

一个接一个地查看这些字符串集来查看模式并不太难; 不幸的是,大约有24,000个这些独特的字符串分为33个类别和1714个子类别,因此手动执行此操作有点痛苦.

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

我已经考虑过重复贪婪最长的常见子串消除,但这只是到目前为止,因为除了完全匹配之外它不会崩溃,所以不会检测到,例如,在特定位置的变化数字串的常见模式语法.

暴力强迫任何不会脱离常见子串消除的东西是可能的,但可能在计算上不可行.(另外,我想过这个问题,有可能是一个"阶段排序"和/或子淘汰"当地最低"的问题,因为你可能会做出最终迫使最终语法贪婪的字符串匹配要少压缩/即使它看起来是最好的减少最小).

我从科学文献中提取了一系列表格,这些表格由列组成,每列都是不同的类型.这是一个例子

我希望能够为每列自动生成正则表达式.显然有一些简单的解决方案,.*所以我会添加他们只使用的约束:

• [A-Z] [a-z] [0-9]
• 明确标点符号(如',',''')
• "简单"量词(例如 {3,4}

上表的"最佳"答案是:

 [A-Z]{3}
 [A-Za-z\s\.]+
 \d{4}\sm
 \d{2}\u00b0\d{2}'\d{2}"N,\d{2}\u00b0\d{2}'\d{2}"E
 (speciosissima|intermediate|troglodytes)
 (hf|sr)
 \d{4}

当然,如果我们移出地理区域,第四个正则表达式会破裂,但软件不知道这一点.目的是收集许多正则表达式,比如说"坐标"并概括它们,可能是部分手动的.仅当存在少量不同的字符串时才会创建枚举.

我很感激能够做到这一点的(特别是F/OSS)软件的例子,特别是在Java中.(它类似于Google的Refine).我4年前就知道这个问题了,但这并没有真正回答问题和text2re网站似乎是互动的.

注意:我注意到投票结束为"过于本地化".这是一个非常普遍的问题(给出的表只是一个例子),正如Google/Freebase开发的Refine解决这个问题所示.它可能涉及各种各样的表格(例如财务,新闻等).这是一个浮点值:

自动确定某些权威机构报告实际年龄(例如,不是几个月,几天)并使用2位数的精确度将是有用的.