regex - 为字符串列表创建正则表达式

Question

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

我希望能够为每一列自动生成正则表达式。显然有诸如.*之类的微不足道的解决方案。所以我会添加他们只使用的约束:

[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)。我知道 this question 4 years ago但这并没有真正回答问题和 text2re看起来是交互式的站点。

注意:我注意到投票结束“过于本地化”。这是一个非常普遍的问题(给出的表格只是一个例子)，如谷歌/Freebase 开发 Refine 来解决这个问题所示。它可能指的是非常广泛的表格(例如金融、新闻等)。这是一个带有浮点值的:


自动确定某些当局以实数(例如，不是月、日)报告年龄并使用 2 位精度会很有用。

Answer 1

您的特定问题是“演示编程”的特例。也就是说，给定一堆输入/输出示例，您想要生成一个程序。对您来说，输入是字符串，输出是每个字符串是否属于给定列。最后，您希望使用您提出的有限正则表达式语言生成一个程序。

这个通过演示编程的特殊实例似乎与 Flash Fill 密切相关。 ，MSR 最近的一个项目。在那里，他们不是生成正则表达式来匹配数据，而是根据输入/输出示例自动生成程序来转换字符串数据。

我只是浏览了一下 one他们的论文，但我会尽量在这里列出我的理解。

这篇论文基本上有两个重要的见解。第一个是设计一种小型编程语言来表示字符串转换。即使使用完整的正则表达式也创造了太多快速搜索的可能性。他们设计了自己的抽象语言来处理字符串；但是，您的约束(例如仅使用简单的量词)可能会与他们的自定义语言发挥相同的作用。这在很大程度上是可能的，因为您的特定问题的范围比他们的要小一些。

第二个见解是如何在这种抽象语言中实际找到与给定输入/输出对匹配的程序。我的理解是这里的关键思想是使用一种叫做 version space algebra 的技术。 .关于版本空间代数的粗略想法是，您维护可能程序空间的表示，并通过引入附加约束反复修剪它。这个过程的确切细节远远超出了我的主要兴趣，所以你最好阅读这样的内容 introduction to version space algebra ，其中还包括一些示例代码。

他们还有一些聪明的方法来对不同的候选程序进行排名，甚至猜测哪些输入可能对已经生成的程序有问题。我看到一个演示，他们在没有给它足够的输入/输出对的情况下生成了一个程序，该程序实际上可以突出显示可能不正确的新输入。这种排名非常有趣，但需要一些更复杂的机器学习技术，并且可能不会立即适用于您的用例。不过可能仍然很有趣。 (此外，这可能在与我链接的论文不同的论文中详细说明。)

是的，长话短说，您可以通过将输入/输出示例输入到基于版本空间代数的系统中来生成表达式。我希望这有帮助。