=> 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 为什么这个比 Trie 更快？这么搞了之后和 Trie 几乎一样的啊，可能还不如 Trie。因为 Perl 风格的正则表达式需要回溯
可以试一下 re2
https://code.google.com/p/re2/
或者把 irregexp 从 V8 里面剥出来
#4 楼 @quakewang 不是。哦，好像和高亮一样..
#5 楼 @bhuztez 没说比 Trie 快，貌似提到正则更灵活，并且也不慢。 还有即使用 Perl 实现的 trie 和正则从算法复杂度是一样，正则引擎是 c 实现的，速度应该也会有差异。 所以我才想用实际数据测试一下:-)
整了一个 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
整成一个 gem 了 ...
gem ins regexp_optimized_union
require 'regexp_optimized_union'
Regexp.optimized_union %w[foobar foobaz foobarbaz]
哇！还有另一种情况不知道需不需要优化
哈哈。@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, 当然，其他表示法，我也会用控制字符。不过对于正则来说意义更大一些。
原来 yasnippet 可以这么配...
不是，那些方法是我自己为 yasnippet 创建的判断方法，Yasnippet 自己不带的。不过写起来很简单的。
边界这样写不错，不过我觉得复杂正则用 x 参数加些空白就好了...
你的意思我没有明白，下面的写法，
/
hello\ world
/x
和 /hello world/ 有区别吗？这好像是匹配整个 hello world, 而非 world 前面的那个 hello 吧。
我的意思是 / hello\ world /x 和 %r^Ahello world^A 结果一样，加空格也是提高可读性的一个手段... 没说 look around... 因为常用的 look around 就有 (?<), (?<!), (?=), (?!), 有时还会用到 (?:), (?>) (原子分组), (?@) (我有个开启捕获历史的 ruby...), 类似的 code pattern 种类太多就没做 snippet...
哦。我理解错了。还以为你说正则断言呢。
不过，我所讲的用 %r 的场合，在于你编写一些脚本的时候，这个时候，你用控制字符作为边界，不用担心使用脚本的用户，在正则中输入和边界一样的字符。