D言語で差分抽出

# はじめに
テキストファイルの差分抽出コマンドである`diff`を実装するためのアルゴリズムに興味を持ち、調べた際のメモになります。

# 差分抽出アルゴリズム
差分を効率的に抽出するアルゴリズムについては、下記リンクに詳しい説明があります。

[diffの動作原理を知る～どのようにして差分を導き出すのか](https://gihyo.jp/dev/column/01/prog/2011/diff_sd200906)
[差分検出アルゴリズム三種盛り](https://susisu.hatenablog.com/entry/2017/10/09/134032)

# ソースコード
## その１
[こちら](https://github.com/cubicdaiya/gonp/blob/master/gonp.go)で`go`のソースコード実装例が紹介されていました。
参考にしながら`D`言語版を実装しました。
オリジナルの`go`と比べて、`D`言語版は`struct Diff(T)`とテンプレートにしました。
テキストファイル以外の差分抽出にも応用できます。

```d:dist1.d
import std.algorithm;
import std.file;
import std.stdio;
import std.string;

// SesAdd    is manipulaton type of adding   element in SES
// SesDelete is manipulaton type of deleting element in SES
// SesCommon is manipulaton type of same     element in SES
enum SesType { SesAdd, SesDelete, SesCommon }

// Point is coordinate in edit graph
struct Point {
	int x;
	int y;
}

// PointWithRoute is coordinate in edit graph attached route
struct PointWithRoute {
	int x;
	int y;
	int r;
}

// SesElem is element of SES
struct SesElem(T) {
	T e;
	SesType t;
}

// Diff is context for calculating difference between a and b
struct Diff(T) {
	T[]					a;
	T[]					b;
	int					m, n;
	int					ed;		// Editdistance
	T[]					lcs;	// LCS (Longest Common Subsequence)
	SesElem!T[]			ses;	// SES (Shortest Edit Script)
	bool				reverse;
	int[]				path;
	bool				onlyEd;	// calculate only edit distance
	PointWithRoute[]	pointWithRoute;
	
	// New is initializer of Diff
	this(T[] A, T[] B) {
		a = A;
		b = B;
		m = cast(int)a.length;
		n = cast(int)b.length;
		reverse = false;
		if ( m > n ) {
			swap(a, b);
			swap(m, n);
			reverse = true;
		}
		onlyEd = false;
	}
	
	// PrintSes prints shortest edit script between a and b
	void printSes() {
		int n1 = 1;
		int n2 = 1;
		int bSame = true;
		foreach ( e ; ses ) {
			switch ( e.t ) {
			  case SesType.SesDelete:
				writefln("%04d      - %s", n1, e.e);
				n1++;
				bSame = false;
				break;
			  case SesType.SesAdd:
				writefln("     %04d + %s", n2, e.e);
				n2++;
				bSame = false;
				break;
			  default:	// SesType.SesCommon:
				n1++;
				n2++;
				if ( !bSame ){
					writeln("----------");
				}
				bSame = true;
				break;
			}
		}
	}
	
	// Compose composes diff between a and b
	void compose() {
		int[] fp;
		fp.length = m + n + 3;
		fp[] = -1;
		path.length = m + n + 3;
		path[] = -1;
		int offset = m + 1;
		int delta  = n - m;
		
		for ( int p = 0; ; p++ ) {
			for ( int k = -p; k <= delta - 1; k++ ) {
				fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset], offset);
			}
			for ( int k = delta + p; k >= delta + 1; k-- ) {
				fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset], offset);
			}
			fp[delta+offset] = snake(delta, fp[delta-1+offset]+1, fp[delta+1+offset], offset);
			if ( fp[delta+offset] >= n ) {
				ed = delta + 2 * p;
				break;
			}
		}
		
		if ( onlyEd ) {
			return;
		}
		
		int r = path[delta+offset];
		Point[] epc;
		while ( r != -1 ) {
			Point p = { x: pointWithRoute[r].x, y: pointWithRoute[r].y };
			epc ~= p;
			r = pointWithRoute[r].r;
		}
		recordSeq(epc);
	}
	
	int snake(int k, int p, int pp, int offset) {
		int r = 0;
		if ( p > pp ) {
			r = path[k-1+offset];
		} else {
			r = path[k+1+offset];
		}
		int y = max(p, pp);
		int x = y - k;
		while ( x < m && y < n && a[x] == b[y] ) {
			x++;
			y++;
		}
		if ( !onlyEd ) {
			path[k+offset] = cast(int)pointWithRoute.length;
			PointWithRoute pr = {x: x, y: y, r: r};
			pointWithRoute ~= pr;
		}
		return y;
	}
	
	void recordSeq(Point[] epc) {
		int x = 1;
		int y = 1;
		int px = 0;
		int py = 0;
		for ( int i = cast(int)epc.length - 1; i >= 0; i-- ) {
			while ( (px < epc[i].x) || (py < epc[i].y) ) {
				if ( (epc[i].y - epc[i].x) > (py - px) ) {
					auto t = SesType.SesAdd;
					if ( reverse ) {
						t = SesType.SesDelete;
					}
					SesElem!T s = { e: b[py], t: t};
					ses ~= s;
					y++;
					py++;
				} else if ( epc[i].y-epc[i].x < py-px ) {
					auto t = SesType.SesDelete;
					if ( reverse ) {
						t = SesType.SesAdd;
					}
					SesElem!T s = {e: a[px], t: t};
					ses ~= s;
					x++;
					px++;
				} else {
					lcs ~= a[px];
					SesElem!T s = {e: a[px], t: SesType.SesCommon};
					ses ~= s;
					x++;
					y++;
					px++;
					py++;
				}
			}
		}
	}
}

void main(string[] args)
{
	string[] a = args[1].readText.splitLines;
	string[] b = args[2].readText.splitLines;
	Diff!string d = Diff!string(a, b);
	d.compose();
	d.printSes();
}
```

テキストファイル以外の差分抽出の実装例は以下の通りです。

```d:dist2.d
import std.algorithm;
import std.stdio;

// SesAdd    is manipulaton type of adding   element in SES
// SesDelete is manipulaton type of deleting element in SES
// SesCommon is manipulaton type of same     element in SES
enum SesType { SesAdd, SesDelete, SesCommon }

// Point is coordinate in edit graph
struct Point {
	int x;
	int y;
}

// PointWithRoute is coordinate in edit graph attached route
struct PointWithRoute {
	int x;
	int y;
	int r;
}

// SesElem is element of SES
struct SesElem(T) {
	T e;
	SesType t;
}

// Diff is context for calculating difference between a and b
struct Diff(T) {
	T[]					a;
	T[]					b;
	int					m, n;
	int					ed;		// Editdistance
	T[]					lcs;	// LCS (Longest Common Subsequence)
	SesElem!T[]			ses;	// SES (Shortest Edit Script)
	bool				reverse;
	int[]				path;
	bool				onlyEd;	// calculate only edit distance
	PointWithRoute[]	pointWithRoute;
	
	// New is initializer of Diff
	this(T[] A, T[] B) {
		a = A;
		b = B;
		m = cast(int)a.length;
		n = cast(int)b.length;
		reverse = false;
		if ( m > n ) {
			swap(a, b);
			swap(m, n);
			reverse = true;
		}
		onlyEd = false;
	}
	
	// PrintSes prints shortest edit script between a and b
	void printSes() {
		int n1 = 1;
		int n2 = 1;
		int bSame = true;
		foreach ( e ; ses ) {
			switch ( e.t ) {
			  case SesType.SesDelete:
				writefln("%04d      - %s", n1, e.e);
				n1++;
				bSame = false;
				break;
			  case SesType.SesAdd:
				writefln("     %04d + %s", n2, e.e);
				n2++;
				bSame = false;
				break;
			  default:	// SesType.SesCommon:
				n1++;
				n2++;
				if ( !bSame ){
					writeln("----------");
				}
				bSame = true;
				break;
			}
		}
	}
	
	// Compose composes diff between a and b
	void compose() {
		int[] fp;
		fp.length = m + n + 3;
		fp[] = -1;
		path.length = m + n + 3;
		path[] = -1;
		int offset = m + 1;
		int delta  = n - m;
		
		for ( int p = 0; ; p++ ) {
			for ( int k = -p; k <= delta - 1; k++ ) {
				fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset], offset);
			}
			for ( int k = delta + p; k >= delta + 1; k-- ) {
				fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset], offset);
			}
			fp[delta+offset] = snake(delta, fp[delta-1+offset]+1, fp[delta+1+offset], offset);
			if ( fp[delta+offset] >= n ) {
				ed = delta + 2 * p;
				break;
			}
		}
		
		if ( onlyEd ) {
			return;
		}
		
		int r = path[delta+offset];
		Point[] epc;
		while ( r != -1 ) {
			Point p = { x: pointWithRoute[r].x, y: pointWithRoute[r].y };
			epc ~= p;
			r = pointWithRoute[r].r;
		}
		recordSeq(epc);
	}
	
	int snake(int k, int p, int pp, int offset) {
		int r = 0;
		if ( p > pp ) {
			r = path[k-1+offset];
		} else {
			r = path[k+1+offset];
		}
		int y = max(p, pp);
		int x = y - k;
		while ( x < m && y < n && a[x] == b[y] ) {
			x++;
			y++;
		}
		if ( !onlyEd ) {
			path[k+offset] = cast(int)pointWithRoute.length;
			PointWithRoute pr = {x: x, y: y, r: r};
			pointWithRoute ~= pr;
		}
		return y;
	}
	
	void recordSeq(Point[] epc) {
		int x = 1;
		int y = 1;
		int px = 0;
		int py = 0;
		for ( int i = cast(int)epc.length - 1; i >= 0; i-- ) {
			while ( (px < epc[i].x) || (py < epc[i].y) ) {
				if ( (epc[i].y - epc[i].x) > (py - px) ) {
					auto t = SesType.SesAdd;
					if ( reverse ) {
						t = SesType.SesDelete;
					}
					SesElem!T s = { e: b[py], t: t};
					ses ~= s;
					y++;
					py++;
				} else if ( epc[i].y-epc[i].x < py-px ) {
					auto t = SesType.SesDelete;
					if ( reverse ) {
						t = SesType.SesAdd;
					}
					SesElem!T s = {e: a[px], t: t};
					ses ~= s;
					x++;
					px++;
				} else {
					lcs ~= a[px];
					SesElem!T s = {e: a[px], t: SesType.SesCommon};
					ses ~= s;
					x++;
					y++;
					px++;
					py++;
				}
			}
		}
	}
}

void printDiff(T)(string message, T[] a, T[] b)
{
	writeln(message);
	writefln("  比較対象１：  %s", a);
	writefln("  比較対象２：  %s", b);
	writeln("差分抽出結果");
	Diff!T d = Diff!T(a, b);
	d.compose();
	d.printSes();
	writeln();
}

void main(string[] args)
{
	import std.string;
	
	printDiff("文字列の差分抽出", "abcdef", "dacfea");
	printDiff("配列の差分抽出", [1, 2, 3, 4], [1, 3, 4, 5, 6]);
	string t1 =
`あいうえお
かきくけこ
さしすせそ
`;
	string t2 =
`あいうえお
がぎぐげご
さしすせそ
`;
	printDiff("行の差分抽出(diff)", t1.splitLines, t2.splitLines);
	writeln();
}
```

## 実行例
```text:コマンドプロンプト
D:\Dev> chcp 65001
Active code page: 65001

D:\Dev> dmd -m64 dist1.d

D:\Dev> dmd -m64 dist2.d

D:\Dev> dist2
文字列の差分抽出
  比較対象１：  abcdef
  比較対象２：  dacfea
差分抽出結果
     0001 + d
----------
0002      - b
----------
     0004 + f
0004      - d
----------
     0006 + a
0006      - f

配列の差分抽出
  比較対象１：  [1, 2, 3, 4]
  比較対象２：  [1, 3, 4, 5, 6]
差分抽出結果
0002      - 2
----------
     0004 + 5
     0005 + 6

行の差分抽出(diff)
  比較対象１：  ["あいうえお", "かきくけこ", "さしすせそ"]
  比較対象２：  ["あいうえお", "がぎぐげご", "さしすせそ"]
差分抽出結果
     0002 + がぎぐげご
0002      - かきくけこ
----------



D:\Dev> dist1 dist1.d dist2.d
0002      - import std.file;
----------
0004      - import std.string;
----------
     0183 + void printDiff(T)(string message, T[] a, T[] b)
0185      - void main(string[] args)
----------
     0185 +     writeln(message);
     0186 +     writefln("  比較対象１：  %s", a);
     0187 +     writefln("  比較対象２：  %s", b);
     0188 +     writeln("差分抽出結果");
     0189 +     Diff!T d = Diff!T(a, b);
0187      -     string[] a = args[1].readText.splitLines;
0188      -     string[] b = args[2].readText.splitLines;
0189      -     Diff!string d = Diff!string(a, b);
----------
     0192 +     writeln();
----------
     0194 +
     0195 + void main(string[] args)
     0196 + {
     0197 +     import std.string;
     0198 +
     0199 +     printDiff("文字列の差分抽出", "abcdef", "dacfea");
     0200 +     printDiff("配列の差分抽出", [1, 2, 3, 4], [1, 3, 4, 5, 6]);
     0201 +     string t1 =
     0202 + `あいうえお
     0203 + かきくけこ
     0204 + さしすせそ
     0205 + `;
     0206 +     string t2 =
     0207 + `あいうえお
     0208 + がぎぐげご
     0209 + さしすせそ
     0210 + `;
     0211 +     printDiff("行の差分抽出(diff)", t1.splitLines, t2.splitLines);
     0212 +     writeln();
     0213 + }
```

## その２
`D`言語の標準関数([Phobos](https://dlang.org/phobos/))に[レーベンシュタイン距離](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)を求める関数[levenshteinDistanceAndPath](https://dlang.org/library/std/algorithm/comparison/levenshtein_distance_and_path.html)があります。
こちらを使えば、より簡潔にコードが実装できました。
※ちなみに、その１のソースコード作成後に、関数の存在を知りました。

```d:dist3.d
import std.algorithm;
import std.file;
import std.stdio;
import std.string;

void printSes(EditOp[] eoarr, string[] a, string[] b) {
	int n1 = 1;
	int n2 = 1;
	int bSame = true;
	foreach ( eo ; eoarr ) {
		switch ( eo ) {
			case EditOp.remove:
				writefln("%04d      - %s", n1, a[n1 - 1]);
				n1++;
				bSame = false;
				break;
			case EditOp.insert :
				writefln("     %04d + %s", n2, b[n2 - 1]);
				n2++;
				bSame = false;
				break;
			case EditOp.substitute :
				writefln("%04d      - %s", n1, a[n1 - 1]);
				writefln("     %04d + %s", n2, b[n2 - 1]);
				n1++;
				n2++;
				bSame = false;
				break;
			default:	// EditOp.none:
				n1++;
				n2++;
				if ( !bSame ){
					writeln("----------");
				}
				bSame = true;
				break;
		}
	}
}

void main(string[] args)
{
	string[] a = args[1].readText.splitLines;
	string[] b = args[2].readText.splitLines;
	auto lev = levenshteinDistanceAndPath(a, b);
	printSes(lev[1], a, b);
}
```

もちろん、`levenshteinDistanceAndPath`関数でも、テキストファイル以外の差分を抽出できます。

```d:dist4.d
import std.algorithm;
import std.stdio;
import std.string;

void printSes(T)(EditOp[] eoarr, T[] a, T[] b) {
	int n1 = 1;
	int n2 = 1;
	int bSame = true;
	foreach ( eo ; eoarr ) {
		switch ( eo ) {
			case EditOp.remove:
				writefln("%04d      - %s", n1, a[n1 - 1]);
				n1++;
				bSame = false;
				break;
			case EditOp.insert :
				writefln("     %04d + %s", n2, b[n2 - 1]);
				n2++;
				bSame = false;
				break;
			case EditOp.substitute :
				writefln("%04d      - %s", n1, a[n1 - 1]);
				writefln("     %04d + %s", n2, b[n2 - 1]);
				n1++;
				n2++;
				bSame = false;
				break;
			default:	// EditOp.none:
				n1++;
				n2++;
				if ( !bSame ){
					writeln("----------");
				}
				bSame = true;
				break;
		}
	}
}

void main(string[] args)
{
	auto a1 = "abcdef";
	auto a2 = "dacfea";
	auto lev1 = levenshteinDistanceAndPath(a1, a2);
	printSes(lev1[1], a1, a2);
	writeln();
	
	auto b1 = [1, 2, 3, 4];
	auto b2 = [1, 3, 4, 5, 6];
	auto lev2 = levenshteinDistanceAndPath(b1, b2);
	printSes(lev2[1], b1, b2);
	writeln();
	
	string t1 =
`あいうえお
かきくけこ
さしすせそ
`;
	string t2 =
`あいうえお
がぎぐげご
さしすせそ
`;
	auto c1 = t1.splitLines;
	auto c2 = t2.splitLines;
	auto lev3 = levenshteinDistanceAndPath(c1, c2);
	printSes(lev3[1], c1, c2);
}
```

## 実行例
```text:コマンドプロンプト
D:\Dev> chcp 65001
Active code page: 65001

D:\Dev> dmd -m64 dist3.d

D:\Dev> dmd -m64 dist4.d

D:\Dev> dist4
0001      - a
     0001 + d
0002      - b
     0002 + a
----------
0004      - d
     0004 + f
----------
0006      - f
     0006 + a

0002      - 2
----------
     0004 + 5
     0005 + 6

0002      - かきくけこ
     0002 + がぎぐげご
----------

D:\Dev> dist3 dist3.d dist4.d
0002      - import std.file;
----------
0006      - void printSes(EditOp[] eoarr, string[] a, string[] b) {
     0005 + void printSes(T)(EditOp[] eoarr, T[] a, T[] b) {
----------
     0042 +     auto a1 = "abcdef";
     0043 +     auto a2 = "dacfea";
     0044 +     auto lev1 = levenshteinDistanceAndPath(a1, a2);
     0045 +     printSes(lev1[1], a1, a2);
     0046 +     writeln();
     0047 +
     0048 +     auto b1 = [1, 2, 3, 4];
     0049 +     auto b2 = [1, 3, 4, 5, 6];
     0050 +     auto lev2 = levenshteinDistanceAndPath(b1, b2);
     0051 +     printSes(lev2[1], b1, b2);
     0052 +     writeln();
     0053 +
     0054 +     string t1 =
     0055 + `あいうえお
     0056 + かきくけこ
     0057 + さしすせそ
     0058 + `;
     0059 +     string t2 =
     0060 + `あいうえお
     0061 + がぎぐげご
     0062 + さしすせそ
     0063 + `;
0043      -     string[] a = args[1].readText.splitLines;
     0064 +     auto c1 = t1.splitLines;
0044      -     string[] b = args[2].readText.splitLines;
     0065 +     auto c2 = t2.splitLines;
0045      -     auto lev = levenshteinDistanceAndPath(a, b);
     0066 +     auto lev3 = levenshteinDistanceAndPath(c1, c2);
0046      -     printSes(lev[1], a, b);
     0067 +     printSes(lev3[1], c1, c2);
----------
```

# 参考情報
[diffの動作原理を知る～どのようにして差分を導き出すのか](https://gihyo.jp/dev/column/01/prog/2011/diff_sd200906)
[差分検出アルゴリズム三種盛り](https://susisu.hatenablog.com/entry/2017/10/09/134032)
[Wu らによる差分検出の O(NP) アルゴリズム実装シリーズ ③Goによる実装](https://qiita.com/convto/items/39efea78e23a944d0760)
[goによる実装 ソースコード](https://github.com/cubicdaiya/gonp)