计算机是否可以通过用户提供的示例“学习”正则表达式？

Question

计算机是否可以通过用户提供的示例“学习”正则表达式？

澄清：

• 我做不要学习正则表达式。
• 我想创建一个程序，它可以从用户交互式提供的例子中“学习”正则表达式，也许可以通过从文本中选择部分或选择开始或结束标记。

这可能吗？ Google可以提供哪些算法，关键字等？

编辑：谢谢你的答案，但我没有兴趣在提供此功能的工具。我正在寻找理论信息，如论文，教程，源代码，算法名称，所以我可以为自己创造一些东西。

Answer 1

本书An Introduction to Computational Learning Theory包含学习有限自动机的算法。由于每种常规语言都等价于有限自动机，因此可以通过程序学习一些正则表达式。 Kearns and Valiant显示了一些不可能学习有限自动机的情况。一个相关的问题是learning hidden Markov Models，它是可以描述字符序列的概率自动机。请注意，编程语言中使用的大多数现代“正则表达式”实际上比常规语言更强，因此有时难以学习。

Answer 2

你可能想用这个网站玩了一下，这是相当凉爽，听起来就像是做类似的东西，你在说什么：http://txt2re.com

Answer 3

相信术语是“上岗”。你想引发一个正规的语法。

我不认为用一组有限的例子（正数或负数）是可能的。但是，如果我记得正确的话，如果有一个可以咨询的Oracle，就可以完成。 （基本上，你必须让程序询问用户是/否的问题，直到它的内容。）

Answer 4

如果它有可能一个人去学习正则表达式，那么它是从根本上可能的程序。但是，该程序需要正确编程才能学习。幸运的是，这是一个相当有限的逻辑空间，所以它不像教授一个程序能够看到物体或类似物体那么复杂。

Answer 5

是的，这当然是“可能的”;这里的伪代码：

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>) 
{ 
    if HasIntersection(<listOfPosExamples>, <listOfNegExamples>) 
    return <IntersectionError> 

    string regex = ""; 
    foreach(string example in <listOfPosExamples>) 
    { 
     if(regex != "") 
     { 
     regex += "|"; 
     } 
     regex += DoRegexEscaping(example); 
    } 
    regex = "^(" + regex + ")$"; 

    // Ignore <listOfNegExamples>; they're excluded by definition 

    return regex; 
} 

问题是，有无数的正则表达式将匹配的例子列表。这段代码提供了集合中最简单/最愚蠢的正则表达式，它基本上与正例中的任何东西都匹配（并且没有其他任何内容，包括任何负面例子）。

我想真正的挑战是找到与所有例子相匹配的最短正则表达式，但即使如此，用户也不得不提供非常好的输入来确保结果表达式是“正确的”。

Answer 6

@Yuval是正确的。你正在研究计算学习理论，或者“归纳推理”。“

这个问题比你想象的要复杂得多，因为”学习“的定义是非平凡的。一个常见的定义是学习者可以随时吐出答案，但最终它必须停止吐出答案，或总是吐出相同的答案，这假定有无数的输入，并且在程序达到其决定时绝对不提供任何补偿，而且，当它已经达到它的决定时，你不能分辨它是什么，因为它可能仍然输出不同的东西以后。

根据这个定义，我敢肯定，正规语言是可以学习的。其他的定义，没有那么多...

Answer 7

没有计算机编程的， m将永远能够在有效匹配列表上生成一个基于的纯粹的有意义的正则表达式。让我告诉你为什么。

假设你提供的实施例中111111和999999，应在计算机生成：

1. 甲正则表达式匹配恰好这两个例子：(111111|999999)
2. 甲正则表达式匹配的6个相同数字(\d)\1{5}
3. 甲正则表达式匹配的6一个和九个[19]{6}
4. 匹配任意6位数的正则表达式\d{6}
5. 任何三个以上，具有单词边界，例如， \b\d{6}\b
6. 前三位中的任何一位，前面或后面都没有数字，例如， (?<!\d)\d{6}(?!\d)

正如你可以看到，有许多方法在这些实例可以概括为正则表达式。计算机构建可预测的正则表达式的唯一方法是要求您列出全部可能的匹配项。然后它可以生成一个匹配那些匹配的搜索模式。

如果您不想列出所有可能的匹配项，则需要更高级别的说明。这正是正则表达式旨在提供的。您只需告诉程序匹配“任意六位数字”，而不是提供6位数字的长列表。在正则表达式语法中，这变成\ d {6}。

任何提供与正则表达式一样灵活的更高级别描述的方法也将与正则表达式一样复杂。像RegexBuddy这样的所有工具都可以使创建和测试高级描述更容易。直接使用简洁的正则表达式语法，RegexBuddy使您可以使用简单的英语构建块。但它不能为你创建高级描述，因为它不能神奇地知道它应该什么时候推广你的例子，什么时候不应该。

当然可以创建一个工具，使用示例文本以及用户提供的指导原则来生成正则表达式。设计这种工具的难点在于它如何向用户询问所需的指导信息，而不会使工具比正则表达式本身更难学习，并且不会将工具限制为普通的正则表达式工作或简单的正则表达式。

Answer 8

有一种语言致力于这样的问题，基于prolog。它被称为progol。

正如其他人所提到的，其基本思想是归纳学习，在AI界通常被称为ILP（inductive logic programming）。

第二个链接是关于ILP的wiki文章，其中包含许多有用的源材料，如果您有兴趣了解更多关于该主题的内容。

Answer 9

我已经做了谷歌和CiteSeer一些研究，发现这些技术/论文：

• Language identification in the limit
• Probably approximately correct learning

而且戴纳·安格卢的“学习从查询和反例规则集”似乎很有前途，但我无法找到PS或PDF版本，只能引用和研讨会论文。

即使在理论层面上，这似乎也是一个棘手的问题。

Answer 10

是的， 有可能， 我们可以从例子（文本 - >所需的提取）中生成正则表达式。 这是一个在线工具，它可以完成这项工作：http://regex.inginf.units.it/

正则表达式++在线工具通过使用GP搜索算法提供的示例生成正则表达式。 GP算法由多目标适应度驱动，导致更高的性能和更简单的解决方案结构（Occam's Razor）。 这个工具是由里雅斯特大学的机器勒维实验室（Universitàdegli studi di Trieste）提供的一种应用。 请看视频教程here。

这是一个研究项目，所以你可以阅读关于使用的算法here。

看哪！ :-)

寻找从一个例子的正则表达式有意义/溶液是可能当且仅当所提供的实施例描述了问题良好。 考虑这些描述提取任务的例子，我们正在寻找特定的物品代码;的实例是文本/提取对：

"The product code il 467-345A" -> "467-345A" 
"The item 789-345B is broken" -> "789-345B" 

的（人）的人，着眼于实施例，可以说--ie： “的项目代码之类的东西\ d ++ - 345 [AB]”

当物品代码更宽容但我们没有提供其他例子时，我们没有证据可以很好地理解问题。 当将人类产生的解\ d ++ - 345 [AB]以下内容的文本，它失败：

"On the back of the item there is a code: 966-347Z" 

你必须提供其它实例中，为了更好地描述什么是匹配的，哪些是不所需的匹配： --ie：

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z" 

的电话号码是不是一个产品ID，这可能是一个重要的证明。