Hirschberg法 - Wu による O(NP) テキスト差分の試行 その 2

注意! この項の線形空間による O(NP) 実装は未だ試行中で、 テストしきれていません。 バグが潜んでいる可能性があります。

その 1 の続きです。

前回は、 編集距離の求め方に自信がもてなかったので、 当初コードに含めていた編集距離の計算部分を削り、 middle snake の座標だけを頼りに編集スクリプトの場合分けをしました。 その後、 いくつかのパターンを試してみていく過程で見つけた無限再帰呼び出しになってしまうケースの対策を施しました。 この致命的なバグの修正はその 1 のソースコードに反映済みです。

(編集距離) 双方向版での編集距離の計算方法を考えます。 片方向版の O(NP) での編集距離は Δ + 2 * p で求まります。 両方向版でも、 格子の反対の端へ到達するときは片方向版と同じ式で求まります。 一方、 途中で重なるときは、 k に依存している分を補正しつつ p のループで一つ前まで繰り返した p を勘定しなければいけません。 さらに、 順方向での重なりの分は一つ減らす必要があります。

2015 年 4 月 6 日修正: 重なったときに k によって生じるずれを、 Wu 等 An O(NP) Sequence Comparison Algorithm (1989) 2 節を参考にして補正するようにしました。

  1. 順方向で右端に到達したとき、 編集距離は Δ + 2 * p
  2. 逆方向で左端に到達したとき、 編集距離は Δ + 2 * p
  3. 順方向で重なったとき、 編集距離は Δ + 2 * ((k > Δ ? p + Δ - k : p) + (k < 0 ? p - 1 + k : p - 1))
  4. 逆方向で重なったとき、 編集距離は Δ + 2 * ((k+Δ > Δ ? p + Δ - (k+Δ) : p) + (k+Δ < 0 ? p + k+Δ : p))

(無限再帰バグ) その 1 で修正済みの無限再帰呼び出しになってしまうケースでは、 編集距離が 2 以上で x == a.size かつ y == b.size になっていました。 こうなると、 格子の分割ができず、 同じ格子を繰り返し再帰呼び出しで延々と処理しようとします。 末尾に文字を追加する場合および末尾から文字を削除する場合に無限再帰してしまっていたので、 致命的なバグになっていました。 これの対策は、 wu_shortest_edit_string に条件節を追加して、 一方から末尾の文字を削ってから再帰呼び出しします。

wu_shortest_edit_script("a", "aBC")
     a  B  C |      a  B  C
  0  .  .  . |   .  .  .  .
a .  0  0  0 | a .  .  .  .
=> (x,y)=(1,3) (u,v)=(1,3)

wu_shortest_edit_script("a", "aBCDEF")
     a  B  C  D  E  F |      a  B  C  D  E  F
  0  .  .  .  .  .  . |   .  .  .  .  .  .  .
a .  0  0  0  0  0  0 | a .  .  .  .  .  .  .
=> (x,y)=(1,6) (u,v)=(1,6)

wu_shortest_edit_script("Ba", "aC")
     a  C |      a  C
  0  1  . |   .  .  .
B 1  .  . | B .  .  .
a .  1  1 | a .  .  0
=> (x,y)=(2,2) (u,v)=(2,2)

wu_shortest_edit_script("Bhijklmn", "hijklmnC")
     h  i  j  k  l  m  n  C |      h  i  j  k  l  m  n  C
  0  1  .  .  .  .  .  .  . |   .  .  .  .  .  .  .  .  .
B 1  .  .  .  .  .  .  .  . | B .  .  .  .  .  .  .  .  .
h .  1  .  .  .  .  .  .  . | h .  .  .  .  .  .  .  .  .
i .  .  1  .  .  .  .  .  . | i .  .  .  .  .  .  .  .  .
j .  .  .  1  .  .  .  .  . | j .  .  .  .  .  .  .  .  .
k .  .  .  .  1  .  .  .  . | k .  .  .  .  .  .  .  .  .
l .  .  .  .  .  1  .  .  . | l .  .  .  .  .  .  .  .  .
m .  .  .  .  .  .  1  .  . | m .  .  .  .  .  .  .  .  .
n .  .  .  .  .  .  .  1  1 | n .  .  .  .  .  .  .  .  0
=> (x,y)=(8,8) (u,v)=(8,8)

