ふつうの人は WinMerge を使いましょう。
0. はじめに
Windows 付属の FC コマンドの出来が酷いのだ。UNIX などで用いられる diff コマンドと比べると，大規模なテキストにおける差分抽出能力がとても低いように思える。
1. 仕様案（お品書き）
- 比較アルゴリズムは UNIX の
diffコマンド準拠とする。 - 比較結果の出力について，Windows 付属の
FCコマンドの出力形式に準拠する。 - 文字コードについて，ファイルの先頭に BOM（バイト順マーク）があれば従うが，無い場合はシステムデフォルト値（日本語版 Windows の場合は Shift-JIS）に従う。
- オプション
/Nを指定すると行番号を表示する。行番号は5桁表示とする。 - ファイルが一致する場合の返値は 0，不一致の場合は 1，エラーの場合は -1 を返す。
※Windows 付属のFCコマンドではエラーの場合も 1 を返す。 - 使用言語は C# とする。Windows 10 付属の C# コンパイラでビルドできること。
2. UNIX の diff コマンドのアルゴリズムについて
UNIX の diff コマンドのアルゴリズムについては古くから論文が出ており，詳しくは参考文献を参照して欲しい。 このうち最も基礎的と思われる動的計画法を用いたアルゴリズムを自分なりに咀嚼した内容を以下記す。
2.1 サンプルファイル
本記事で取り扱う変更前後のサンプルファイルを以下に示す。
2.2 照合マップ
まず，変更前の $i$ 行と変更後の $j$ 行を比較した結果である照合マップ $C(i,j)$ を作成する。二つの行が一致していれば $C(i,j) = 1$ とし ◯ で示す。一方，不一致の場合 $C(i,j) = 0$ として空白で示す。なお ■ で示す余白部分の意味については後述する。
ここで左上端のマス（始点）から右下端のマス（終点）まで，できるだけ多くの一致するマス ◯ を通過する経路（最短経路）を求めてやればよい。原則としてマスを右または下に一つずつしか移動できないものとし，二つの行が一致しているマスのみ斜め移動可能とする。
変更前後で内容が一致している部分は斜めに移動，削除された部分は下方向に移動，追加された部分は右方向に移動する。変更された部分は下方向への移動と右方向への移動の組み合わせである。
2.3 距離マップ
このような最短経路を求めるため，まず始点から各マスへの距離マップ $D(i,j)$ を求める。
- 各マスの距離 $D(i,j)$ は左および上のマスの距離を参照するため，参照エラーが生じないよう余白部分 ■ を設け，$D(i,0) = i$，$D(0,j) = j$ とする。
- マスが一致しない場合，すなわち $C(i,j) = 0$ のとき，左のマスの距離に１を加えたものと上のマスの距離に１を加えたもののうち小さいほうとする。
D(i,j) = \min \left\{ \,\, D(i - 1, j) + 1,\,\, D(i, j - 1) + 1 \,\, \right\} - マスが一致している場合，すなわち $C(i,j) = 1$ のとき，さらに左上のマスの距離との最小値とする。
D(i,j) = \min \left\{ \,\, D(i - 1, j) + 1,\,\, D(i, j - 1) + 1 ,\,\, D(i- 1,j - 1) \,\, \right\}
このようにして求めた距離マップ $D(i,j)$ を以下に示す。※一致するマスは ■ で示す。
2.4 最短経路
始点からの最短経路は，終点から逆算して求める。
(1) 斜め移動の条件
$i \ge 1$，$j \ge 1$，$C(i,j) = 1$，$D(i-1,j-1) \le D(i-1,j)$，$D(i-1,j-1) \le D(i,j-1)$ のとき
(2) 左に移動の条件
$j \ge 1$，$C(i,j) = 1$，$D(i, j - 1) \le D(i - 1, j)$，$D(i, j - 1) < D(i - 1, j - 1)$ のとき
$j \ge 1$，$C(i,j) = 0$，$D(i, j - 1) \le D(i - 1, j)$ のとき
(3) 上に移動する条件
$i \ge 1$，$C(i,j) = 1$，$D(i - 1, j) < D(i, j - 1)$，$D(i - 1, j) < D(i - 1, j - 1)$ のとき
$i \ge 1$，$C(i,j) = 0$，$D(i - 1, j) < D(i, j - 1)$ のとき
以上のルールに基づいて，終点から始点まで最短経路を辿ると下記のようになる。
ちなみに終点のマスの距離がゼロの場合，二つのファイルは完全一致していることになる。
3. 差分の出力
差分の出力サンプルを以下に示す。Windows 付属の FC コマンドに準じ，不一致部分を挟んで前後の一致部分を一行だけ出力するものとする。
これをマップで示すと以下のようになる。一致するマス ○ が連続する場合を除き，一致するマスから次の一致するマスまでの部分経路（下図の▢の範囲）を出力すればよい。
4. 実装コード
4.1 ファイルの読み込み
文字コードはシステムデフォルト値としてファイルをオープンするが，ファイルの先頭に BOM がある場合は BOM を優先する。入力ファイルの行数 $N$ とすると，整数 $i$ を用いて $1 \le i \le N$ の範囲でリストにアクセスできるよう，先頭にダミーとして空行を入れる。
ファイルの読み込み
static List<string> load_file( string filename ) {
if( !File.Exists( filename ) ) {
Console.Error.WriteLine( "ファイル {0} を開けません。このファイルは存在しません",
filename );
return null;
}
var line = new List<string>();
var reader = new StreamReader( filename, Encoding.Default, true );
line.Add( "" );
while( !reader.EndOfStream ) {
var s = reader.ReadLine();
line.Add( s );
}
return line;
}
4.2 照合マップの作成
二つの入力ファイルの行数をそれぞれ $M$, $N$ とおくと，全行を読み込んだリスト line1，line2 の長さは先頭にダミー行を追加したため $M + 1$，$N + 1$ となる。照合マップは二次元配列であり，サイズは $(M + 1)\times (N + 1)$ となる。なお C# は多次元配列を公式サポートしている言語であるが，C# の多次元配列は非常に遅いことで有名なため，代わりにジャグ配列を用いた。
照合マップの作成
static bool[][] make_cmap( List<string> line1, List<string> line2 ) {
var hash1 = make_hash( line1 );
var hash2 = make_hash( line2 );
var cmap = new bool[line1.Count][];
for( int i = 0; i < line1.Count; i++ )
cmap[i] = new bool[line2.Count];
for( int i = 1; i < line1.Count; i++ )
for( int j = 1; j < line2.Count; j++ )
if( hash1[i] != hash2[j] )
cmap[i][j] = false;
else if( 0 != string.Compare( line1[i], line2[j] ) )
cmap[i][j] = false;
else
cmap[i][j] = true;
return cmap;
}
照合マップの作成は比較的重い処理になるため，ハッシュ値を用いて文字列比較を高速化する。ハッシュ関数は単なる文字列のサム値とした。
ハッシュの作成
static int[] make_hash( List<string> line ) {
var hash = new int[line.Count];
for( int i = 0; i < line.Count; i++ ) {
var s = line[i];
int sum = 0;
for( int j = 0; j < s.Length; j++ )
sum += (int)s[j];
hash[i] = sum;
}
return hash;
}
4.3 距離マップの作成
距離マップも二次元配列であり，こちらもジャグ配列にする。サイズは $(M + 1)\times (N + 1)$ となる。
距離マップの作成
static int[][] make_dmap( bool[][] cmap ) {
var dmap = new int[cmap.Length][];
for( int i = 0; i < cmap.Length; i++ )
dmap[i] = new int[cmap[0].Length];
dmap[0][0] = 0;
for( int i = 1; i < dmap.Length; i++ )
dmap[i][0] = i;
for( int j = 1; j < dmap[0].Length; j++ )
dmap[0][j] = j;
for( int i = 1; i < dmap.Length; i++ ) {
for( int j = 1; j < dmap[0].Length; j++ ) {
int d = Math.Min( dmap[i - 1][j], dmap[i][j - 1] ) + 1;
if( cmap[i][j] )
d = Math.Min( d, dmap[i - 1][j - 1] );
dmap[i][j] = d;
}
}
return dmap;
}
4.4 最短経路の生成
パス型 PATH を以下のように定義する。
パス型の定義
enum PATH : int {
DELETE = -1,
MATCH = 0,
INSERT = 1
}
最短経路は終点から始点まで逆順にサーチして，最後にリストを反転する。
最短経路の生成
static List<PATH> make_path( bool[][] cmap, int[][] dmap ) {
var path = new List<PATH>();
int i = dmap.Length - 1;
int j = dmap[0].Length - 1;
while( true ) {
if( i == 0 && j == 0 ) {
break;
} else if( i == 0 ) {
path.Add( PATH.INSERT ); j--;
} else if( j == 0 ) {
path.Add( PATH.DELETE ); i--;
} else if( cmap[i][j] && dmap[i - 1][j - 1] <= dmap[i][j - 1]
&& dmap[i - 1][j - 1] <= dmap[i - 1][j] ) {
path.Add( PATH.MATCH ); i--; j--;
} else if( dmap[i][j - 1] <= dmap[i - 1][j] ) {
path.Add( PATH.INSERT ); j--;
} else {
path.Add( PATH.DELETE ); i--;
}
}
path.Reverse();
return path;
}
4.5 差分情報の出力
似たような処理を繰り返すことからローカル関数を用いるとすっきり記述することができる。ところが Windows に付属する C# コンパイラ（バージョン 4.0）ではローカル関数をサポートしていないので delegate で代用することにした。
ローカル関数代用の delegate 型の定義
delegate void LOCALFUNC();
差分情報の出力
static void show_diff( List<PATH> path, List<string> line1, List<string> line2 ) {
int start1 = 1, end1 = 0;
int start2 = 1, end2 = 0;
PATH prev = PATH.MATCH;
//----------------------------------------------------------------------
// 出力用ローカル関数
//----------------------------------------------------------------------
LOCALFUNC output = delegate() {
Console.WriteLine( "***** " + filename1 );
for( int i = start1; i <= end1; i++ ) {
if( line_number ) Console.Write( "{0,5:D}: ", i );
Console.WriteLine( line1[i] );
}
Console.WriteLine( "***** " + filename2 );
for( int i = start2; i <= end2; i++ ) {
if( line_number ) Console.Write( "{0,5:D}: ", i );
Console.WriteLine( line2[i] );
}
Console.WriteLine( "*****" );
Console.WriteLine( "" );
};
for( int i = 0; i < path.Count; i++ ) {
switch( path[i] ) {
case PATH.MATCH:
end1++;
end2++;
if( prev != PATH.MATCH ) output();
start1 = end1;
start2 = end2;
break;
case PATH.INSERT:
end2++;
break;
case PATH.DELETE:
end1++;
break;
}
prev = path[i];
}
if( prev != PATH.MATCH ) output();
}
4.6 実装コード
実装コードを以下に示す。Windows 付属の C# コンパイラ（バージョン4.0）でもコンパイルできるように設計した。もちろん Visual Studio 付属の C# コンパイラでも問題なくコンパイル可能である。
DIFF.CS の実装コードはコチラ
DIFF.CS
//------------------------------------------------------------------------------
// 2 つのファイルを比較し、相違点を表示します。
//------------------------------------------------------------------------------
using System;
using System.IO;
using System.Text;
using System.Reflection;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Runtime.InteropServices;
//------------------------------------------------------------------------------
// 差分クラス
//------------------------------------------------------------------------------
class DIFF {
//--------------------------------------------------------------------------
// 定数定義
//--------------------------------------------------------------------------
enum PATH : int {
DELETE = -1,
MATCH = 0,
INSERT = 1
}
//--------------------------------------------------------------------------
// グローバル変数
//--------------------------------------------------------------------------
static string filename1 = ""; // ファイル名(1)
static string filename2 = ""; // ファイル名(2)
static bool line_number = false; // 行番号を表示する
//--------------------------------------------------------------------------
// ヘルプメッセージ
//--------------------------------------------------------------------------
static int usage() {
Console.Error.WriteLine( "2 つのファイルを比較し、相違点を表示します。" );
Console.Error.WriteLine( "" );
Console.Error.WriteLine( "DIFF(.EXE) (オプション) [ファイル名1] [ファイル名2]" );
Console.Error.WriteLine( "" );
Console.Error.WriteLine( "/N 行番号を表示します。" );
return -1;
}
//--------------------------------------------------------------------------
// オプション解析
//--------------------------------------------------------------------------
static int get_option( string[] args ) {
foreach( string s in args ) {
if( s[0] == '-' || s[0] == '/' ) {
switch( s[1] ) {
case 'N': case 'n':
line_number = true;
break;
default:
Console.Error.WriteLine( "不正なオプションです：{0}", s );
return -1;
}
} else if( filename1 == "" ) {
filename1 = s;
} else if( filename2 == "" ) {
filename2 = s;
} else {
Console.Error.WriteLine( "入力ファイル名は既に指定されています!!" );
return -1;
}
}
if( filename1 == "" || filename2 == "" ) return usage();
return 0;
}
//--------------------------------------------------------------------------
// ファイルの読み込み
//--------------------------------------------------------------------------
static List<string> load_file( string filename ) {
if( !File.Exists( filename ) ) {
Console.Error.WriteLine( "ファイル {0} を開けません。このファイルは存在しません",
filename );
return null;
}
var reader = new StreamReader( filename, Encoding.Default, true );
var line = new List<string>();
line.Add( "" );
while( !reader.EndOfStream ) {
var s = reader.ReadLine();
line.Add( s );
}
return line;
}
//--------------------------------------------------------------------------
// ハッシュの作成
//--------------------------------------------------------------------------
static int[] make_hash( List<string> line ) {
var hash = new int[line.Count];
for( int i = 0; i < line.Count; i++ ) {
var s = line[i];
int sum = 0;
for( int j = 0; j < s.Length; j++ )
sum += (int)s[j];
hash[i] = sum;
}
return hash;
}
//--------------------------------------------------------------------------
// 照合マップの作成
//--------------------------------------------------------------------------
static bool[][] make_cmap( List<string> line1, List<string> line2 ) {
var hash1 = make_hash( line1 );
var hash2 = make_hash( line2 );
var cmap = new bool[line1.Count][];
for( int i = 0; i < line1.Count; i++ )
cmap[i] = new bool[line2.Count];
for( int i = 0; i < line1.Count; i++ )
for( int j = 0; j < line2.Count; j++ )
if( hash1[i] != hash2[j] )
cmap[i][j] = false;
else if( 0 != string.Compare( line1[i], line2[j] ) )
cmap[i][j] = false;
else
cmap[i][j] = true;
return cmap;
}
//--------------------------------------------------------------------------
// 距離マップの作成
//--------------------------------------------------------------------------
static int[][] make_dmap( bool[][] cmap ) {
var dmap = new int[cmap.Length][];
for( int i = 0; i < cmap.Length; i++ )
dmap[i] = new int[cmap[0].Length];
dmap[0][0] = 0;
for( int i = 1; i < dmap.Length; i++ )
dmap[i][0] = i;
for( int j = 1; j < dmap[0].Length; j++ )
dmap[0][j] = j;
for( int i = 1; i < dmap.Length; i++ ) {
for( int j = 1; j < dmap[0].Length; j++ ) {
int d = Math.Min( dmap[i - 1][j], dmap[i][j - 1] ) + 1;
if( cmap[i][j] )
d = Math.Min( d, dmap[i - 1][j - 1] );
dmap[i][j] = d;
}
}
return dmap;
}
//--------------------------------------------------------------------------
// 最短経路の生成
//--------------------------------------------------------------------------
static List<PATH> make_path( bool[][] cmap, int[][] dmap ) {
var path = new List<PATH>();
int i = dmap.Length - 1;
int j = dmap[0].Length - 1;
while( true ) {
if( i == 0 && j == 0 ) {
break;
} else if( i == 0 ) {
path.Add( PATH.INSERT ); j--;
} else if( j == 0 ) {
path.Add( PATH.DELETE ); i--;
} else if( cmap[i][j] && dmap[i - 1][j - 1] <= dmap[i][j - 1]
&& dmap[i - 1][j - 1] <= dmap[i - 1][j] ) {
path.Add( PATH.MATCH ); i--; j--;
} else if( dmap[i][j - 1] <= dmap[i - 1][j] ) {
path.Add( PATH.INSERT ); j--;
} else {
path.Add( PATH.DELETE ); i--;
}
}
path.Reverse();
return path;
}
//--------------------------------------------------------------------------
// ローカル関数型の定義
//--------------------------------------------------------------------------
delegate void LOCALFUNC();
//--------------------------------------------------------------------------
// 差分情報の出力
//--------------------------------------------------------------------------
static void show_diff( List<PATH> path, List<string> line1, List<string> line2 ) {
int start1 = 1, end1 = 0;
int start2 = 1, end2 = 0;
PATH prev = PATH.MATCH;;
//----------------------------------------------------------------------
// 出力用ローカル関数
//----------------------------------------------------------------------
LOCALFUNC output = delegate() {
Console.WriteLine( "***** " + filename1 );
for( int i = start1; i <= end1; i++ ) {
if( line_number ) Console.Write( "{0,5:D}: ", i );
Console.WriteLine( line1[i] );
}
Console.WriteLine( "***** " + filename2 );
for( int i = start2; i <= end2; i++ ) {
if( line_number ) Console.Write( "{0,5:D}: ", i );
Console.WriteLine( line2[i] );
}
Console.WriteLine( "*****" );
Console.WriteLine( "" );
};
for( int i = 0; i < path.Count; i++ ) {
switch( path[i] ) {
case PATH.MATCH:
end1++;
end2++;
if( prev != PATH.MATCH ) output();
start1 = end1;
start2 = end2;
break;
case PATH.INSERT:
end2++;
break;
case PATH.DELETE:
end1++;
break;
}
prev = path[i];
}
if( prev != PATH.MATCH ) output();
}
//--------------------------------------------------------------------------
// メイン関数
//--------------------------------------------------------------------------
static int Main( string[] args ) {
//----------------------------------------------------------------------
// ヘルプメッセージ
//----------------------------------------------------------------------
if( args.Length == 0 ) return usage();
//----------------------------------------------------------------------
// オプション解析
//----------------------------------------------------------------------
if( get_option( args ) != 0 ) return -1;
//----------------------------------------------------------------------
// ファイルの比較
//----------------------------------------------------------------------
Console.WriteLine( "ファイル {0} と {1} を比較しています", filename1, filename2 );
//----------------------------------------------------------------------
// ファイルの読み込み
//----------------------------------------------------------------------
var line1 = load_file( filename1 ); if( line1 == null ) return -1;
var line2 = load_file( filename2 ); if( line2 == null ) return -1;
//----------------------------------------------------------------------
// 照合マップの作成
//----------------------------------------------------------------------
var cmap = make_cmap( line1, line2 );
//----------------------------------------------------------------------
// 距離マップの作成
//----------------------------------------------------------------------
var dmap = make_dmap( cmap );
//----------------------------------------------------------------------
// 距離マップの右下端が 0 なら 2 つのファイルは完全一致
//----------------------------------------------------------------------
if( dmap[dmap.Length - 1][dmap[0].Length - 1] == 0 ) {
Console.WriteLine( "DIFF: 相違点は検出されませんでした" );
Console.WriteLine( "" );
return 0;
}
//----------------------------------------------------------------------
// 最短経路の生成
//----------------------------------------------------------------------
var path = make_path( cmap, dmap );
//----------------------------------------------------------------------
// 差分情報の出力
//----------------------------------------------------------------------
show_diff( path, line1, line2 );
path.Clear();
line1.Clear();
line2.Clear();
return 1;
}
}
Windows 付属の C# コンパイラにパスを通すバッチファイル SETCSC.CMD のコードも以下に示す。
SETCSC.CMD のコードはコチラ
SETCSC.CMD
@echo off
if defined DOTNETPATH (
echo PATH に %DOTNETPATH% は既に存在します。
exit /b
)
for /F "usebackq tokens=1,2,*" %%I in (
`reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v4\Full" /v InstallPath`
) do (
if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
for /F "usebackq tokens=1,2,*" %%I in (
`reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v4\Full" /v Version`
) do (
if "%%I"=="Version" set "DOTNETVERSION=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
echo PATH に %DOTNETPATH% を追加しました。
5. 実行例
引数なしで実行するとヘルプメッセージを表示する。エラーコードは -1 となる。
ファイルが一致する場合のエラーコードは 0 となる。
ファイルが一致しない場合のエラーコードは 1 となる。
行番号を表示させた場合を以下に示す。
6. 今後の課題
- (1) 比較するファイルサイズ（行数）の制限
- 比較する二つのファイルの行数の積 $M \times N$ に比例したマップを作成する必要があることから，事実上，数千行程度が上限である。C# プログラムなので 64bit OS であれば広大なメモリを取り扱うことはできるが，さすがに数万行規模に及ぶと計算時間も目立って遅くなる。ただ，もともとこの課題は有名なもので，この課題を解決するために後発のアルゴリズムが開発されたといっても良い。つまり，解決策は無数にある。
- (2) タブの置換
- Windows 付属の
FCコマンドはデフォルトでタブをスペースに置換してくれる。オプションで置換しないことも選択できる。ただしタブ幅は半角 8 文字分固定である。筆者は 4 文字派なので，置換するタブ幅を変更できるようにしたい。ただし，タブの置換は Unicode の持つ半角／全角問題に向き合う必要があり，真面目にやろうとすると沼にハマりそうで危険な香りがする。 - (3) 英字の大文字・小文字の区別
- Windows 付属の
FCコマンドはデフォルトで英字の大文字・小文字を区別するが，オプションで区別しないことも選択できる。 - (4) 連続するスペースの圧縮
- Windows 付属の
FCコマンドはオプションで連続した空白（スペースおよびタブ）を単一のスペースとみなして比較するモードがある。
