gonp〜Goによるdiffのアルゴリズム実装〜

この記事は、2015年のGo Advent Calendarの25日目の記事です。

Go Advent Calendarのその2とその3ができる前、最終日だけ空いてて滑り込みで登録したのはいいけど、なんかネタないかなーと思いつつ、自分のgithubリポジトリを漁っていたらdiffのアルゴリズムをGoで実装したやつが出てきたので紹介してみます。

gonp〜Goによるdiffのアルゴリズム実装〜

gonpはGoによるdiffのアルゴリズム実装です。元々は昔々C++で書いたdtlというdiffライブラリの簡易移植で、diffを取るのに必要な以下の要素を求めることができます。

• 編集距離（Edit Distance）
• LCS（Longest Common Subsequence）
• SES（Shortest Edit Script）

diffのアルゴリズムにはさまざまな種類があり、中でもdiffに限らず様々な用途に応用可能な動的計画法が有名です。ただ、動的計画法を利用したdiffは計算量やメモリ使用量の観点から見てあまり効率的ではありません。そこでgonpでは動的計画法よりも計算量やメモリ使用量が小さいアルゴリズム（Sun Wu, Udi Manber, G.Myers, W.Miller, "An O(NP) Sequence Comparison Algorithm"）を使用しています。昔々Software Designに書いたdiffのアルゴリズムの解説記事がgihyo.jpで公開されているので詳しくはそちらをご覧下さい。

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

ちなみに、このアルゴリズムはSubversionのdiff実装のベースにもなっています。

gonpで２つの要素列の編集距離、LCS、SESを計算する

まずはgonpをインストールします。

go get -u github.com/cubicdaiya/gonp

以下は２つの文字列abcとabdの差分を求めるサンプルプログラムです。

diff.go

package main
 
import (
        "fmt"
        "github.com/cubicdaiya/gonp"
)
 
func main() {
        diff := gonp.New("abc", "abd")
        diff.Compose()
        fmt.Println("編集距離：", diff.Editdistance())
        fmt.Println("LCS：", diff.Lcs())
        fmt.Println("SES:")
        diff.PrintSes("+", "-", " ")
}

実行すると編集距離、LCS、SESが求められます。

$ go run diff.go
編集距離： 2
LCS： ab
SES:
  a
  b
- c
+ d

なお、日本語もちゃんと動きます。

diff_ja.go

package main

import (
        "fmt"
        "github.com/cubicdaiya/gonp"
)

func main() {
        diff := gonp.New("ごーらん", "あーらん")
        diff.Compose()
        fmt.Println("編集距離：", diff.Editdistance())
        fmt.Println("LCS：", diff.Lcs())
        fmt.Println("SES:")
        diff.PrintSes("+", "-", " ")
}

ちゃんと日本語単位で差分が出てますね。

$ go run diff_ja.go
編集距離： 2
LCS： ーらん
SES:
- ご
+ あ
  ー
  ら
  ん

アルゴリズムの言語別実装

gonpで利用しているアルゴリズムの原理は複雑ですが、実装は比較的簡単なので練習の意味合いでいろんな言語にポートしているので興味のある方は以下のリポジトリを御覧ください。言語によって実装具合に差異はありますが、C、D、Go、Java、JavaScript、Lua、Objective-C、Perl、Python、Ruby、Scalaでの実装があります。