(middle snake 捕捉) トレースを眺めていると、 もう一つ改善するべきパターンが見つかります。 p == 0 で順方向へ末尾まで辿ってしまうとき、 middle snake を飛び越してしまって末尾の snake を返してしまいます。 これでは、 Hirschberg 法の分割統治がうまく働かないので、 middle snake として y が (n + 1) / 2 に一致する点を含む snake を捕捉することにします。

wu_shortest_edit_script("hijklmn", "hiAPjkINlmn")
     h  i  A  P  j  k  I  N  l  m  n |      h  i  A  P  j  k  I  N  l  m  n
  0  .  .  .  .  .  .  .  .  .  .  . |   .  .  .  .  .  .  .  .  .  .  .  .
h .  0  .  .  .  .  .  .  .  .  .  . | h .  .  .  .  .  .  .  .  .  .  .  .
i .  .  0  0  0  .  .  .  .  .  .  . | i .  .  .  .  .  .  .  .  .  .  .  .
j .  .  .  .  .  0  .  .  .  .  .  . | j .  .  .  .  .  .  .  .  .  .  .  .
k .  .  .  .  .  .  0  0  0  .  .  . | k .  .  .  .  .  .  .  .  .  .  .  .
l .  .  .  .  .  .  .  .  .  0  .  . | l .  .  .  .  .  .  .  .  .  .  .  .
m .  .  .  .  .  .  .  .  .  .  0  . | m .  .  .  .  .  .  .  .  .  .  .  .
n .  .  .  .  .  .  .  .  .  .  .  0 | n .  .  .  .  .  .  .  .  .  .  .  .
=> (x,y)=(4,8) (u,v)=(7,11) "lmn" を返します。
#=> (x,y)=(2,4) (u,v)=(4,6) 格子分割には "jk" の方が適切です。

以上を取り込んだ改善版を作ります。 wu_midsnake に middle snake 捕捉と編集距離計算を盛り込みます。

def wu_midsnake(a0, b0)
  if a0.size <= b0.size
    a, b = a0, b0
  else
    b, a = a0, b0
  end
  m = a.size
  n = b.size
  # fgrid = Array.new(m + 1) { Array.new(n + 1) }
  fp = Array.new(m + n + 3, -1)
  # rgrid = Array.new(m + 1) { Array.new(n + 1) }
  rp = Array.new(m + n + 3, n + 1)
  delta = n - m
  pb = -1
  while delta + 4 * (pb + 1) - 2 <= m + n
    pb = pb + 1
    ymid = (n + 1) / 2      # 追加 (middle snake 捕捉)
    midsnake = nil          # 追加 (middle snake 捕捉)
    (-pb).upto(pb + delta) do |k0|
      is_midsnake = false   # 追加 (middle snake 捕捉)
      k = k0 < delta ? k0 : pb + delta - (k0 - delta)
      y = [fp[k - 1] + 1, fp[k + 1]].max
      x = y - k
      u, v = x, y
      while x < m and y < n and a[x] == b[y]
        # fgrid[x][y] = pb
        is_midsnake = true if y == ymid   # 追加 (middle snake 捕捉)
        x += 1
        y += 1
      end
      # fgrid[x][y] = pb if x <= m and y <= n
      fp[k] = y
      midsnake = [u, v, x, y] if is_midsnake or (x <= m and y == ymid)  # 追加 (middle snake 捕捉)
      if y == n or (pb > 0 and k >= -(pb - 1) and k <= pb - 1 + delta and y >= rp[k])
        #d = y == n ? delta + 2 * pb : delta + 4 * pb - 2    # 削除 (編集距離)
        fpb = k > delta ? pb + delta - k : pb
        rpb = k < 0 ? pb - 1 + k : pb - 1
        d = y == n ? delta + 2 * pb : delta + 2 * (fpb + rpb)  # 追加 (編集距離)
        if pb == 0 and d > 1 and x == m and y == n and not midsnake.nil?
          u, v, x, y = midsnake     # 追加 (middle snake 捕捉)
        end
        if a0.size <= b0.size
          return [d, u, v, x, y]    # 追加 (編集距離)
        else
          return [d, v, u, y, x]    # 追加 (編集距離)
        end
      end
    end
    (delta + pb).downto(-pb) do |k0|
      kdelta = k0 > 0 ? k0 : -(pb + k0)
      y = [rp[kdelta - 1], rp[kdelta + 1] - 1].min
      x = y - kdelta
      u, v = x, y
      while x > 0 and x <= m and y > 0 and a[x - 1] == b[y - 1]
        # rgrid[x][y] = pb
        x -= 1
        y -= 1
      end
      # rgrid[x][y] = pb if x >= 0 and x <= m and y >= 0
      rp[kdelta] = y
      if y == 0 or (kdelta >= -pb and kdelta <= pb + delta and y <= fp[kdelta])
        #d = y == 0 ? delta + 2 * pb : delta + 4 * pb    # 削除 (編集距離)
        fpb = kdelta > delta ? pb + delta - kdelta : pb
        rpb = kdelta < 0 ? pb + kdelta : pb
        d = y == 0 ? delta + 2 * pb : delta + 2 * (fpb + rpb)  # 追加 (編集距離)
        if a0.size <= b0.size
          return [d, x, y, u, v]    # 追加 (編集距離)
        else
          return [d, y, x, v, u]    # 追加 (編集距離)
        end
      end
    end
  end
  raise RuntimeError, "cannot happen"
