计算Swift中正则表达式的最小匹配长度

问题描述：

我想知道是否有人有算法来计算以字符串表示的给定正则表达式的最小可能匹配长度。例如，让我们称此算法计算Swift中正则表达式的最小匹配长度

φ(r)=Int

其中是正则表达式和函数吐出的整数值。我想在我的应用程序使用这种算法，这样我就可以计算像

$φ(\bimport\s+)=7$

的东西，而不是一个“最小模式长度”件的元数据手动标记到每一个正则表达式。我去之前的任何想法都尝试重新创建似乎是一个非常复杂的轮子，我自己？尽管如此，我仍将享受挑战。我认为我必须使用正则表达式来分析正则表达式本身。先谢谢您的帮助！我正在寻找一个用Swift编写的解决方案，但通用版本不会受到影响。

答

你想要做将需要一些工作是什么。你将需要开发你自己的正则表达式解析器，我不会为你做这件事（我不知道Swift，但不应该用正则表达式来完成正确的解析器）。但是，我可以帮助使用该算法。

我会想象这种工作的方式是，一步一步地删除和修改正则表达式，直到可以达到具体的答案。显然，你不应该在你唯一的正则表达式副本上这样做，因为这可能最终会破坏正则表达式。

这里有一些要采取的步骤：

与.替换字符类。您需要小心，您知道Swift的正则表达式如何处理奇怪的语法，例如[]，在某些口味中，]将其视为文字，因为语法无效。
删除最多：(regex part){min~~,max~~}。
- 将(regex part){min}替换为min重复的regex part。
删除*声明：~~(regex part)*~~
删除任何+符号：~~(~~regex part~~)+~~
对于交替，找到最短的交替，并删除所有其他的人：~~(regex part is long|but this regex part is super duper long|medium regex|~~short~~)~~
用一个.替换char类
用.替换所有转义字面值，即使是\n。请记住，抛开花哨的语法可以更容易地计算最少有多少个字符。

这不是一个详尽的清单，但它会希望让你开始。一些谨慎的就是抢先消除括号，这可能会搞乱了操作顺序和反向引用。如果Swift的正则表达式具有递归功能，这个任务变得更加困难。

另外要记住的是，一些正则表达式可能不会匹配任何东西（但弄清这一点可能很难），以及“最低匹配长度”是在这些情况下没有意义的。

提示是大加赞赏。是的，这需要很多理论，并简单地将表达式缩减为一个简短的字符串并返回该长度 –

答

这是在Ruby中，没有斯威夫特，但here是一个工具，我写了可以用来解决这个问题：

/import\s+/.examples.map(&:length).min # => 7

这个工具将用于所有正则表达式的工作，除了那些其中包含环视。（预见，后视，字边界锚等）

如果您只希望它能够使用正则表达式语言的一小部分，您就可以很容易地编写一个简单得多的版本。但是，从经验来看，创建这样的“通用解决方案”非常复杂。

答

这是一项正在进行的工作，但是这是我迄今为止...

public extension String { 

    public var minRegexMatchLength: Int { 

     let pattern = (self as NSString).mutableCopy() as! NSMutableString 

     if let expr = try? NSRegularExpression(pattern: "((\\(.*?\\))|(\\[.*?\\])|.)[*?]", options: []) { 
      expr.replaceMatchesInString(pattern, options: [], range: NSMakeRange(0, (pattern as String).length), withTemplate: "") 
     } 

     if let expr = try? NSRegularExpression(pattern: "((\\(.*?\\))|(\\[.*?\\])|.)[+]", options: []) { 
      expr.replaceMatchesInString(pattern, options: [], range: NSMakeRange(0, (pattern as String).length), withTemplate: ".") 
     } 

     if let expr = try? NSRegularExpression(pattern: "(\\[bswBSW])", options: []) { 
      expr.replaceMatchesInString(pattern, options: [], range: NSMakeRange(0, (pattern as String).length), withTemplate: ".") 
     } 

     if let expr = try? NSRegularExpression(pattern: "\\(.*?\\)", options: []) { 

      var lengths = [Int]() 

      expr.enumerateMatchesInString(pattern as String, options: [], range: NSMakeRange(0, (pattern as String).length)) 
      { (result: NSTextCheckingResult?, _, _) -> Void in 
       if let result = result { 
        let substring = pattern.substringWithRange(NSMakeRange(result.range.location + 1, result.range.length - 2)) 
        var length = substring.length 
        for word in substring.componentsSeparatedByString("|") { 
         if (word.length < length) { 
          length = word.length 
         } 
        } 
        lengths.append(length) 
       } 
      } 

      var match = expr.firstMatchInString(pattern as String, options: [], range: NSMakeRange(0, (pattern as String).length)) 
      var i = 0 
      while match != nil && i < lengths.count { 
       if let range = match?.range { 
        pattern.replaceCharactersInRange(range, withString: "".stringByPaddingToLength(lengths[i], withString: ".", startingAtIndex: 0)) 
       } 
       match = expr.firstMatchInString(pattern as String, options: [], range: NSMakeRange(0, (pattern as String).length)) 
       i += 1 
      } 

     } 

     return pattern.length 

    } 

}

计算Swift中正则表达式的最小匹配长度

相关推荐