一般記事

diffの動作原理を知る~どのようにして差分を導き出すのか

この記事を読むのに必要な時間:およそ 7 分

効率的な差分アルゴリズム

差分の計算をするには「編集距離」⁠LCS」⁠SES」を求めれば良いということがわかりました。しかし,差分の計算というのは非常に重い処理で,単純に2つの要素列を比較するようなプログラムでは,計算量がO(MN),必要なメモリがM×Nになってしまいます注3。そのため,実用的なdiffのプログラムには計算量や計算に必要なメモリの量を小さくする工夫が求められます。ここでは効率的なアルゴリズムの1つであり,dtlやSubversionで使用されているWuのアルゴリズムについて解説します。

注3)
M,Nはそれぞれの要素列の長さ。

Wuのアルゴリズム

Wuのアルゴリズムは平均的な計算量がO(N+PD),最悪の計算量がO(NP)であるアルゴリズムで,Nは2つの要素列の長さの和,PはSESにおける「削除」の合計数を表しています注4

エディットグラフと最短経路問題

Wuのアルゴリズムの基本的な考え方は,差分を計算するという問題を2つの要素列を図2のように,エディットグラフと呼ばれるグラフに見立てて,点(0,0)から点(M,N)注5までの(ある条件つきの)最短経路を求める問題に還元することにあります。言葉で説明するよりも図で説明したほうがわかりやすいと思うので,図2を見てください。

図2 エディットグラフ

※エディットグラフは,xを縦軸,yを横軸でよく扱うので,本稿でもそれに従っています。

図2 エディットグラフ

図のように,SESにおける「追加」「y軸方向に+1」⁠⁠削除」「x軸方向に+1」⁠また,互いの要素列の現在の要素が同一の場合,⁠y軸とx軸の対角線上に+1」というふうに定義します。そして「y軸方向に+1」⁠もしくは「x軸方向に+1」進むのに必要なコストを1,⁠y軸とx軸の対角線上に+1」進むのに必要なコストを0とします。このように考えると,2つの要素列の差分を計算するというのは,図2のようなエディットグラフの点(0,0)から点(M,N)まで進むのに必要なコストを最小限にする経路(SES)を求めることと等価だと考えることができます。

注4)
Dは編集距離。
注5)
M,Nはそれぞれ比較するそれぞれの要素列の長さです。また,N≧Mです。

Wuのアルゴリズムの動作原理

エディットグラフ上の最短経路を求めれば差分を計算できることがわかりました。

では,どのようにして最短経路を計算するのでしょうか。単純に1つひとつ総当たりで調べていくアルゴリズムだと,計算量はO(MN),またエディットグラフを表すデータ構造(たとえばM×Nの2次元配列)のためにM×Nのメモリが必要になります。

Wuのアルゴリズムは計算量が最悪の場合でもO(NP),また平均的な計算量がO(N+PD)となるので,かなりの改善が期待できます。それでは,このような少ない計算量を実現しているWuのアルゴリズムがどのように動作しているのか解説していきます注6

D=Δ+2P(※Δはデルタ)

まず,次のような約束事をします。

  • 2つの要素列の長さをM,N(N≧M)とし,Δ=N-Mとする
  • 編集距離をDとする
  • SESにおける「削除」の合計数をPとする

Δは2つの要素列の長さだけがわかっている際に,考えられる最小編集距離です。これは図3のよう考えるとわかりやすいと思います。

図3のように,片方の要素列が2つの要素列のLCSと完全に一致する場合(図3の例では「abc」⁠編集距離はΔ=N-M(N≧M)で表すことができます。

図3 Δ=Dとなる場合のエディットグラフ

図3 Δ=Dとなる場合のエディットグラフ

つまり,どんなにがんばっても編集距離はΔよりも小さい値にはならないわけです。

しかしそれ以外の場合,たとえば,⁠abec」「abcdef」の場合,図4のように編集距離はΔよりも大きくなります。

図4 LCSとSESを求める

$ ./strdiff abec abcdef
editDistance:4
LCS:abe
SES
  a
  b
+ c
+ d
  e
+ f
- c

この場合のエディットグラフを図5に示します。先述したように2つの要素列の長さだけからわかる最小の編集回数はΔです。

図5 Δ≠Dとなる場合のエディットグラフ

図5 Δ≠Dとなる場合のエディットグラフ

たとえばy軸方向へΔだけ進んだあとに(0,Δ)から(M,N)までの対角線k上を一気に進むことができれば,編集距離はΔになります。しかし,そうならない場合,対角線kの上側(下側)を通ることになります。ここで,エディットグラフ上のある性質が見てとれます。それは対角線k上からPだけy軸(x軸)方向に進んだ場合,最終的に点(M,N)にたどり着くには対角線k上に復帰する必要があるので,Pだけx軸(y軸)方向に進まなければならないということです。

また,対角線k上の点にたどり着くには最低でもコストがΔかかります。よって次の関係が成り立ちます。

  • D=Δ+P+P

  •  =Δ+2P

探索範囲を絞り込む

先ほど述べたように単純にひとつひとつ総当たりで調べていくのでは,計算量が大きくなってしまいます。そこで,Wuのアルゴリズムでは経路の探索範囲を図6のように絞り込むことによって,計算量を大幅に削減しています。このような絞り込みができるのは,最短経路がこの範囲外にある場合,⁠削除」の合計数Pの値が矛盾してしまうためです。

たとえば,図6のように対角線s上を通る経路では,どうがんばってもP=P+1となってしまいます。また,対角線t上を通る経路でも同様です。

図6 探索範囲の絞り込み

図6 探索範囲の絞り込み

著者プロフィール

久保達彦(くぼたつひこ)

インフラ兼ソフトウェアエンジニア。ピクシブ株式会社所属。

pixivのインフラの最適化や運用の省力化を提案・実行する傍らレコメンド・エンジンなどのソフトウェアの開発も行っている。

HP:http://cccis.jp/

twitter:@cubicdaiya

バックナンバー

プログラミング