end

格子を分割して再帰する wu_shortest_edit_script を編集距離を使うように修正して、 無限再帰バグを潰します。

def wu_shortest_edit_script(a, b)
  return b.each_char.map{|c| "+" + c } if a.empty?
  return a.each_char.map{|c| "-" + c } if b.empty?
  if a.size == 1
    x = b.rindex(a)
    return b.each_char.map{|c| "+" + c} + ["-" + a] if x.nil?
    b0, b1 = b[0 ... x], b[x + 1 ... b.size] || ""
    return b0.each_char.map{|c| "+" + c } + [" " + a] + b1.each_char.map{|c| "+" + c }
  elsif b.size == 1
    x = a.rindex(b)
    return ["+" + b] + a.each_char.map{|c| "-" + c} if x.nil?
    a0, a1 = a[0 ... x], a[x + 1 ... a.size] || ""
    return a0.each_char.map{|c| "-" + c } + [" " + b] + a1.each_char.map{|c| "-" + c }
  end
  d, x, y, u, v = wu_midsnake(a, b)
  if d == 0
    a.each_char.map{|c| " " + c }
  elsif d == 1 and x < y and x == a.size and y == b.size
    a.each_char.map{|c| " " + c } + ["+" + b[y - 1]]
  elsif d == 1 and x > y and x == a.size and y == b.size
    b.each_char.map{|c| " " + c } + ["-" + a[x - 1]]
  elsif d == 1 and u - x == a.size
    ["+" + b[0]] + a.each_char.map{|c| " " + c }
  elsif d == 1 and v - y == b.size
    ["-" + a[0]] + b.each_char.map{|c| " " + c }
  elsif x == a.size and y == b.size and a.size <= b.size    # 追加 (無限再帰バグ)
    wu_shortest_edit_script(a[0 ... x], b[0 ... y - 1]) + ["+" + b[-1]]
  elsif x == a.size and y == b.size                         # 追加 (無限再帰バグ)
    wu_shortest_edit_script(a[0 ... x - 1], b[0 ... y]) + ["-" + a[-1]]
  else
    a0, a1 = a[0 ... x], a[u ... a.size] || ""
    mc = a[x ... u] || ""
    b0, b1 = b[0 ... y], b[v ... b.size] || ""
    wu_shortest_edit_script(a0, b0) + mc.each_char.map{|c| " " + c } + wu_shortest_edit_script(a1, b1)
  end
end

動作確認に使っているテストです。

def test
  ntest = 0
  nfail = 0
  pieces = ["", "a", "a", "b", "cde", "fghijk"]
  (0 .. 5).to_a.permutation(4).to_a.combination(2).to_a.map {|x, y|
    [x.map{|i| pieces[i] }.join, y.map{|i| pieces[i] }.join]
  }.sort.uniq.each {|a, b|
    ntest += 1
    ses = wu_shortest_edit_script(a, b)
    s = ""
    t = ""
    ses.each do |u|
      s << u[1] if u[0] != '+'
      t << u[1] if u[0] != '-'
    end
    if s != a or t != b
      nfail += 1
      puts '---%s:%s +++%s:%s' % [a.inspect, s.inspect, b.inspect, t.inspect]
      ses.each{|u| puts u }
      puts
    end
  }
  puts '%d tests %d fails' % [ntest, nfail]
end

test #=> 6438 tests 0 fails