5

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

我希望能够为每一列自动生成正则表达式。显然有一些简单的解决方案，例如，.*我将添加它们仅使用的约束：

  • [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}

当然，如果我们移出地理区域，第 4 个正则表达式会中断，但软件不知道这一点。目的是收集许多正则表达式，比如“坐标”并概括它们，可能部分是手动的。只有当有少量不同的字符串时才会创建枚举。

我会很感激可以做到这一点的（尤其是 F/OSS）软件的例子，尤其是在 Java 中。（类似于 Google 的 Refine）。我在4 年前就知道这个问题，但这并没有真正回答这个问题，而且text2re网站似乎是交互式的。

注意：我注意到投票结束为“过于本地化”。这是一个非常普遍的问题（给出的表格只是一个例子），正如 Google/Freebase 开发 Refine 来解决这个问题所展示的那样。它可能指代非常广泛的表格（例如金融、新闻等）。这是一个浮点值： 在此处输入图像描述

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

4

3 回答 3

2

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

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

我只浏览了他们的一篇论文，但我会尝试在这里列出我所理解的内容。

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

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

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

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

于 2013-05-11T22:25:57.943 回答
1

我目前正在研究相同的（或类似的）（这里）。通常，这称为语法归纳，或者在正则表达式的情况下，它是正则语言的归纳。有关于这个领域的StaMinA 比赛。常见的算法有 RPNI 和 Blue-Fringe。

这是另一个相关的问题。这里还有一个。这里还有一个。

于 2014-02-25T16:02:22.433 回答
1

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

  1. 变平[A-Z]为'A'
  2. 变平[a-z]为'a'
  3. 变平[0-9]为'0'
  4. 将任何其他特殊代码点集（例如希腊字符）展平为单个字符（例如 alpha）

然后列变为：

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

然后我将用正则表达式替换这些，例如

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

并将单个角色捕获到集合中。这将表明（比方说）在 3. 最后的 char 总是"m"，所以\d\d\d\d\s[m]对于 7. 值是[2][0][0][458]。

对于不适合此模型的列，我们使用搜索"(.*)"并查看是否可以创建有用的集合（第 5 列和第 6 列），例如“至少 2 个多个字符串且不超过 50% 的唯一字符串”之类的启发式方法。

通过使用动态编程（cf. Kruskal），我希望能够对齐相似的正则表达式，这至少对我有用！

于 2013-05-13T09:59:08.323 回答