春の入門祭りの8日目です。

文字列の新旧の違いを表現する時によくdiffをとるとか言いますよね。そこで実行されるのが差分アルゴリズムです。差分のアルゴリズムって結構知れば知るほど難しいやつです。「より良い差分」という基準が、状況によって変わるからです。ヒューリスティックなやつです。例えば、HTMLの説明の文章を書いていたとします。タイトルをテーブルに書き換えてみたとします。

<title>

どちらの差分の方がわかりやすいでしょうか？

- <title>
+ <table>

  <t
- it
+ ab
  le>

どちらも間違ってはおらず、この差分を元にパッチを当てたりも可能です。ただ、読んだ時の読みやすさが違います。

これはもちろん前者と答える人の方が多いでしょう。だって、タグという意味の塊が維持されていますからね。
これは究極的にはわかりやすいdiffというのは「意味」を理解しないと作れないということを意味します。これがdiffは簡単なようで難しいと書いた理由です。もちろん、ほどほどの工数で、ほどほどの見た目のdiffも作成可能です。

案件の中で「とりあえず差分を」となるとあまり細かい部分まで詰めきれないことが多いと思います。差分の表示の質はどちらかというと、「あれば嬉しい」話で、「ないと困る」という線引きがしにくいものです。とりあえず出せてしまったらそこで試合終了になることも多いかも知れません。というか、そもそも差分アルゴリズムを案件で使おうという議論にもあまりならない気がします。

個人的には結構工夫しがいがあってお気に入りの差分アルゴリズムについて、それが何者であるか、どのような特製があって、どのような工夫ができるのかを紹介していきます。この説明では、Google製のdiff-match-patchのGo移植を元に説明していきますが、基本的な考え方は他の実装でも使えると思います。なお、このライブラリはdiff以外にmatchとpatchの機能もありますが、このエントリーではdiffのみを扱います。

差分検知では何が行われるのか？

さっそく、差分を表示してみます。

package main

import (
	"log"

	"github.com/sergi/go-diff/diffmatchpatch"
)

const (
	text1 = "github.com/mattn_jp/go-sqlite3"
	text2 = "github.com/shibukawa/nanogui-go"
)

func main() {
	dmp := diffmatchpatch.New()

	diffs := dmp.DiffMain(text1, text2, false)

	log.Println(diffs)
}

[{Equal github.com/} {Delete m} {Insert shibuk}]みたいなテキストで出力されますが、手動でdiffコマンド的に出力をわかりやすく表示すると以下のようになります。

  github.com/
- m
+ shibuk
  a
- tt
+ wa/
  n
- _jp/
+ anogui-
  go
- -sqlite3

結果のdiffsは差分のリストで、文字列片ごとに、Equal/Insert/Deleteのフラグ(Type)がついたものです。

type Diff struct {
    Type Operation
    Text string
}

差分アルゴリズムがやっていることは、この編集リストを作るのがお仕事です。ちなみに、このEqualとInsertだけをピックアップして文字列を結合すれば新しい文字列が、EqualとDeleteだけをピックアップすると古い文字列になります。

文章を編集するアクションのリストなので、ここからレーベンシュタイン距離を計算することもできます。diff-match-patchのライブラリではまさにその関数が提供されています。レーベンシュタイン距離はInsertやDeleteが多いほどスコアが上がるアルゴリズムで、単語同士の距離を計算できます。

log.Println(dmp.DiffLevenshtein(diffs))
// output: 24

レーベンシュタイン距離を使うと、ユーザーが入力したコマンドが、利用可能なコマンドリストのどれにもマッチしないときに、一番近いコマンド名を出して「これを入力しようとしたんでしょうか？」と聞くことができます。

出力部分の補助関数

diffの結果を加工する関数がいくつか提供されています。HTMLにしたり、カラーコード付きでコンソール出力したり、diffから元のテキストを復元したり、diffのテキストのように出力したり・・・

func (dmp *DiffMatchPatch) DiffPrettyHtml(diffs []Diff) string
func (dmp *DiffMatchPatch) DiffPrettyText(diffs []Diff) string
func (dmp *DiffMatchPatch) DiffText1(diffs []Diff) string
func (dmp *DiffMatchPatch) DiffText2(diffs []Diff) string
func (dmp *DiffMatchPatch) DiffToDelta(diffs []Diff) string

基本の検知ロジックのカスタマイズ

マッチを探す文字数の範囲やコスト計算のパラメータ調整は構造体の属性をいじると行えます。diff以外のmatchとpatch用のパラメータもあります。とはいえ、これだけで「見やすいdiff」を作り出すのは難しいと思います。そのため、基本の差分ロジックの出力を後から変更していく方法をこのあと紹介します。

type DiffMatchPatch struct {
    // Number of seconds to map a diff before giving up (0 for infinity).
    DiffTimeout time.Duration
    // Cost of an empty edit operation in terms of edit characters.
    DiffEditCost int
    // How far to search for a match (0 = exact location, 1000+ = broad match). A match this many characters away from the expected location will add 1.0 to the score (0.0 is a perfect match).
    MatchDistance int
    // When deleting a large block of text (over ~64 characters), how close do the contents have to be to match the expected contents. (0.0 = perfection, 1.0 = very loose).  Note that MatchThreshold controls how closely the end points of a delete need to match.
    PatchDeleteThreshold float64
    // Chunk size for context length.
    PatchMargin int
    // The number of bits in an int.
    MatchMaxBits int
    // At what point is no match declared (0.0 = perfection, 1.0 = very loose).
    MatchThreshold float64
}

