更改字符串以匹配正则表达式

是否有可能（或为什么不可能）将输入字符串转换为匹配正则表达式的字符串的最小Levenshtein距离？更改字符串以匹配正则表达式

即如果1234是字符串和^（[0-9] {6}）$是正则表达式，我需要输出像123412（输出字符串匹配的正则表达式和距离原始字符串2的距离，可能有其他字符串但第一个结果会做）

如何做到这一点？（无蛮力..）

编辑：

在其他可能性

，可我只得到Levenshtein距离？（没有匹配字符串...）

还有什么其他信息除了表格布尔（匹配或不匹配）可以正则表达式给？

来源

2010-09-12 iamgopal

对我来说似乎很难。我可以想象没有快速贪婪的算法，这将是一个大搜索。 – LatinSuD 2010-09-12 10:59:16

如果你知道finite automaton你可以构造一个代表你的正则表达式（有库可以这样做）。然后你用你的字符串（1234）运行它，你会以某种状态结束。从这个状态开始，你做一个breath-first search，直到你达到接受状态。在搜索过程中，您会记录您跑过的哪些转换（字符）。角色会给你最短的（或者其中一个）字符串，这个字符串符合你的正则表达式。

添加链接：你可能会对http://www.brics.dk/automaton/看看这是在奥胡斯大学（BSD许可证）

更新实施了自动机库：我建你寻求从上面的自动机实现的。首先，与其他自动机类处于相同包中的ExtendedOperations类，因为我需要访问某些方法。

package dk.brics.automaton; 

public class ExtendedOperations { 
    //Taken from Automaton.run and modified to just return state instead of accept (bool) 
    static State endState(String s, Automaton a) 
    { 
     if (!a.deterministic) a.determinize(); 

     State p = a.initial; 
     for (int i = 0; i < s.length(); i++) { 
      p = p.step(s.charAt(i)); 
      if (q == null) return null; 
     } 
     return p; 
    } 

    public static String getShortestCompletion(Automaton a, String partlyInput) 
    { 
     State e = endState(partlyInput, a); 

     if (e == null) return null; 

     return BasicOperations.getShortestExample(e, true); 
    } 
}

二，一点点testsample：

package subsetautomaton; 

import dk.brics.automaton.*; 

public class Main { 
    public static void main(String[] args) { 
     RegExp re = new RegExp("[a-zA-Z0-9._%+-]+\\@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,6}"); 
     Automaton a = re.toAutomaton(); 

     System.out.println(ExtendedOperations.getShortestCompletion(a, "a")); 
    } 
}

的例子是一个天真的电子邮件地址寄存器。进出口。请注意，^隐含在注册表中。进出口。和$一样。其次，@与\一起转义，因为它在此实现中表示“任何字符串”。

以上示例的结果是：@-.AA

来源

2010-09-12 10:53:23

更改字符串以匹配正则表达式

回答

相关问题