Ruby List to Regexp

hooopo · 2012年11月05日 · 最后由 zw963 回复于 2012年11月15日 · 4025 次阅读
=> list = %w{foobar fooxar foozap fooza}
=> ["foobar", "fooxar", "foozap", "fooza"]
[22] pry(main)> Regexp.union(list)
=> /foobar|fooxar|foozap|fooza/

上面是一个 list 转换成一个正则的普通做法,但生成的正则不是最优的,最优的是/foo(?:[bx]ar|zap?)/

http://search.cpan.org/~dankogai/Regexp-Optimizer-0.15/lib/Regexp/List.pm

这里有 Perl 的实现,不过看不懂。。。谁能写个 Ruby 版的哇?

做了有用么?貌似正则引擎已经做了提取公共子表达式的优化了?

好吧看了编译出来的 Onig 字节码,应该没做这种优化

PATTERN: /fooa|foob|fooc/ (US-ASCII)
optimize: EXACT_BM
  anchor: []
  sub anchor: []

exact: [foo]: length: 3
code length: 36
0:[push:(10)] 5:[exact4:fooa] 10:[jump:(20)] 15:[push:(10)] 20:[exact4:foob]
25:[jump:(5)] 30:[exact4:fooc] 35:[end]

然后测了下做不做优化的区别

require 'benchmark'
os = 'o'*10000
r1 = /f#{os}a|f#{os}b|f#{os}c/
r2 = /f#{os}[abc]/
s = "f#{os}c"
puts Benchmark.measure{ 1000.times{r1.match s} }
puts Benchmark.measure{ 1000.times{r2.match s} }

10000 个子的话,做这种优化会快一倍多点的样子,但是短的就不清楚了

可以一做...

#2 楼 @luikore 我是看 http://book.douban.com/subject/6758780/ 这本书里讲他们用来处理关键字链接,就是有一组关键词对全文做 autolink,大概是blog.body.gsub(/(key1|key2...)/, "<a href='...'>\\1</a>")

场景应该是关键词短,但数量多,文章长。

据说他们从Regexp union -> Aho-Corasick算法的Trie树-> Perl 的Regexp::List

#3 楼 @hooopo 是 csdn 在用?你们有全文索引的吧,文章索引的时候各个关键字的位置都已经获得了,在对应的位置前后直接插入,这样会更加方便吧。

#3 楼 @hooopo 为什么这个比 Trie 更快?这么搞了之后和 Trie 几乎一样的啊,可能还不如 Trie。因为 Perl 风格的正则表达式需要回溯

可以试一下 re2

https://code.google.com/p/re2/

或者把 irregexp 从 V8 里面剥出来

#4 楼 @quakewang 不是。哦,好像和高亮一样..

#5 楼 @bhuztez 没说比 Trie 快,貌似提到正则更灵活,并且也不慢。 还有即使用 Perl 实现的 trie 和正则从算法复杂度是一样,正则引擎是 c 实现的,速度应该也会有差异。 所以我才想用实际数据测试一下:-)

@hooopo

整了一个 Regexp.list (其实我的编辑器里也需要类似的功能), 希望没奇怪的 bug 哈

class Regexp
  class TrieNode < Hash
    attr_accessor :parent, :op_maybe, :op_suffix
    def []= k, v
      super(k, v)
      v.parent = self
    end

    def single_branch?
      empty? or (size == 1 and !op_maybe and values[0].single_branch?)
    end

    def single_char?
      size == 1 and values[0].empty?
    end

    # prereq: single_branch?
    def to_chars
      if empty?
        []
      else
        [keys[0], *values[0].to_chars]
      end
    end

    # returns: regexp source for common suffix
    def compute_common_suffix
      branches = map do |key, value|
        [key, *value.to_chars]
      end
      branches.each &:reverse!
      max_common_size = branches.map(&:size).min
      common_size = nil
      max_common_size.downto 1 do |i|
        found = true
        branches.map {|b| b.take i }.each_cons(2) do |b1, b2|
          if b1 != b2
            found = false
            break
          end
        end
        if found
          common_size = i
          break
        end
      end

      if common_size
        common = branches[0].take(common_size).reverse.join
        if branches.all?{|b| b.size == common_size + 1 }
          diff = branches.map(&:last).join
          "[#{diff}]#{common}"
        else
          diff = branches.map do |b|
            b.drop(common_size).reverse.join
          end.join '|'
          "(?:#{diff})#{common}"
        end
      end
    end

    def to_re_src
      return '' if empty?

      res = compute_common_suffix if op_suffix
      if !res
        can_be_branched = true
        res = map do |key, value|
          "#{key}#{value.to_re_src}"
        end.join '|'
      end

      if op_maybe
        if single_char?
          "#{res}?"
        else
          "(?:#{res})?"
        end
      else
        if can_be_branched and size > 1 and parent
          "(?:#{res})"
        else
          res
        end
      end
    end
  end

  def self.list a
    trie = TrieNode.new
    term_nodes = {}

    # build trie
    a.each do |s|
      next if s.empty?
      t = trie
      s.chars.each do |c|
        c = Regexp.escape c
        unless t[c]
          t[c] = TrieNode.new
        end
        t = t[c]
      end
      term_nodes[t] = true
      t.op_maybe = true
    end

    # tag op_suffix nodes
    term_nodes.each do |node, _|
      next unless node.empty?
      while node = node.parent and !node.op_suffix and !node.op_maybe
        if node.size > 1
          if node.values.all?(&:single_branch?)
            node.op_suffix = true
          end
          break
        end
      end
    end

    Regexp.new trie.to_re_src
  end
