最近、「何故、君はマウスを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のアルゴリズムのおもしろさが伝われば幸いです。
お詫びと訂正
本記事には訂正箇所が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%