unoh.github.com

Software Design 6月号に「diffの動作原理を知る」の記事を執筆しました

2009-05-18 01:18:00 +0000


最近、「何故、君はマウスを2つ同時に使っているんだい?」と聞かれることが多くなったbokkoです。VX Revolution RXは右手用ですが、左手で使うならMicrosoftのArcがオススメです。近頃はフットマウスを買うかどうか真剣に悩んでいます。


Software Designには去年にも「ソースを読み,パッチを作成してみよう~GNU GLOBAL,diff,patchの使い方~」という記事を執筆する機会を頂いたので、本誌に執筆するのはこれが二度目になります。


今回の内容は以前当ブログに書いた「diff with C++」の記事をもっと濃くした感じになっていて、編集距離やLCS、SESの解説に始まり、Subversionのdiffエンジンや拙作のdtlで使われているWuのO(NP)差分アルゴリズムについて解説しています。


WuのO(NP)アルゴリズム(以下Wuのアルゴリズム)や、それによく似たMyersのO(ND)アルゴリズムをはじめとするエディットグラフを使って差分を求めるアルゴリズムは普段何気なく使っているdiffコマンドや各種バージョン管理システムで使われていることからもわかるようにとても有用であり、アルゴリズム自体の美しさやスマートさにも目を見張るものがあります。興味がある方はぜひ手にとって読んでみてください。本記事を通してdiffのアルゴリズムのおもしろさが伝われば幸いです。


sd0906cover.jpgのサムネール画像のサムネール画像


お詫びと訂正




本記事には訂正箇所が3箇所ほどあります。うち2つは本記事で使用しているdtlのバージョンが執筆後に0.05から0.06に上がったことによるもので、もう一つはWuのアルゴリズムの計算量に対する私の勘違いによるものです。詳しい内容についてはSoftware Design 2009年6月号:サポートページ|gihyo.jp ... 技術評論社をご覧下さい。


関係者や読者の方にはご迷惑をおかけしました。すみません。以後、気を付けます。


おまけ



本記事にはサンプルコードとしてWuのアルゴリズムを使って2つの文字列間の編集距離を求めるC++のプログラムが載っているのですが、ふと思い立って、同じことをするプログラムおよびLCSとSESも計算するプログラムをLuaで書いてみました。だからどうというわけでもないのですが、何か新しいプログラミング言語を触る際に、こんな風に自分にとってなじみのあるアルゴリズムを記述してみるのはその言語を勉強する上で、とてもいい方法だと再確認した次第です。


実際に書いていてハマったのですが、Luaではほかの大多数の言語と違って配列や文字列のインデックスが0からではなく1から始まるので、別の言語で記述されたアルゴリズムとかのコードを写経する際は注意しましょう。


しかし、この間、プログラマの友達とそんなLuaの独特の挙動について話をしていると、


まあ、(アルゴリズムの)論文に載っているような擬似コードは配列のインデックスが1から始まってるから、論文の擬似コードを写経する分にはちょうどいいんじゃね?


という感じのことを言われて「ああ、言われてみればそうだなあ」と妙に納得した次第です。とりあえず、今後、論文に載ってる疑似コードを実際のコードに落とす際はまずLuaで書いてそれからCとかC++に書き直すということを実践してみようと思います。


話が逸れました。以下にLuaによるWuのアルゴリズムの実装を2種類示します。その1が編集距離のみを計算するバージョン、その2が編集距離に加えてLCS、SESを計算するバージョンになります。なお、dtlと違ってワーストケース(LCSが極端に短くなる場合)への対応は行っていません。

LuaによるWuのアルゴリズムの実装 その1(編集距離のみ)



-- editDistance.lua
-- Lua5.1.4で動作確認
ONP = {}
function ONP.new (a, b)           -- ONPクラスのコンストラクタ
   local self = {                           -- メンバ変数
      A = a,
      B = b,
      M = string.len(a),
      N = string.len(b),
   }
   function self.editDistance ()  -- 編集距離を計算する
      offset = self.M + 1
      delta  = self.N - self.M
      size   = self.M + self.N + 3
      fp = {}
      for i = 0, size-1 do
	 fp[i] = -1
      end
      p = -1
      repeat
	 p = p + 1
	 for k=-p, delta-1, 1 do
	    fp[k+offset] = self.snake(k, math.max(fp[k-1+offset]+1, fp[k+1+offset]))
	 end
	 for k=delta+p,delta+1, -1 do
	    fp[k+offset] = self.snake(k, math.max(fp[k-1+offset]+1, fp[k+1+offset]))
	 end
	 fp[delta+offset] = self.snake(delta, math.max(fp[delta-1+offset]+1, fp[delta+1+offset]))
      until fp[delta+offset] >= self.N
      return delta + 2 * p
   end
   function self.snake (k, y)     -- 最遠点のy座標を計算する
      x = y - k
      while (x < self.M and y < self.N and 
	     string.sub(self.A, x+1, x+1) == string.sub(self.B, y+1, y+1)) 
      do
	 x = x + 1
	 y = y + 1
      end
      return y
   end
   if self.M >= self.N then       -- N >= Mになるように調整
      self.A, self.B = self.B, self.A
      self.M, self.N = self.N, self.M
   end
   return self
end
if #arg < 2 then
   error("few argument")
end
a = arg[1]
b = arg[2]
d = ONP.new(a, b)
print("editDistance:" .. d:editDistance())


実行



