[Goでテキスト差分検出を行う] sergi/go-diff/diffmatchpatchの使い方

この記事でわかること

• 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()関数は内部で以下の処理を実行します：

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

---

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)

---

まとめ

重要ポイント

1. 基本的な使い方

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

2. 差分の「視点」

   • DiffMain(A, B)は「AをBに変える」という視点で差分を検出
   • 返り値は[]Diff型で、Delete/Insert/Equalの3種類の操作を含む

3. パフォーマンス調整

   • 短いテキスト: checklines = false
   • 長いテキスト: checklines = true

4. 活用シーン

   • GitHubのPRのような差分表示機能を実装できる
   • バージョン管理システムやドキュメント管理システムに活用可能

参考リンク

• sergi/go-diff - GitHub
• sergi/go-diff - pkg.go.dev
• Google Diff-Match-Patch