後処理でのdiffの統合

最初のサンプルをみた時に、わかりにくかった原因は「細かすぎる」ことにありました。diff-match-patchはデフォルトではなるべく細かい差分を見つけようとします。ただ、それではわかりにくかったりするので、行ごとの差分になるようにしたり「編集リストをまとめて数を減らす」のが基本的なチューニングの方向性になります。

例えばこの差分は、Equalが2つ、DeleteとInsertが1つずつのリストになっています。

  <t
- it
+ ab
  le>

で、読みやすい方は、Equal要素はDeleteとInsertにそれぞれマージされています。

- <title>
+ <table>

diff-match-patchには、デフォルトのアルゴリズムで作成した編集リストを、ある程度まとめてわかりやすくする関数がいくつも提供されています。

func (dmp *DiffMatchPatch) DiffCleanupEfficiency(diffs []Diff) []Diff
func (dmp *DiffMatchPatch) DiffCleanupMerge(diffs []Diff) []Diff
func (dmp *DiffMatchPatch) DiffCleanupSemantic(diffs []Diff) []Diff
func (dmp *DiffMatchPatch) DiffCleanupSemanticLossless(diffs []Diff) []Diff

それぞれ、異なる戦略でマージしようとします。DiffCleanupEfficiency()とDiffCleanupSemantic()の結果は次の通りです。他の2つはこの入力では変わりませんでした。

  github.com/
- mattn_jp/
+ shibukawa/nanogui-
  go
- -sqlite3

  github.com/
- mattn_jp/go-sqlite3
+ shibukawa/nanogui-go

行単位のdiff

複数行のテキストを今までの関数に入れてみます。行頭に改行が来たり、テキストの中に来たり、まちまちです。そのまま色付きで表示してもなんかわかりにくい表示結果になりがちです。

  github.com/
- mattn_jp/go-sqlite3
+ shibukawa/nanogui-go
  (改行)github.com/labstack/echo(改行)github.com/g
- orilla/mux
+ in-gonic/gin
  (改行)

この結果をゴニョゴニョ直しても良いのですが、行単位でのdiffでは今までとは違うメソッドを使って入力と出力をフィルターすることで読みやすい差分出力を行うロジックが提供されています。

package main

import (
	"log"

	"github.com/sergi/go-diff/diffmatchpatch"
)

const (
	text1 = "github.com/mattn_jp/go-sqlite3"
	text2 = "github.com/shibukawa/nanogui-go"
)

func main() {
	dmp := diffmatchpatch.New()
	a, b, c := dmp.DiffLinesToChars(text1, text2)
	diffs := dmp.DiffMain(a, b, false)
	diffs = dmp.DiffCharsToLines(diffs, c)

	log.Println(diffs)
}

- Delete github.com/mattn_jp/go-sqlite3(改行)
+ Insert github.com/shibukawa/nanogui-go(改行)
  github.com/labstack/echo(改行)
- Delete github.com/gorilla/mux(改行)
+ Insert github.com/gin-gonic/gin(改行)

見慣れたdiffが出てきましたね。

これ、何をしているかというと、入力のテキストを行単位にわけ、1行1文字となるように、前処理をしているのですよね。そして、最後に文字を行に戻しています。文字というのは、それ以上は分られない単位ですので、この前処理を行うことで行単位でのdiffが出力されるわけです。

応用編: GitHubのようなdiff

みなさんが見慣れているGitHubでは、行単位のdiffの中に、文字単位のdiffが入った出力が行われます。この出力の情報量は多く、長い行の一部が変更された場合などに力を発揮します。

これを実現するには既製のライブラリをそのまま使うだけではダメで、いろいろ後処理を加える必要があります。完成品はこちらにあります。

やっていることは単純で、diffsの差分の結果中で、Delete→Insertの順番に並んでいるところを見つけ、その差分を行内のdiffとして出力してあげればいけます。

なお、GitHubの場合は新旧の行番号を両方表示しているため、そこをエミュレーションするにはdiffsのテキストを解析し、新旧の行番号をカウントしてあげる必要があります。上記のコードではまずさいしょにこの処理を行っています。Equalなら両方の、Deleteなら旧の方のみ、Insertなら新の方のみの行カウンターをインクリメントする、みたいな感じですね。

これらの処理を組み合わせることで、次のような行単位差分と、その中のテキスト単位差分を出しつつ、新旧の行数を両方出す（unified形式）で出したのが次のスクリーンショットです。まあ、テキスト単位差分はもうちょっと何かしらの後処理はした方が良いですが、とりあえず実証実験ということで。

まとめ

diffのアルゴリズムと応用について紹介しました。

diffってすごく人間臭いアルゴリズムだと思うんですよね。そもそもすべてがきちんと動いている・情報が把握されている場合にはあまり必要とされない。間違った時、間違いを見つけようとした時ほど役立つんですよね。フューチャーが扱うようなシステムでも必須要件に入ることはあまりないと思いますし、僕が前職でやっていたような社内SE業でも必ずしも必要とされない。でも、それを知っていると、もしユーザーが間違った時に「もしかしてこれじゃないですか？」「前回の設定との違いはこれですよ。間違いの原因はこの中にありますか？」みたいな親切なことができるんですよね。

「なくても困らないけど、あったら嬉しい」ものって、ほとんどの場合「付加価値」を提供するものです。diffアルゴリズムも自分が使える道具の中に入れておくと、いざと言う時に「最低限を満足するだけのシステム」から「すごく親切なシステム」にパワーアップできると思います。