narazuya@bokkko% lua editDistance.lua abcdef dacfea
6
narazuya@bokkko% lua e.editDistancelua abc abd
2
narazuya@bokkko% 


LuaによるWuのアルゴリズムの実装 その2(編集距離、LCS、SES)



-- onp.lua
-- Lua5.1.4で動作確認
ONP = {}
SES_DELETE = -1
SES_COMMON = 0
SES_ADD    = 1
function ONP.new (a, b)          -- ONPクラスのコンストラクタ
   local self = {                          -- メンバ変数
      A = a,
      B = b,
      M = string.len(a),
      N = string.len(b),
      path       = {},
      pathposi   = {},
      P          = {},
      ses        = {},
      seselem    = {},
      lcs        = "",
      editdis    = 0,
      reverse    = false,
   }
   -- getter
   function self.geteditdistance () 
      return self.editdis
   end
   function self.getlcs ()
      return self.lcs
   end
   function self.getses ()
      return self.ses
   end
   -- constructor
   function self.P.new (x_, y_, k_)
      local self = { x=x_, y=y_, k=k_ }
      return self
   end
   function self.seselem.new (elem_, type_)
      local self = { elem=elem_, type=type_}
      return self
   end
   -- 差分構築
   function self.compose ()
      offset = self.M + 1
      delta  = self.N - self.M
      size   = self.M + self.N + 3
      fp = {}
      for i = 0, size-1 do
	 fp[i]        = -1
	 self.path[i] = -1
      end
      p = -1
      repeat
	 p = p + 1
	 for k=-p, delta-1, 1 do
	    fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])
	 end
	 for k=delta+p,delta+1, -1 do
	    fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])
	 end
	 fp[delta+offset] = self.snake(delta, fp[delta-1+offset]+1, fp[delta+1+offset])
      until fp[delta+offset] >= self.N
      self.editdis = delta + 2 * p
      r    = self.path[delta+offset]
      epc  = {}
      while r ~= -1 do
	 epc[#epc+1] = self.P.new(self.pathposi[r+1].x, self.pathposi[r+1].y, nil)
	 r = self.pathposi[r+1].k
      end
      self.recordseq(epc)
   end
   function self.snake (k, p, pp)     -- 最遠点のy座標を計算する
      r = 0;
      if p > pp then
	 r = self.path[k-1+offset];
      else
	 r = self.path[k+1+offset];
      end
      y = math.max(p, pp);
      x = y - k
      while (x < self.M and y < self.N and 
	     string.sub(self.A, x+1, x+1) == string.sub(self.B, y+1, y+1)) 
      do
	 x = x + 1
	 y = y + 1
      end
      self.path[k+offset] = #self.pathposi
      p = self.P.new(x, y, r)
      self.pathposi[#self.pathposi+1] = p
      return y
   end
   function self.recordseq (epc)          -- LCS、SESを記録する
      x_idx,  y_idx  = 1, 1
      px_idx, py_idx = 0, 0
      for i=#epc, 1, -1 do
	 while (px_idx < epc[i].x or py_idx < epc[i].y) do
	    if (epc[i].y - epc[i].x) > (py_idx - px_idx) then
	       elem = string.sub(self.B, y_idx, y_idx)
	       if self.reverse then 
		  type = SES_DELETE
	       else
		  type = SES_ADD
	       end
	       self.ses[#self.ses+1] = self.seselem.new(elem, type)
	       y_idx  = y_idx  + 1
	       py_idx = py_idx + 1
	    elseif epc[i].y - epc[i].x < py_idx - px_idx then
	       elem = string.sub(self.A, x_idx, x_idx)
	       if self.reverse then 
		  type = SES_ADD
	       else
		  type = SES_DELETE
	       end
	       self.ses[#self.ses+1] = self.seselem.new(elem, type)
	       x_idx  = x_idx  + 1
	       px_idx = px_idx + 1
	    else 
	       elem = string.sub(self.A, x_idx, x_idx)
	       type = SES_COMMON
	       self.lcs = self.lcs .. elem
	       self.ses[#self.ses+1] = self.seselem.new(elem, type)
	       x_idx  = x_idx  + 1
	       y_idx  = y_idx  + 1
	       px_idx = px_idx + 1
	       py_idx = py_idx + 1
	    end
	 end
      end
   end
   if self.M >= self.N then       -- N >= Mになるように調整
      self.A, self.B = self.B, self.A
      self.M, self.N = self.N, self.M
      self.reverse = true
   end
   return self
end
if #arg < 2 then
   error("few argument")
end
a = arg[1]
b = arg[2]
d = ONP.new(a, b)
d:compose()
print("editDistance:" .. d:geteditdistance()) -- 編集距離
print("LCS:"          .. d:getlcs())                    -- Longest Common Subsequence
print("SES")
ses = d:getses()                                          -- Shortest Edit Script
for i=1, #ses do
   if ses[i].type == SES_COMMON then
      print("  " .. ses[i].elem)
   elseif ses[i].type == SES_DELETE then
      print("- " .. ses[i].elem)
   elseif ses[i].type == SES_ADD then
      print("+ " .. ses[i].elem)
   end
end


実行



narazuya@bokkko% lua onp.lua abcdef dacfea
editDistance:6
LCS:acf
SES
+ d
  a
- b
  c
- d
- e
   f
+ e
+ a
narazuya@bokkko% lua a.lua abc abd
editDistance:2
LCS:ab
SES
  a
  b
- c
+ d
narazuya@bokkko%