11
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

Organization

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])"

その他の言語の実装

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

中途半端とは

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

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

おわりに

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
11
Help us understand the problem. What are the problem?