创建一个字符串列表的正则表达式

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这个网站似乎是互动的。

注：我注意到投票结束为“过于本地化”。这是一个非常普遍的问题（表中给出的仅仅是一个例子），正如Google/Freebase开发Refine所示，以解决这个问题。它可能涉及各种各样的表格（例如金融，新闻等）。这里有一个浮点值：

自动确定某些权威机构实时报告年龄（例如不是几个月，几天）并使用2位数的精度将是有用的。

Answer 1

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

这个演示编程的特例似乎与MSR最近的一个项目Flash Fill密切相关。在那里，代替匹配数据生成正则表达式，它们自动生成程序变换基于输入/输出示例的字符串数据。

我只通过one他们的论文，但我会试着阐述我在这里理解的东西。

本文中基本上有两个重要的见解。首先是设计一个小型编程语言来表示字符串转换。即使使用全功能正则表达式，也可以快速搜索到太多可能性。他们设计了自己的抽象语言来操作字符串;然而，您的约束（例如，只使用简单的量词）可能会起到与其自定义语言相同的作用。这在很大程度上是可能的，因为您的特定问题的范围比他们的范围稍小。

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

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

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

Answer 2

我自己的方法（我已部分原型化）是启发式的，并且基于给定列经常具有相同或相似字符长度且具有类似标点符号的条目的前提。我会欢迎评论（并由此产生的代码将为开源）。

1. 弄平[A-Z]到'A'
2. 弄平[a-z]到'a'
3. 弄平[0-9]到'0'
4. 弄平任何其它特殊的码点集（例如希腊字符）为单个字符（例如字母）

然后列成为：

1. "AAA"
2. "Aaaaaaaaaa", "Aaaaaaaaaaaaa", "Aaa aaa Aaaaaa"等
3. "0000 a"
4. "00\u00b000'00"N,00\u00b000'00"E
5. ...
6. ...
7. “0000”

我可以将取代这些通过正则表达式suc H作为

1. "([A-Z])([A-Z])([A-Z])"
2. ...
3. "(\d)(\d)(\d)(\d)\s([0-9])"

，并捕获单个字符成组。这将显示（说）在3。最终字符总是"m"，所以\d\d\d\d\s[m]和7.值为[2][0][0][458]。

对于不适合此模型的列，我们使用"(.*)"进行搜索，并查看我们是否可以创建有用的集合（第5列和第6列），如“至少2个多个字符串且不超过50个％独特的字符串“。

通过使用动态规划（参见克鲁斯卡）我希望能够对准类似的正则表达式，这将是有用的对我来说，至少！

Answer 3

我目前正在研究相同的（或类似的）（here）。通常，这称为Grammar induction，或者在正则表达式的情况下，它是induction of regular languages。关于这个领域有StaMinA competition。常用算法是RPNI和Blue-Fringe。

Here是另一个相关的问题。而另一个是here。另外还有here。