是否有可能为计算机"学习"一个定期表达的用户提供的例子吗？

StackOverflow https://stackoverflow.com/questions/616292

题

是否有可能为计算机"学习"一个定期表达的用户提供的例子吗？

为了澄清：

  • 我这样做 不 想学习正规的表达。
  • 我想要创造一个节目"学习"一个定期表达的实例是以交互方式提供一个用户，也许通过选择的部分从文字或选择开始或结束的标记。

这可能吗？有没有算法、关键词等。我可以谷歌？

编辑:谢谢你的答案，但我不感兴趣的工具， 提供 这一特征。我在寻找理论信息，像文件，教程，源代码，名称算法，这样我就可以创造的东西我自己。

有帮助吗？

解决方案

这本书 介绍计算的学习理论 包含一个算法为学习的一个有限的自动机。为每一个正规语言是相当于一个有限的自动机的，它是可以学到一些经常表达的程序。 柯恩斯和英勇 显示一些情况下，它不是可以学习一种有限的自动机。一个相关的问题是 学习隐马模型, ，这是概率性的自动机，可以描述一字符序列。请注意，大多数现代"经常表现形式"使用编程语言实际上比常规语言，因此有时难以了解。

其他提示

是的， 它是可能的， 我们可以产生regex从实例(文->需要拔牙).这是一个在线工作的工具，它不会的工作： http://regex.inginf.units.it/

Regex发电机++在线工具产生regex从提供的例子使用GP搜索算法。GP算法是由一个多目的的健身，这会导致更高效和更简单的解决方案结构(奥卡姆剃刀).这个工具是一个demostrative应用程序的机Lerning实验室，的里雅斯特大学(Università degli studi di的里雅斯特).请看视频教程 在这里，.

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

看哪！ :-)

找到一个有意义的regex/溶液的实例是可能的 如果且只有如果 提供的例子说明问题。考虑到这些示例，介绍一个提取的任务，我们正在寻找特别项目的代码；例的文字/取对：

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

一种(人类)的家伙，看着的例子，可以说:"项目的代码的东西喜欢\d++-345[AB]"

当该项目的代码的更多宽容，但我们不提供的其他例子，我们没有证据来理解这个问题。当申请人产生的解决方案\d++-345[AB]以下文本，它失败：

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

你必须提供的其他例子，以便更好地描述什么是一个比赛并不是什么期望相匹配：-我.e：

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

该电话号码不是一种产品标识，这可能是一个重要证明。

没有计算机程序将永远能够产生一个有意义的经常表达的基础 只 在一系列有效的匹配。让我告诉你为什么。

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

  1. Regex匹配的正是这两个例子： (111111|999999)
  2. Regex匹配的6相同的数字 (\d)\1{5}
  3. Regex匹配的6人，并花枝招展 [19]{6}
  4. Regex匹配的任何6位数 \d{6}
  5. 上述任何三个词的界限，例如 \b\d{6}\b
  6. 任何第三，不是之前或之后通过一个数字，例如(?<!\d)\d{6}(?!\d)

正如你可以看到，有许多方式中的示例可以推广到一个普通的表达。唯一的方式计算机建立一个可预测的经常表达的是需要你的表 所有 可能匹配。然后它可能会产生一种搜索模式相匹配的正是这些相匹配。

如果你不想列举所有可能的匹配，你需要一个更高级别的说明。这正是经常表达的设计来提供。而不是提供一个长长的清单的6位数字的号码，你只需告诉程序相匹配"任何一六位数字".在经常表达法，这种变\d{6}.

任何方法提供更高水平的描述，这是因为灵活，因为经常表也将作为复杂，因为经常表达方式。所有工具 RegexBuddy 可以做的是使它更容易创造和测试的高级别介绍。而不是使用简洁regular expression syntax直接RegexBuddy可以使用简单的英语。但是它不可能创造高级别描述为你，因为它不能奇迹般的知道什么时候应该一概而论您的例子，当它不应该。

这当然可能创造一个工具使用的样本的案文与指南用户提供的产生一个定期表达。最难的部分在设计这样一个工具，是如何不询问用户的指导信息的，它需要，而不会使该工具难以了解比常规的表达自己，并没有限制的工具，以共同regex工作或简单的规则的表达。

是的，这是肯定的"可能的";这是伪码：

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;
}

问题是，有无数的regexs，将符合清单的实例。这个代码提供最简单/愚蠢的regex在设置，基本上匹配的任何东西的列表中的积极例子(而不是其他，包括任何负面的例子)。

我想真正的挑战将是找到最短regex相匹配的所有例子，但即使在那时，用户必须提供非常良好的投入，以确保所得的表达是"正确的"。

我相信术语是"诱导".你要诱使一个正规语法。

我不认为这是可能的一组有限的实例(正或负)。但是，如果我记忆正确的话，它可以做，如果存在一个Oracle其可以进行协商。(基本上，你就必须让的程序要求的用户是/否的问题，直到它的内容。)

你可能想要玩这个网站一点，这是相当酷的，听起来像它一些类似的你在说什么: http://txt2re.com

有一个语言专门用于这样的问题，基于序言.这就是所谓 progol.

正如其他人已经提到的，基本想法是感性的学习，通常被称为指令级(感应编程逻辑)在艾圈子。

第二链接是维基的文章指令级，它包含了很多有用的材料来源如果你有兴趣了解更多关于该主题。

@尤瓦是正确的。你看计算的学习理论，或者"感应推断。"

问题是比你想象的更复杂，因为该定义的"了解"是非微不足道的。一个共同定义是，学习者可以吐出答案，只要它想，但最终，这必须停止吐出答复，或一直吐出相同的回答。这假定无限数量的输入，和提供绝对没有garauntee在当程序将达到其决定。还有，你不能告诉当它已经达到了其决定，因为它可能仍然出不同的东西以后。

通过这个定义，我敢肯定，经常语言中都可以学习的.通过的其他定义，没有这么多...

我已经做了一些研究，谷歌和 CiteSeer 并找到这些技术/文件：

也纳Angluin的"学习常规设置，从查询和反例"，似乎有希望的，但是我没能找到一个PS或PDF格式的版本中，只有《濒危物种贸易公约》和研讨会论文。

这似乎是一个棘手的问题，即使在理论水平。

如果其可能一个人学习一个经常的表达，那么它从根本上讲是可能的程序。然而，该程序将需要正确的编程能够学习。幸运的是，这是一个相当有限空间的逻辑，所以它不会是为复杂，因为教学的一个程序，以便能够看见物体或类似的东西。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top