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

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

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

https://github.com/cubicdaiya/gonp

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で2つの要素列の編集距離、LCS、SESを計算する

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

go get -u github.com/cubicdaiya/gonp

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

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での実装があります。

https://github.com/cubicdaiya/onp


『 Go 』Article List
Category List

Eye Catch Image
Read More

Androidに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

AWSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Bitcoinに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

CentOSに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

dockerに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

GitHubに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Goに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Javaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

JavaScriptに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Laravelに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Pythonに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Rubyに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Scalaに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Swiftに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Unityに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Vue.jsに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

Wordpressに関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。

Eye Catch Image
Read More

機械学習に関する現役のエンジニアのノウハウ・トレンドのトピックなど技術的な情報を提供しています。コード・プログラムの丁寧な解説をはじめ、初心者にもわかりやすいように写真や動画を多く使用しています。