计算机是否可以通过用户提供的示例“学习”正则expression式？
计算机是否可以通过用户提供的示例“学习”正则expression式？
澄清：
- 我不想学习正则expression式。
- 我想创build一个程序，从用户交互提供的例子中“学习”一个正则expression式，也许从文本中select部分或select开始或结束标记。
可能吗？ 是否有algorithm，关键字等我可以谷歌？
编辑 ：谢谢你的答案，但我对提供此function的工具不感兴趣。 我正在寻找理论信息，如论文，教程，源代码，algorithm名称，所以我可以为自己创造一些东西。
“ 计算学习理论导论 ”一书包含了学习有限自动机的algorithm。 由于每一个正则语言都等价于一个有限自动机，所以可以通过一个程序来学习一些正则expression式。 Kearns和Valiant展示了一些不可能学习有限自动机的情况。 一个相关的问题是学习隐马尔可夫模型 ，这是可以描述字符序列的概率自动机。 请注意，在编程语言中使用的大多数现代“正则expression式”实际上比常规语言更强，因此有时难以学习。
没有计算机程序将永远只能根据有效的匹配列表生成一个有意义的正则expression式。 让我告诉你为什么。
假设你提供了例子111111和999999，如果计算机产生：
- 正则expression式匹配这两个例子：
(111111|999999) - 一个匹配6个相同数字
(\d)\1{5}正则expression式 - 匹配6个和9个正则expression式
[19]{6} - 一个正则expression式匹配任何6位
\d{6} - 以上三种中的任何一种，带有单词边界，例如
\b\d{6}\b - 前三位中的任何一位，前后都没有数字，例如
(?<!\d)\d{6}(?!\d)
正如你所看到的，有很多方法可以将例子推广到正则expression式中。 计算机构build可预测的正则expression式的唯一方法是要求您列出所有可能的匹配项。 然后它可以生成一个匹配那些匹配的search模式。
如果您不想列出所有可能的匹配项，则需要更高级别的说明。 这正是正则expression式旨在提供的。 而不是提供一个长长的6位数字列表，你只需告诉程序匹配“任何六位数字”。 在正则expression式语法中，这变成\ d {6}。
提供与正则expression式一样灵活的更高级别描述的任何方法也将与正则expression式一样复杂。 像RegexBuddy所能做的所有工具就是使创build和testing高级描述更容易。 直接使用简洁的正则expression式语法，RegexBuddy使您可以使用简单的英语构build块。 但是它不能为你创build高级描述，因为它不能神奇地知道什么时候应该推广你的例子，什么时候不应该。
当然可以创build一个工具，使用示例文本以及用户提供的指导来生成正则expression式。 devise这样的工具的难点在于如何向用户询问所需的指导信息，而不会使工具比正则expression式本身难于学习，并且不会将工具限制为普通的正则expression式工作或简单的正则expression式。
是的，这是可能的，我们可以从例子（文本 – >所需的提取）生成正则expression式。 这是一个在线工具，可以完成这个工作： http : //regex.inginf.units.it/
正则expression式生成器++在线工具使用GPsearchalgorithm从提供的示例生成正则expression式。 GPalgorithm由多目标适应性驱动，导致更高的性能和更简单的解决scheme结构（Occam's Razor）。 这个工具是Trieste Univeristy机器学院（里雅斯特大学）的一个实用的应用程序。 请看这里的video教程。
这是一个研究项目，所以你可以在这里阅读关于使用的algorithm。
看哪！ 🙂
从实例中find一个有意义的正则expression式/解决scheme是可能的， 当且仅当提供的例子很好地描述了这个问题。 考虑这些描述提取任务的例子，我们正在寻找特定的物品代码; 示例是文本/提取对：
"The product code il 467-345A" -> "467-345A" "The item 789-345B is broken" -> "789-345B"
一个（人）的人，看着这个例子，可能会说–ie：“物品代码就是\ d ++ – 345 [AB]”
当项目代码更宽容，但我们没有提供其他的例子，我们没有证据很好地理解这个问题。 将以下文本应用于人工生成的解决scheme\ 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"
电话号码i不是产品ID，这可能是一个重要的证据。
是的，这当然是“可能的”; 这里是伪代码：
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; }
问题是，有无数的正则expression式会匹配一个例子列表。 这段代码提供了最简单/最愚蠢的正则expression式，基本上匹配正例中的任何东西（除此之外没有其他的东西，包括任何负面的例子）。
我认为真正的挑战是find与所有例子相匹配的最短正则expression式，但即使如此，用户也不得不提供非常好的input，以确保得到的expression式是“正确的”。
你可能想玩一下这个网站，这很酷，听起来像是和你在说的东西类似： http : //txt2re.com
我相信这个词是“归纳”。 你想诱导一个正规的语法。
我不认为用一组有限的例子（正面或负面）是可能的。 但是，如果我记得正确的话，如果有一个可以咨询的Oracle，就可以做到。 （基本上，你必须让程序询问用户是/否问题，直到它的内容。）
基于prolog，有一种专门用于这样的问题的语言。 这就是所谓的progol 。
正如其他人所提到的，其基本思想是归纳学习，通常称为AI圈子中的ILP（ 归纳逻辑编程 ）。
第二个链接是关于ILP的wiki文章，如果您有兴趣了解更多关于这个主题的内容，那么它将包含许多有用的资料。
@Yuval是正确的。 你正在研究计算学习理论，或者“归纳推理”。
这个问题比你想象的要复杂得多，因为“学习”的定义是不平凡的。 一个普遍的定义是，学习者可以随时吐出答案，但最终必须停止吐出答案，或者始终吐出相同的答案。 这假定了无数的input，并且绝对不会提供什么时候该计划将达到其决定。 而且，你不能分辨它什么时候做出了决定，因为它可能会在以后输出不同的东西。
通过这个定义，我很确定正规语言是可以学习的。 通过其他定义，不是很多…
我对Google和CiteSeer做了一些研究，发现了这些技术/论文：
- 语言识别的极限
- 大概大概正确的学习
Dana Angluin的“从查询和反例学习常规集”看起来很有希望，但是我找不到PS或PDF版本，只能引用和研讨会论文。
这似乎是一个棘手的问题，即使在理论层面上。
如果一个人可以学习一个正则expression式，那么对一个程序来说，这是基本可能的。 但是，该程序需要正确编程才能学习。 幸运的是，这是一个相当有限的逻辑空间，所以它不像教授一个程序能够看到物体或类似的东西那么复杂。
