构建一个正则表达式作曲家

用户给出了他想要什么例子，并不想匹配。该程序试图推导出适合这些示例的正则表达式。然后它会生成适合和不适合的示例。用户更正了错误的示例，并组成了新的正则表达式。迭代地，你得到一个足够接近你需要的正则表达式。

这听起来像是一个非常有趣的想法给我。有没有人有一个想法，如何做到这一点？我的第一个想法就像一个遗传算法，但我会喜欢你们的一些输入。

2010-09-06 Amir Rachum

XD。我只是想到用户输入“必须匹配'bob'，'charlie'和'grant'”等可接受的输入，而正则表达式生成器吐出“REGEXP = bob | charlie | grant”。 > _>。 – Stephen 2010-09-06 13:51:17

@Stephen这也是我关心的，这就是为什么我在寻找输入：P – 2010-09-06 13:51:57

也许一个遗传算法可以为更短的表达式提供点... – 2010-09-06 13:52:23

您可能会尝试使用已在其他应用程序中使用的基本推理算法。我已经实现了基于构建状态机的一个非常基础的。但是，它仅占正面样本。源代码位于http://github.com/mvaled/inferdtd

应该对AutomataInferrer.py感兴趣，它非常简单。

来源

2010-09-07 18:41:42 manu

RegexBuilder似乎有许多你正在寻找的功能。

来源

2010-09-16 02:18:18

这完全不一样。另外，我没有要求一个程序，我问了算法的想法。 – 2010-09-16 08:20:52

埃米尔，但如果你花时间评估程序，它可以给你一些算法的想法！ – splash 2010-09-16 12:49:10

实际上，这开始变得越来越像编译器应用程序。事实上，如果我没有记错的话，Aho Dragon编译器手册使用一个正则表达式来构建一个DFA编译器。这是开始的地方。这可能是一个非常酷的编译器项目。

如果是太多了，你可以接近它通过几个步骤的优化，以进一步和进一步完善它，但是这将是所有预定义的算法中的初：

第一步：要匹配猫，渔获量罐结果：/猫|渔获|罐/

第二关：寻找类似的启动条件：结果：/钙（T | tches | ANS）/

第二关：寻找类似的结局条件：结果：/ Ca（t | tch | an）s */

第三关：寻找更多的改进喜欢重复和消极条件

来源

2010-09-16 12:35:38 SDGator

我已经想到了这种方法，但它有几个缺点：首先，我不明白它是如何工作的不匹配的例子。其次，它永远不会满足我的期望。例如，如果我得到几个例子，比如'a'，'aa'，'aaa'，'aaaa'，'aaaaa'，那么我希望它提出'a *'而不是'aa？a？a？一个？'。即与所提供的示例匹配/不匹配的最短正则表达式。 – 2010-09-16 12:51:37

听起来像你想做一个编译器，然后。阅读Aho书的前两三章。它详细介绍了如何构建一个DFA编译器来执行此操作。我们在我的最后一个公司做过...我的一个朋友为我们在HW中实现的正则表达式引擎编写了一个编译器。他还使用了一个可视化库来绘制编译器提出的DFA状态，并且它有时会提供一些非常狂野的图。不过，我们正在优化性能而不是简短。 – SDGator 2010-09-16 13:11:12

程序试图演绎一个正则表达式适合的例子

我不认为这是一个非常有用的问题要问。你必须从语义上知道你需要表达的东西。当你写一个正则表达式时，你有一个目的：接受url，接受电子邮件，从代码中提取令牌等等。我会重新定义这个问题：给定知识库和正则表达式的语义，计算最小的正则表达式。这更进一步，因为你有自然语言试图解释一般表达，我们都知道它是如何变得模糊！你必须有一些语义解释。没有这些，你可以做的最好的例子是计算正则表达式，覆盖ok列表中的所有字符串。

算法报道：

填充好的名单
填充也不行列表
检查重复
检查矛盾（相同字符串不能在这两个列表）
创建确定性有限自动机（DFA）从确定列表中，列表中的字符串是最终状态
通过消除重复性状态来简化DFA。（[1] 4.4）
将DFA转换为正则表达式。（[1] 3.2.2）
测试OK列表和Not OK列表

[1] Introduction to Automata Theory, Language, and Computation. J. Hopcroft, R. Motwani, J.D. Ullman, 2nd Edition, Pearson Education.

P.S.

我有一些遗传编程方面的经验，我认为这对您的问题来说确实是一个开销。由于目标函数非常轻，因此最好使用单个处理器进行评估，这可能需要很长时间。为了缩短表达式，您只需要最小化DFA。但GA可能会产生有趣的结果。

来源

2010-09-16 14:40:23

存在一个正确的例子，正是这样做的算法。

正则表达式等同于DFA（确定性有限自动机）。该策略大多都是一样的：

看看Alergia（理论）和MDI算法（真实用法）如果生成确定性自动机就足够了。

的Alergia算法和MDI都说明如下： http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/icml2k.pdf

如果你想生成较小的模型，你可以使用另一种算法。描述它的文章是在这里： http://www.grappa.univ-lille3.fr/~lemay/publi/TCS02.ps.gz

他的主页是在这里： http://www.grappa.univ-lille3.fr/~lemay

如果你想用反面教材，我建议你用一个简单的规则（着色）而无法DFA的两种状态被合并。

如果你问这些人，我相信他们会分享他们的代码源。

我在博士期间做了同样的算法。用于概率自动机。这意味着，您可以将每个字符串的概率关联起来，并且我已经制作了一个C++程序来“学习”加权自动机。

主要是这些算法的工作像：

从正面的例子：{ABB，ABA，AB | BB}

创建接受正是所有这些例子最简单的DFA：

-> x -- a --> (y) -- b --> (z) 
      \ 
      b --> t -- b --> (v)

X倾斜例如，通过阅读字母“a”来说明y。状态是x，y，z，t和v。（z）意味着它是一个有限状态。的DFA的

然后“合并”的状态：（这里例如合并状态y及t之后的结果

   _ 
      /\ 
      v | a,b  (<- this is a loop :-)) 
x -- a -> (y,t) _/

新的状态（Y，t）是终端状态通过合并ÿ获得和t并且你可以从中读取字母a和b 现在DFA可以接受：a（a | b）*并且很容易从DFA构造正则表达式

哪个状态合并是一种选择，使算法之间的主要区别

来源

2010-09-16 22:50:53 yogsototh

你描述的算法是如何处理反例的？ – 2010-09-17 16:19:06

事实上，我主要是通过正面的例子。对于否定的，你应该使用一种阻止合并的状态着色方法。该算法在此处详述：http://www.irisa.fr/symbiose/old/people/coste/pub/icml97.ps – yogsototh 2010-09-19 21:01:18

也许我有点晚了，但有一种方法可以通过遗传编程来解决这个问题。遗传编程（GP）是一种进化机器学习技术，在这种技术中，给定问题的候选候选解决方案被表示为抽象语法树。

已经发表了几篇关于如何使用GP的研究，以便找到与给定的一组示例相匹配的正则表达式。你可以找到这篇文章和细节here

这样做的web应用程序托管在regex.inginf.units.it。该应用程序背后的源代码已公开发布于github

来源

2015-05-01 18:08:17 mimmuz

构建一个正则表达式作曲家

回答

相关问题