この記事でわかること

sergi/go-diff/diffmatchpatchパッケージの基本的な使い方
DiffMain()関数による差分検出の実装方法
差分検出の「視点」という重要な概念
checklinesパラメータによるパフォーマンス調整

対象読者

Goでテキスト差分検出を実装している開発者
バージョン管理やドキュメント管理システムを開発している方
diffmatchpatchパッケージの挙動を理解したい方

概要

sergi/go-diff/diffmatchpatchは、Googleの「Diff-Match-Patch」アルゴリズムをGo言語に移植したパッケージです。2つのテキスト間の差分を文字レベルで検出し、構造化されたデータとして返します。本記事では、このパッケージの基本的な使い方と、差分検出の「視点」という重要な概念について解説します。

sergi/go-diff/diffmatchpatchとは

パッケージの概要

sergi/go-diff/diffmatchpatchは、2つのテキスト間の差分を文字レベルで検出するパッケージです。

公式リポジトリ: https://github.com/sergi/go-diff

主な特徴:

Myers差分アルゴリズムによる効率的な実装
追加・削除・変更なしの3種類で差分を表現
UTF-8対応（日本語や絵文字も正しく処理）
Go modulesで簡単にインストール可能

元となるアルゴリズム

このパッケージは、Googleが開発した「Diff-Match-Patch」アルゴリズムのGo言語実装です。

Diff-Match-Patch: https://github.com/google/diff-match-patch

同じアルゴリズムは、Google Docs、GitHub、Wikipediaなどでも使用されています。

Myers差分アルゴリズムとは

Myers差分アルゴリズムは、1986年にEugene W. Myersによって発表された、2つのテキスト間の最短編集距離を求めるアルゴリズムです。

特徴:

最小の編集操作（追加・削除）で変換する手順を見つける
動的計画法ベースで効率的に計算
多くのバージョン管理システムで採用されている標準的なアルゴリズム

参考論文: An O(ND) Difference Algorithm and Its Variations

GitHubのPull Request機能やGitのgit diffコマンドも、このMyers差分アルゴリズムをベースにしています。本パッケージを使うことで、GitHubのPRのような差分表示機能を自分のアプリケーションに実装できます。

インストール

go get github.com/sergi/go-diff/diffmatchpatch

Diff-Match-Patchの3つの機能

パッケージ名の「Diff-Match-Patch」が示す通り、このライブラリは3つの主要機能を提供しています。本記事ではDiff機能のみを解説します。

1. Diff（差分検出）

2つのテキスト間の差分を検出します。本記事で解説する機能です。

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

2. Match（パターンマッチング）

テキスト内で指定したパターンに最も近い位置を検索します。あいまい検索（fuzzy matching）に対応しており、完全一致でなくても類似した箇所を見つけられます。

// text内でpatternに最も近い位置を検索
location := dmp.MatchMain(text, pattern, expectedLocation)

3. Patch（差分適用）

Diffで検出した差分情報を別のテキストに適用します。バージョン管理システムのパッチ機能に相当します。

// 差分からパッチを生成
patches := dmp.PatchMake(text1, diffs)
// パッチを適用
text2, _ := dmp.PatchApply(patches, text1)

これら3つの機能を組み合わせることで、リアルタイム共同編集やバージョン管理システムなどの複雑な機能を実装できます。

基本的な使い方

最小構成のコード

package main

import (
    "fmt"
    "github.com/sergi/go-diff/diffmatchpatch"
)

func main() {
    dmp := diffmatchpatch.New()
    
    text1 := "Hello World"
    text2 := "Hello Go"
    
    diffs := dmp.DiffMain(text1, text2, false)
    
    fmt.Println(diffs)
}

出力:

[{Equal Hello } {Delete Worl} {Insert G} {Equal o}]

Operation型はString()メソッドを実装しているため、-1/0/1ではなくDelete/Equal/Insertとして表示されます。

返却値の構造

DiffMain()関数は、Diff構造体のスライスを返します。

type Diff struct {
    Type Operation  // 差分のタイプ
    Text string     // 該当するテキスト
}

type Operation int8
const (
    DiffDelete Operation = -1  // 削除
    DiffEqual  Operation = 0   // 変更なし
    DiffInsert Operation = 1   // 追加
)

各タイプの意味:

DiffDelete (-1): text1にあるがtext2にない（削除された部分）
DiffEqual (0): 両方に存在する（変更なし）
DiffInsert (1): text1にないがtext2にある（追加された部分）

差分検出の「視点」を理解する

DiffMain()の引数の意味

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

この関数は text1をtext2に変えるには何が必要かという視点で差分を検出します

DiffDelete: text2にするには削除が必要（text1にあるがtext2にない）
DiffInsert: text2にするには追加が必要（text1にないがtext2にある）
DiffEqual: 両方に存在（変更不要）

具体例1: シンプルな追加

text1 := "Hello World"
text2 := "Hello Beautiful World"

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

返却値:

[{Equal Hello } {Insert Beautiful } {Equal World}]

"Hello "と"World"はそのままで、"Beautiful "を追加すればtext2になります。

具体例2: 複雑な変更

text1 := "hello world"
text2 := "hallo wold"

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

返却値:

[{Equal h} {Delete e} {Insert a} {Equal llo wo} {Delete r} {Equal ld}]

diffmatchpatchは文字レベルで詳細に差分を検出します。

DiffMain()関数の詳細

関数シグネチャ

func (dmp *DiffMatchPatch) DiffMain(text1, text2 string, checklines bool) []Diff

引数:

text1: 比較元のテキスト
text2: 比較先のテキスト
checklines: 行単位での最適化を行うかどうか

返り値:

[]Diff: 差分情報のスライス

内部処理の流れ

DiffMain()関数は内部で以下の処理を実行します：

前処理: 共通接頭辞・接尾辞の除去
差分検出: Myers差分アルゴリズムで最小編集距離を計算
後処理: 連続する小さな差分をマージして可読性を向上

checklinesパラメータによるパフォーマンス調整

パラメータの使い分け

// false: 文字レベルで直接比較
diffs := dmp.DiffMain(text1, text2, false)

// true: 行レベル→文字レベルの2段階比較
diffs := dmp.DiffMain(text1, text2, true)

checklines = false（デフォルト）

文字レベルで直接比較
短いテキスト（〜1,000文字）に適している
計算量: O(n×m) ※n, mは文字数

checklines = true

まず改行で分割して行単位で比較
差分がある行のみ文字レベルで詳細比較
長いテキスト（1,000文字以上）で高速化が期待できる
計算量: O(l×k + n×m) ※l, kは行数、n×mは差分行のみ

使い分けの目安

// 短いテキスト（〜1,000文字）
diffs := dmp.DiffMain(shortText1, shortText2, false)

// 長いテキスト（1,000文字以上）
diffs := dmp.DiffMain(longText1, longText2, true)

まとめ

重要ポイント

基本的な使い方

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

差分の「視点」
- DiffMain(A, B)は「AをBに変える」という視点で差分を検出
- 返り値は[]Diff型で、Delete/Insert/Equalの3種類の操作を含む
パフォーマンス調整
- 短いテキスト: checklines = false
- 長いテキスト: checklines = true
活用シーン
- GitHubのPRのような差分表示機能を実装できる
- バージョン管理システムやドキュメント管理システムに活用可能

参考リンク