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にも移植したいよなぁと思いながらもなかなか手がつけられていない。

おわりに

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