匹配重复模式的字符串的正则表达式

Question

我正在尝试找到一个正则表达式来匹配具有三个或更多重复部分的URL（可以包括任意数量的目录），例如：

• s1 = 'http://www.foo.com/bar/bar/bar/'
• s2 = 'http://www.foo.com/baz/biz/baz/biz/baz/biz/etc'
• s3 = '/foo/bar/foo/bar/foo/bar/'

而不匹配如下的URL：

• s4 = '/foo/bar/foo/bar/foo/barbaz'

首先，我尝试了以下正则表达式：

re1 = /((.+\/)+)\1\1/

哪些是有效的：

re1 === s1 #=> true
re1 === s2 #=> true

但是，随着段落数量的增加，正则表达式匹配的时间将呈指数级增长：

require 'benchmark'
Benchmark.bm do |b|
  (10..15).each do |num|
    str = '/foo/bar' * num
    puts str
    b.report("#{num} repeats:") { /((.+\/)+)\1\1/ === str }
  end
end

       user     system      total        real
/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
    10 repeats:  0.060000   0.000000   0.060000 (  0.054839)
    /foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
    11 repeats:  0.210000   0.000000   0.210000 (  0.213492)
    /foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
    12 repeats:  0.870000   0.000000   0.870000 (  0.871879)
    /foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
    13 repeats:  3.370000   0.010000   3.380000 (  3.399224)
    /foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
    14 repeats: 13.580000   0.110000  13.690000 ( 13.790675)
    /foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
    15 repeats: 54.090000   0.210000  54.300000 ( 54.562672)

然后，我尝试了一个与这里给出的正则表达式类似的正则表达式：

re2 = /(\/.+)(?=.*\1)\1\1/

我希望你能够提供一个性能优异且能匹配我所需字符串的解决方案：

re2 === s3 #=> true

但是它也匹配了我不想要匹配的字符串，比如：

re2 === s4 #=> true, but should be false

我接近第二个正则表达式。我错过了什么？

- MothOnMars

Answer 1

将 . 替换为 [^\/] 。这样做可以降低正则表达式的复杂性，因为它不会尝试匹配“任何”字符。

require 'benchmark'

Benchmark.bm do |b|
  (10..15).each do |num|
    str = '/foo/bar' * num
    puts str
    b.report("#{num} repeats:") { /(([^\/]+\/)+)\1\1/ === str }
  end
end

10 repeats:  0.000000   0.000000   0.000000 (  0.000015)
/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
11 repeats:  0.000000   0.000000   0.000000 (  0.000004)
/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
12 repeats:  0.000000   0.000000   0.000000 (  0.000004)
/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
13 repeats:  0.000000   0.000000   0.000000 (  0.000004)
/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
14 repeats:  0.000000   0.000000   0.000000 (  0.000004)
/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar/foo/bar
15 repeats:  0.000000   0.000000   0.000000 (  0.000005)

- Josh Voigts

Answer 2

定义

假设：

str = 'http://www.example.com/dog/baz/biz/baz/biz/baz/biz/cat/'

我们可以将'/dog'，'/baz'，'/biz'等定义为片段。一个组由一个或多个连续的片段组成，例如'/dog'，'/baz'，'/dog/baz'，'/baz'，'/baz/biz'，'biz/baz'，'/baz/biz/baz'等。

问题

我的理解是要确定给定的字符串是否包含三个（或更多）连续且相等的组，后跟一个正斜杠。 s2通过以下子字符串满足此测试：

'/baz/biz/baz/biz/baz/biz/'

算法

我不相信可以编写一个单一的正则表达式来进行这种判断，但是我们可以编写一个正则表达式来确定是否存在至少三个（或某些任意数量的）连续的相等分组，已知每组的段数。假设这是通过一个名为contiguous_fixed_group_size?的方法完成的，该方法的调用方式如下：

contiguous_fixed_group_size?(str, segments_per_group, nbr_groups)

并返回true或false。为确保字符串至少有3个连续的相等组（对于给定的segments_per_group值），我们使用nbr_groups = 3调用此方法。我认为最好简要地推迟构建此方法；目前假设它对我们可用。

我采取的方法是使用不同的segments_per_group值调用此方法，并确定该方法是否对其中至少一个值返回true。

主方法

第一步是确定字符串中的段数（其中str包含上述给定的字符串）：

 r = /(?<!\/)\/(?!\/)/
 nbr_segments = str.scan(r).size - 1 
   #=> 8

我们可以通过在自由间距模式下编写正则表达式来记录它：

 r = /
     (?<!\/)  # match is not to be preceded by '/' (negative lookbehind)
     \/       # march '/' 
     (?!\/)   # match is not to be followed by '/' (negative lookahead)
     /x

Lookarounds 防止匹配 str 中的 '//'。

现在我们要问自己，必须考虑的 segments_per_group 的最大值是多少。因为我们要求：

nbr_groups * segments_per_group <= nbr_segments

由此可知：

segments_per_group <= nbr_segments/nbr_groups

在右边使用整数算术。对于nbr_groups = 3，我们得到：

segments_per_group <= 8/3 => 2

因此，我们可以按照以下方式确定str是否包含（至少）nbr_groups个连续的相等组：

(1..nbr_segments/nbr_groups).any? do |segs_per_group|
  contiguous_fixed_group_size?(str, segs_per_group, nbr_groups)
end
  #=> true

我们可以将其封装在一个方法中：

def contiguous?(str, nbr_groups)
  nbr_segments = str.scan(/(?<!\/)\/(?!\/)/).size - 1
  (1..nbr_segments/nbr_groups).any? do |segs_per_grp|
    contiguous_fixed_group_size?(str, segs_per_grp, nbr_groups)
  end
end

构建方法contiguous_fixed_group_size?

该方法可以编写如下：

def contiguous_fixed_group_size?(str, segments_per_group, nbr_groups)
  r = /((?:\/[^\/]+){#{segments_per_group}})\1{#{nbr_groups-1}}/ 
  str.match?(r)
end

对于

str = s2
segments_per_group = 2
nbr_groups = 3

正则表达式为：

r #=> /((?:\/[^\/]+){2})\1{2}\//

这里是以自由空格模式编写的：

r = /
    (?<!\/)                    # match is not to be preceded by a forward slash
                               # (negative lookbehind)    
    (                          # begin capture group 1
      (?:                      # begin non-capture group
        \/[^\/]+               # match '/' followed by 1+ char other than '/'
      )                        # end non-capture group 
      {#{segments_per_group}}  # execute non-capture group segments_per_group times
    )                          # end capture group 1
    \1{#{nbr_groups-1}}        # execute contents of capture group 1
                               # nbr_groups-1 times 
    \/                         # match '/'
    /x                         # free-spacing regex definition mode

示例

str 如上所定义。

contiguous?(str, 3) #=> true
contiguous?(str, 2) #=> true
contiguous?(str, 1) #=> true
contiguous?(str, 4) #=> false

str = 'http://www.example.com/dog/baz/biz/baz/bix/baz/biz/cat/'
contiguous?(str, 3) #=> false
contiguous?(str, 2) #=> false
contiguous?(str, 1) #=> true

- Cary Swoveland