end

if __FILE__ == $PROGRAM_NAME
  {
    []                                => //,
    ['foo']                           => /foo/,
    ['foo', 'bar']                    => /foo|bar/,
    ['foo', 'foob', 'bar']            => /foob?|bar/,
    ['foo', 'foobar']                 => /foo(?:bar)?/,
    ['bazfoo', 'bazfoobar', 'bazbar'] => /baz(?:foo(?:bar)?|bar)/,
    ['fooabar', 'foobbar']            => /foo[ab]bar/,
    ['fooabar', 'foobazbar']          => /foo(?:a|baz)bar/,
    ['foobar', 'fooabar', 'foogabar'] => /foo(?:|a|ga)bar/
  }.each do |a, r|
    l = Regexp.list a
    a.each do |s|
      raise "#{l.inspect} from #{a.inspect} not match #{s.inspect}" if l.match(s).offset(0) != [0, s.size]
    end
    raise "expected #{r} from #{a.inspect} but got #{l}" if r != l
  end
  puts 'test success!'
end

原来是这样:

@luikore == @night_song  # => true

整成一个 gem 了 ...

gem ins regexp_optimized_union
require 'regexp_optimized_union'
Regexp.optimized_union %w[foobar foobaz foobarbaz]

就这样,一个 gem 诞生了

#10 楼 @luikore 👍 哇!还有另一种情况不知道需不需要优化

require 'regexp_optimized_union'
Regexp.optimized_union %w[a b c d e f g]
=> /a|b|c|d|e|f|g/
#优化?
=> /[a-g]/

#13 楼 @Los 这个实现有点 quick and dirty, 还不好做这个优化,有空我会试试

#9 楼 @skandhas

是一个人吗?难怪对正则这么感兴趣,期待 RubyConf 有关正则的精彩演讲。

#14 楼 @luikore 对现在的算法得出结果后再专门针对 [a|b|c|d|e|f|g] 这类型情况进行二次处理,应该能简单完成这部分优化?

#17 楼 @Los 只对 ascii 字符处理的话可以。非 ascii 字符的话,就不兼容 1.8 了

#18 楼 @luikore 感觉现在支持 1.9 以上版本应该就足够,1.8 慢慢给抛弃了

NS 一出手,就知有没有

#16 楼 @skandhas

哈哈。@luikore , 你为什么整这么多马甲呢?

说起来,真的很期待你有关正则的演讲。

另外,我有一点点小经验分享,不知道你会不会提及。就是编写正则表达式 (尤其是复杂的), 编辑器的模板系统也蛮重要,他可以让我编写正则更加轻松。

例如下面是我 Emacs 的 Yasnippet 中的一个 snippet.

# -*- mode: snippet -*-
# name: RE(?=AFTER)
# binding: M-c >
# condition: (and (yas-ruby-in-interpolated-regexp-p) 'force-in-comment)
# --
(?=`(erase-if-region-active "${1:AFTER}")``yas-selected-text`)

这个模板系统,使用快捷键 (Alt-c + >) 激活 (而不是普通的 key),

例如:我键入 M-c >, 会出现一个模板(?=AFTER),其中 AFTER 我自己可以随意修改. 不过更有趣的是,通过 mark-region 的方式。

例如:hello world, 我要匹配 world 前面的那个 hello, 我会首先直接写 /hello world/ 然后,然后使用 region mark world, 然后键入快捷键 M-c >, 结果会变为:/hello(?= world)/ , 对于复杂的匹配,使用这种写法,让写正则表达式的逻辑更清晰,而且更不容易出现错误,

还有一个小技巧,不知道大家注意到没有。就是我使用 %r 编写正则的时候,可以使用一个控制字符来作为边界,例如,我经常会使用 ASCII 为 1 的字符作为边界,在 Emacs 下面是这样显示的:

%r^Ahello world^A, 当然,其他表示法,我也会用控制字符。不过对于正则来说意义更大一些。

#17 楼 @Los 字符组优化已加好 (0.1.2)

#21 楼 @zw963 原来 yasnippet 可以这么配...

边界这样写不错,不过我觉得复杂正则用 x 参数加些空白就好了...

/
  hello\ world
/x

#22 楼 @luikore

原来 yasnippet 可以这么配...

不是,那些方法是我自己为 yasnippet 创建的判断方法,Yasnippet 自己不带的。不过写起来很简单的。

边界这样写不错,不过我觉得复杂正则用 x 参数加些空白就好了...

你的意思我没有明白,下面的写法,

/
  hello\ world
/x

/hello world/ 有区别吗?这好像是匹配整个 hello world, 而非 world 前面的那个 hello 吧。

#24 楼 @zw963

我的意思是 / hello\ world /x%r^Ahello world^A 结果一样,加空格也是提高可读性的一个手段... 没说 look around... 因为常用的 look around 就有 (?<), (?<!), (?=), (?!), 有时还会用到 (?:), (?>) (原子分组), (?@) (我有个开启捕获历史的 ruby...), 类似的 code pattern 种类太多就没做 snippet...

#22 楼 @luikore 为什么不是 0.2.0? 这是一个新特性~ 版本号这么保守什么时候才能到 10.0 啊!

#25 楼 @luikore

哦。我理解错了。还以为你说正则断言呢。

不过,我所讲的用 %r 的场合,在于你编写一些脚本的时候,这个时候,你用控制字符作为边界,不用担心使用脚本的用户,在正则中输入和边界一样的字符。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号