Rubyで正規表現を中途半端に最適化する

foobar|fooxar|foozap|foozaのような正規表現は、パイプを減らしてfoo(?:bar|xar|zap?)とすることで高速に動作する。
とはいえ一発で後者のような正規表現はなかなか書きにくい。そこでそれを自動化するために書いたのが次のコード。

require 'forwardable'

class Regexp
  class Trie
    def self.union(*patterns)
      trie = new
      patterns.each { |pattern| trie << pattern }
      trie.to_regexp
    end

    extend Forwardable
    def_delegators :@map, :include?, :[], :[]=

    def initialize
      @map = {}
    end

    def add(expr)
      ref = self
      expr.each_char do |char|
        ref[char] = Trie.new unless ref.include?(char)
        ref = ref[char]
      end
      ref[''] = nil
    end
    alias << add

    def to_regexp
      return if @map.include?("") && @map.length == 1
      q = false
      alt, cc = *@map.each_with_object([[], []]) do |(char, value), (alt, cc)|
        quoted_char = Regexp.quote(char)
        if self[char]
          if recurse = value.to_regexp
            alt << quoted_char + recurse
          else
            cc << quoted_char
          end
        else
          q = true
        end
      end
      cconly = alt.empty?
      alt << (cc.size == 1 ? cc[0] : "[#{cc.join}]") unless cc.empty?
      result = alt.size == 1 ? alt[0] : "(?:#{alt * '|'})"
      result = cconly ? "#{result}?" : "(?:#{result})?" if q
      result
    end
  end
end

これは次のように使うことができる。

p Regexp::Trie.union("foobar", "fooxar", "foozap", "fooza") #=> "foo(?:bar|xar|zap?)"
p Regexp::Trie.union("a", "b", "c", "cca") #=> "(?:c(?:ca)?|[ab])"

その他の言語の実装

実を言うとこのアプローチは、様々な言語で実装されている。

• Regexp::Trie - search.cpan.org
• tokuhirom/regexp-trie
• alexeld/regex-trie

中途半端とは

中途半端にと書いたのは、メタ文字を考慮した最適化まではできていないから。
とはいえそこまでやってくれるoptimizerも他の言語には存在していて、次のようなものが挙げられる。

• Regexp::Assemble - search.cpan.org
• Regexp::AssembleをJavaScriptに移植してみた

Rubyにも移植したいよなぁと思いながらもなかなか手がつけられていない。

おわりに

正規表現もプログラミング言語同様、どんなコードを書くかによってパフォーマンスは雲泥の差が生じる。
こういった最適化のアプローチを知識として知っておくと、よりよい正規表現が書けるのではなかろうか。