天泣記

Excel の罫線で木構造を描いてあるドキュメントを眺めて毒づきつつ、ふと 2次元空間に対する正規表現を思いついた。

正規表現での単一文字のマッチは、「現在の位置」にある文字があることを確認した後、現在位置を「右に」一文字ずらすという動作である。

そして、単一文字のマッチ以外に「現在の位置」をずらす機能はない。

とすると、そこを右だけじゃなくて上下左右にずらせるようにするだけで、2次元に拡張できるのではないか?

そうするための拡張方法はとりあえずふたつ考えられる。

単一文字のマッチで位置をずらすのは変えず、ただしエンジン内でずらす方向を保持し、その方向を修正する指示をつくる。たとえば、1次元正規表現の [:lit, "a"] と同じ意味が 2次元正規表現では [:cat, [:dir, :right], [:lit, "a"]] で表現できるようにする。つまり、[:dir, :right] でエンジン内の方向を指定し、[:lit, "a"] は指定された :right な方向に進む。 (方向の絶対指定と相対指定を区別するためには、絶対指定は上下左右じゃなくて東西南北にしたほうがいいかもしれない)
単一文字のマッチを、マッチと位置の移動のふたつに分解し、位置の移動を上下左右にできるようにする。たとえば、1次元正規表現の [:lit, "a"] と同じ意味が 2次元正規表現では [:cat, [:lit, "a"], [:move, :right]] で表現できるようにする。つまり、[:lit, "a"] では位置は動かず、[:move, :right] で :right な方向に進む。

とりあえず前者で実装してみよう。

% cat 2d.rb
def match(pat, strary, start=[0,0], dir=:right)
  map = {}
  strary.each_with_index {|str, y|
    str.each_char.with_index {|ch, x|
      map[[x,y]] = ch
    }
  }
  try(pat, map, [start], dir) {|path2, dir2|
    return path2
  }
  nil
end

def try(pat, map, path, dir, &b)
  case pat[0]
  when :lit; _, ch = pat; try_lit(ch, map, path, dir, &b)
  when :cat; _, *rs = pat; try_cat(rs, map, path, dir, &b)
  when :alt; _, *rs = pat; try_alt(rs, map, path, dir, &b)
  when :rep; _, *rs = pat; try_rep(rs, map, path, dir, &b)
  when :dir; _, d = pat; try_dir(d, map, path, dir, &b)
  else raise "unexpected: #{pat.inspect}"
  end
end

def try_dir(d, map, path, dir)
  yield path, d
end

def try_lit(ch, map, path, dir)
  if map[path.last] && map[path.last] == ch
    x, y = path.last
    case dir
    when :right then x += 1
    when :left then x -= 1
    when :up then y -= 1
    when :down then y += 1
    end
    yield [*path, [x,y]], dir
  end
end

# r1 r2 ...
def try_cat(rs, map, path, dir, &block)
  if rs.empty?
    yield path, dir
  else
    r, *rest = rs
    try(r, map, path, dir) {|path2, dir2|
      try_cat(rest, map, path2, dir2, &block)
    }
  end
end

# r1 | r2 | ...
def try_alt(rs, map, path, dir, &block)
  rs.each {|r|
    try(r, map, path, dir, &block)
  }
end

# (r1 r2 ...)*
def try_rep(rs, map, path, dir, &block)
  try_cat(rs, map, path, dir) {|path2, dir2|
    if !path[0...-1].include?(path.last) # xxx: cannot cross.
      try_rep(rs, map, path2, dir2, &block)
    end
  }
  yield path, dir
end

strary = [
  "************",
  "* *   * *  *",
  "* ***      *",
  "*   * **** *",
  "* *   *G   *",
  "************",
]

pat = [:cat,
        [:rep,
          [:alt, [:dir, :right], [:dir, :left], [:dir, :up], [:dir, :down]],
          [:lit, " "]],
        [:lit, "G"]]

require 'pp'
pp match(pat, strary, [1,1])

% ruby 2d.rb
[[1, 1],
 [1, 2],
 [1, 3],
 [2, 3],
 [3, 3],
 [3, 4],
 [4, 4],
 [5, 4],
 [5, 3],
 [5, 2],
 [6, 2],
 [7, 2],
 [8, 2],
 [9, 2],
 [10, 2],
 [10, 3],
 [10, 4],
 [9, 4],
 [8, 4],
 [7, 4],
 [6, 4]]

とりあえず、迷路を解けている。(初期位置の左上 (1,1) から G と描いてある (7,4) を突き抜けた (6,4) までの経路が得られている。突き抜けているのは G の文字にマッチした後、位置をひとつ進めるから)

[:cat,
  [:rep,
    [:alt, [:dir, :right], [:dir, :left], [:dir, :up], [:dir, :down]],
    [:lit, " "]],
  [:lit, "G"]]

というパターンは、4方向のどれか方向を設定して、一文字空白を進み、それを 0回以上繰り返して、G にたどりつく、というものである。

しかし、実装して気がついたのだが、問題は繰り返しの無限再帰防止検査である

1次元正規表現では以下のように、繰り返しのそれぞれでまったく進まなかったケースはそれ以降調べないというものであった。

def try_rep(r, ary, pos, &block)
  try(r, ary, pos) {|pos2|
    if pos < pos2
      try_rep(r, ary, pos2, &block)
    end
  }
  yield pos
end

2次元正規表現では、(まだまじめに考えていないが) とりあえず以下のように今までに通った位置だったらそれ以降調べない、としてみた。

def try_rep(rs, map, path, dir, &block)
  try_cat(rs, map, path, dir) {|path2, dir2|
    if !path[0...-1].include?(path.last) # xxx: cannot cross.
      try_rep(rs, map, path2, dir2, &block)
    end
  }
  yield path, dir
end

どうやるのが適切だろうか。

まじめにやるなら、その繰り返しの各サイクルで同じ場所になってはならない、というのがいいか。

def try_rep(rs, map, path, dir, visited={}, &block)
  return if visited[path.last]
  visited2 = visited.dup
  visited2[path.last] = true
  try_cat(rs, map, path, dir) {|path2, dir2|
    if visited2[path.last]
      try_rep(rs, map, path2, dir2, visited2, &block)
    end
  }
  yield path, dir
end

天泣記

2011-03-01 (Tue)

2011-03-06 (Sun)

2011-03-08 (Tue)

2011-03-10 (Thu)

2011-03-11 (Fri)

2011-03-13 (Sun)

2011-03-16 (Wed)

2011-03-26 (Sat)

2011-03-27 (Sun)

2011-03-30 (Wed)