ふつうの人は WinMerge を使いましょう。
はじめに
プログラムのソースコードの比較であれば行単位での差分で十分な場合が多いでしょうが,差分を取る対象が一般的な日本語テキストとなると文字単位で比較してみたくなります。
かつて筆者は自作の差分抽出ツールを作ったことがありますが,それは行単位での比較でした。なので今回は文字単位の差分抽出ツールを作りたいと思います。
仕様案(お品書き)
たとえば「変更前の文字列」と「変更後の文字列」の二つの文字列に対して文字単位で差分を取り,一致する部分を目立たないように灰色 #767676 とし,削除された部分を強調すべく赤色 #E74856,追加された部分も緑色 #16C60C でカラー表示するものとします。
開発言語は WSH + JavaScript とします。カラー表示する色をトライ&エラーして決めるにはインタプリタ実行のほうが便利であり,加えて対象のテキストファイルはさほど大きくない(数キロバイト)なので十分な処理速度を得られるだろうという判断です。
差分エンジンは参考文献1のものを流用します。二つのファイルの長さを $m$,$n$ とおくと,$O(m \times n)$ の計算量を必要とする原始的なアルゴリズムですが,手軽に作るのには向いています。元記事のコードは C# ですが,JavaScript への移植はそう難しくはないでしょう。
カラー出力は VT100 準拠のエスケープシーケンスを使用します。WSH スクリプトはコマンドプロンプト上からは通常カラー出力できないので参考文献2を参照してレジストリを書き換えるか,あるいは Windows Terminal を使って下さい。
スクリプト名は icdiff.js とします。文字単位でカラー差分できる UNIX の同名ツールにちなみました。機能的にはかなり違いますが,ご容赦下さい。
実装コード
実装コードを以下に示します。※200行弱あります。
//------------------------------------------------------------------------------
// 定数定義
//------------------------------------------------------------------------------
var PATH = { MATCH:0, INSERT:1, DELETE:-1 };
var ESC = {
MATCH:"\x1b[90m", INSERT:"\x1b[92m", DELETE:"\x1b[91m", RESET:"\x1b[0m"
};
//------------------------------------------------------------------------------
// メイン関数の呼び出し
//------------------------------------------------------------------------------
var args = WScript.Arguments.Unnamed;
var ret = main(args);
try {
WScript.Quit(ret);
} catch(e) {
/* 何もしない */
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
function main(args) {
//--------------------------------------------------------------------------
// ヘルプメッセージの表示
//--------------------------------------------------------------------------
if(args.Count < 2) {
WScript.Echo("二つのテキストファイルを文字単位で比較し、相違点をカラー表示します。");
WScript.Echo("");
WScript.Echo("ICDIFF(.JS) [ファイル名(1)] [ファイル名(2)]");
return -1;
}
//--------------------------------------------------------------------------
// コマンドライン解析
//--------------------------------------------------------------------------
var filename1 = args(0);
var filename2 = args(1);
//--------------------------------------------------------------------------
// テキストファイルの読み込み ※先頭に半角スペースを追加
//--------------------------------------------------------------------------
var text1 = load_text(filename1); if(text1 == null) return -1;
var text2 = load_text(filename2); if(text2 == null) return -1;
//--------------------------------------------------------------------------
// 照合マップの作成
//--------------------------------------------------------------------------
var cmap = make_cmap(text1, text2);
//--------------------------------------------------------------------------
// 距離マップの作成
//--------------------------------------------------------------------------
var dmap = make_dmap(cmap);
//--------------------------------------------------------------------------
// 最短経路の生成
//--------------------------------------------------------------------------
var path = make_path(cmap, dmap);
//--------------------------------------------------------------------------
// 差分情報の出力
//--------------------------------------------------------------------------
show_diff(path, text1, text2);
return 0;
}
//------------------------------------------------------------------------------
// テキストファイルの読み込み ※先頭に半角スペースを追加
//------------------------------------------------------------------------------
function load_text(filename) {
var fso = WScript.CreateObject("Scripting.FileSystemObject");
if(!fso.FileExists(filename)) {
WScript.Echo("ファイル " + filename + " が存在しません!!");
return null;
}
var ts = fso.OpenTextFile(filename);
var text = ts.ReadAll();
ts.Close();
return " " + text;
}
//------------------------------------------------------------------------------
// 照合マップの作成
//------------------------------------------------------------------------------
function make_cmap(text1, text2) {
var cmap = [];
for(var i = 0; i < text1.length; i++) {
cmap[i] = [];
for(var j = 0; j < text2.length; j++) {
var match = (text1.charAt(i) == text2.charAt(j));
cmap[i].push(match);
}
}
return cmap;
}
//------------------------------------------------------------------------------
// 距離マップの作成
//------------------------------------------------------------------------------
function make_dmap(cmap) {
var dmap = [];
for(var i = 0; i < cmap.length; i++) {
dmap[i] = [];
for(var j = 0; j < cmap[0].length; j++)
dmap[i].push(0);
}
for(var i = 0; i < dmap.length; i++)
dmap[i][0] = i;
for(var j = 0; j < dmap[0].length; j++)
dmap[0][j] = j;
for(var i = 1; i < dmap.length; i++) {
for(var j = 1; j < dmap[0].length; j++) {
var 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;
}
//------------------------------------------------------------------------------
// 最短経路の生成
//------------------------------------------------------------------------------
function make_path(cmap, dmap) {
var path = [];
var i = dmap.length - 1;
var j = dmap[0].length - 1;
while(true) {
if(i == 0 && j == 0) {
break;
} else if(i == 0) {
path.push(PATH.INSERT); j--;
} else if(j == 0) {
path.push(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.push(PATH.MATCH); i--; j--;
} else if(dmap[i][j - 1] <= dmap[i - 1][j]) {
path.push(PATH.INSERT); j--;
} else {
path.push(PATH.DELETE); i--;
}
}
return path.reverse();
}
//------------------------------------------------------------------------------
// 差分情報の出力
//------------------------------------------------------------------------------
function show_diff(path, text1, text2) {
//--------------------------------------------------------------------------
// ランレングス圧縮
//--------------------------------------------------------------------------
var runlen = [];
var prev = path[0], len = 1;
for(var k = 1; k < path.length; k++) {
if(prev == path[k]) {
len++;
} else {
runlen.push({ path:prev, length:len });
prev = path[k];
len = 1;
}
}
runlen.push({ path:prev, length:len });
//--------------------------------------------------------------------------
// コンソール出力
//--------------------------------------------------------------------------
var i = 1, j = 1;
for(var k = 0; k < runlen.length; k++) {
var len = runlen[k].length;
switch(runlen[k].path) {
case PATH.MATCH:
WScript.StdOut.Write(ESC.MATCH);
WScript.StdOut.Write(text1.substr(i, len)); i += len; j += len;
break;
case PATH.INSERT:
WScript.StdOut.Write(ESC.INSERT);
WScript.StdOut.Write(text2.substr(j, len)); j += len;
break;
case PATH.DELETE:
WScript.StdOut.Write(ESC.DELETE);
WScript.StdOut.Write(text1.substr(i, len)); i += len;
break;
}
}
WScript.StdOut.Write(ESC.RESET);
}
技術解説
下記の関数については C# 版からのベタ移植に過ぎないので説明を省きます。
- 照合マップの作成
make_cmap() - 距離マップの作成
make_dmap() - 最短経路の生成
make_path()
今回,一番苦労したのが差分情報を表示する関数 show_diff() です。行単位で差分表示するツールでは一行ごとに WriteLine() メソッドを呼び出してコンソール出力していました。しかし,今回,一文字ごとに Write() メソッドを呼び出すのはさすがに効率が悪過ぎます。また表示するカラーを変更する度にエスケープシーケンスを出力する必要がありますが,これも一文字ごとにエスケープシーケンスを出力するのは無駄でしょう。
このため最短経路を示すパス path[] をランレングス圧縮することにしました。
var runlen = [];
var prev = path[0], len = 1;
for(var k = 1; k < path.length; k++) {
if(prev == path[k]) {
len++;
} else {
runlen.push({ path:prev, length:len });
prev = path[k];
len = 1;
}
}
runlen.push({ path:prev, length:len });
こうすればエスケープシーケンスの出力は必要最小限に抑えることができ,かつ文字の出力もまとめて行うことができます。おそらく本スクリプトを拡張して HTML 形式で出力させるのも容易でしょう。
var i = 1, j = 1;
for(var k = 0; k < runlen.length; k++) {
var len = runlen[k].length;
switch(runlen[k].path) {
case PATH.MATCH:
WScript.StdOut.Write(ESC.MATCH);
WScript.StdOut.Write(text1.substr(i, len)); i += len; j += len;
break;
case PATH.INSERT:
WScript.StdOut.Write(ESC.INSERT);
WScript.StdOut.Write(text2.substr(j, len)); j += len;
break;
case PATH.DELETE:
WScript.StdOut.Write(ESC.DELETE);
WScript.StdOut.Write(text1.substr(i, len)); i += len;
break;
}
}
WScript.StdOut.Write(ESC.RESET);
ちなみに定数定義はスクリプト冒頭で下記のように行っています。
var PATH = { MATCH:0, INSERT:1, DELETE:-1 };
var ESC = {
MATCH:"\x1b[90m", INSERT:"\x1b[92m", DELETE:"\x1b[91m", RESET:"\x1b[0m"
};
実行サンプル
ネットワーク対戦ゲーム「将棋ウォーズ」を提供している HEROZ 株式会社の著作物利用ガイドライン3を例題とします。このガイドラインは制定後に何度か改訂されており,その差分を見てみることにしましょう。
なお,ガイドラインの WEB ページよりテキストを抽出する際,スペース調整や全角英字を半角文字に置換するなどの変換を行いましたが,内容の同一性確保に努めました。
2019年7月5日制定版 Rev.1
この当時は Twitter だったんですね(遠い目)
ネットワーク対戦ゲームに係るHEROZ著作物の利用に関するガイドライン
1. 本ガイドラインが適用されるお客様
1. ●個人または非営利団体
2. ●HEROZ株式会社(以下「当社」)が著作権の利用を許諾した法人
2. 当社は、お客様において以下の利用態様と利用条件を遵守していただく場合に限り、当社が著作権を有する「将棋ウォーズ」等のネットワーク対戦ゲーム(以下「ネットワーク対戦ゲーム」)の利用について、著作権侵害を主張いたしません。
(1) 利用態様
1. ●当社が著作権を有するネットワーク対戦ゲームからキャプチャーした映像およびスクリーンショット(以下「当社著作物」)を利用した動画や静止画を、営利を目的としない場合に限り、適法かつ適切な動画や静止画の共有サイトに投稿(ストリーミング配信や実況する場合を含みます。以下同様とします。)すること
2. ●YouTube、ニコニコ動画、Twitter、TwitCastingおよびMirrativの各サービスで指定されたシステムにおいて、当社著作物を利用した動画や静止画を投稿し、収益を得ること
3. ●団体または個人が主催する大会(入場料を徴収する場合を含みます。以下同様とします。)で、ネットワーク対戦ゲームを使用すること、およびその大会におけるプレイ動画を動画の共有サイトに投稿すること
4. ●当社著作物を利用した静止画を、団体または個人が主催する大会において掲載すること
5. ●部活動、道場およびこれに類する場、指導対局、レッスンにおいて使用すること
(2) 利用条件
1. ●当社以外の第三者が有する知的財産権が利用されている場合には、本ガイドラインとは別に、その第三者から知的財産権の利用許諾を得る必要があります。
2. ●他人の投稿を転載したもの、当社が制作した動画を転載したもの、ネットワーク対戦ゲームそのもの、ネットワーク対戦ゲームのサウンドトラックや特定のシーン、イラスト集等をコピーしただけの投稿は認められません。
3. ●お客様の創作物やコメントとともに、当社著作物を投稿または掲載することは問題ありませんが、当社著作物そのものを改変することはできません。
4. ●ネットワーク対戦ゲームの対戦や観戦以外の目的による利用や、他者を誹謗中傷するような態様での利用は禁止いたします。
5. ●事実に反して、当社や当社関係者から、協賛や提携を受けているようなことを示唆し、または第三者が誤診するような利用は禁止いたします。
6. ●当社著作物を利用して創作した動画や静止画を、当社の許可なく販売することは禁止いたします。
7. ●当社著作物を利用する際または利用した結果、第三者の権利や利益を侵害した場合、いかなる理由であっても当社は一切責任を負いません。
8. ●万が一、本ガイドラインに違反する行為、違法または不適切な行為、公序良俗に反する行為がなされた場合には、当社は、サイト運営者に対する投稿の削除請求その他必要な法的措置をとる権利を有しています。当社以外の知的財産権の権利者から依頼を受けて、その権利者に代わって削除請求をする場合もあります。
(3) その他
1. ●本ガイドラインは随時更新されますので、利用前に必ず最新のガイドラインをご確認ください。
2. ●本ガイドラインへのお問合せにはお答えいたしません。ただし、当社著作物の利用許諾を必要とする法人のご担当者様は、当社にご一報ください。
2019年7月5日制定
2025年11月1日改訂版 Rev.2
Twitter が X(旧Twitter) に変わっています。
ネットワーク対戦ゲームに係るHEROZ著作物の利用に関するガイドライン
1. 本ガイドラインが適用されるお客様
1. ●個人または非営利団体
2. ●HEROZ株式会社(以下「当社」)が著作権の利用を許諾した法人
2. 当社は、当社が著作権を有する「将棋ウォーズ」等のネットワーク対戦ゲーム(以下「ネットワーク対戦ゲーム」)の利用について、お客様に以下に定める利用態様、該当せず、また利用条件を遵守していただく場合に限り、著作権侵害を主張いたしません。
ただし、当社において配信されるネットワーク対戦ゲームの有料動画およびAIプログラムに関する当社著作物(2(1)禁止される利用様態に定義)の利用については、本ガイドラインの適用はなく、当社の許諾を必要とします。
(1) 禁止される利用態様
1. ●当社が著作権を有するネットワーク対戦ゲームをキャプチャーした映像およびネットワーク対戦ゲームのスクリーンショット(以下「当社著作物」)、またはこれを利用した動画や静止画を適法かつ適切な動画や静止画の共有サイトに営利を目的として投稿(ストリーミング配信や実況する場合を含み、営利目的の該当性は当社が判断するものとします。以下同様とします。)すること
2. ●YouTube、ニコニコ動画、X(旧Twitter)、Instagram、TikTokおよびMirrativ等のサービスまたはシステムにおいて、当社著作物またはこれを利用した動画や静止画を投稿し、収益を得ること
3. ●団体または個人が主催する大会(入場料を徴収する場合を含みます。以下同様とします。)で、ネットワーク対戦ゲームを使用すること、およびその大会におけるプレイ動画を動画の共有サイトに投稿すること
4. ●ネットワーク対戦ゲームから出力された結果(AIプログラムが生成した棋譜等であるがこれに限らない)に基づいて他社媒体へ応募をおこなうこと
5. ●当社著作物を利用した静止画を、団体または個人が主催する大会において掲載すること
6. ●部活動、道場およびこれに類する場、指導対局、レッスンにおいて使用すること
(2) 利用条件
1. ●当社以外の第三者が有する知的財産権が利用されている場合には、本ガイドラインとは別に、その第三者から知的財産権の利用許諾を得る必要があります。
2. ●(1)に規定される禁止される利用様態に抵触しない適正な利用または、当社が利用を許諾する場合において、その著作物については引用のみを行えるものとし(当社およびネットワーク対戦ゲーム名を引用元として明確に表示することを要する)、改変、翻案、編集、複製、再配布、二次的著作物の作成その他当社の権利を侵害する一切の行為をしてはなりません。
3. ●他人の投稿を転載したもの、当社が制作した動画を転載したもの、ネットワーク対戦ゲームそのもの、ネットワーク対戦ゲームのサウンドトラックや特定のシーン、イラスト集等をコピーしただけの投稿は認められません。
4. ●お客様の創作物やコメントとともに、当社著作物を投稿または掲載することは問題ありませんが、当社著作物そのものを改変することはできません。
5. ●ネットワーク対戦ゲームの対戦や観戦以外の目的による利用や、他者を誹謗中傷するような態様での利用は禁止いたします。
6. ●事実に反して、当社や当社関係者から、協賛や提携を受けているようなことを示唆し、または第三者が誤診するような利用は禁止いたします。
7. ●当社著作物を利用して創作した動画や静止画を、当社の許可なく販売することは禁止いたします。
8. ●当社著作物を利用する際または利用した結果、第三者の権利や利益を侵害した場合、いかなる理由であっても当社は一切責任を負いません。
9. ●万が一、本ガイドラインに違反する行為、違法または不適切な行為、公序良俗に反する行為がなされた場合には、当社は、サイト運営者に対する投稿の削除請求その他必要な法的措置をとる権利を有しています。当社以外の知的財産権の権利者から依頼を受けて、その権利者に代わって削除請求をする場合があります。
(3) その他
1. ●本ガイドラインは随時更新されますので、利用前に必ず最新のガイドラインをご確認ください。
2. ●本ガイドラインへのお問合せにはお答えいたしません。ただし、当社著作物の利用許諾を必要とするお客様は、当社にご一報ください。
2019年7月5日制定
2025年11月1日改訂
2026年2月24日改訂版 Rev.3
最近改訂されたばかりの最新版です。
ネットワーク対戦ゲームに係るHEROZ著作物の利用に関するガイドライン
1. 本ガイドラインが適用されるお客様
1. ●個人または非営利団体
2. ●HEROZ株式会社(以下「当社」)が著作権の利用を許諾した法人
2. 当社は、当社が著作権を有する「将棋ウォーズ」等のネットワーク対戦ゲーム(以下「ネットワーク対戦ゲーム」)の利用について、お客様に以下に定める利用態様かつ、利用条件を遵守していただく場合に限り、著作権侵害を主張いたしません。
ただし、当社において配信されるネットワーク対戦ゲームの有料動画およびAIプログラムに関する当社著作物の利用については、本ガイドラインの適用はなく、当社の許諾を必要とします。
(1) 利用可能な利用態様
1. ●当社が著作権を有するネットワーク対戦ゲームをキャプチャーした映像およびネットワーク対戦ゲームのスクリーンショット(以下「当社著作物」)、またはこれを利用した動画や静止画を適法かつ適切な動画や静止画の共有サイトに営利を目的として投稿(ストリーミング配信や実況する場合を含み、営利目的の該当性は当社が判断するものとします。以下同様とします。)すること
2. ●YouTube、ニコニコ動画、X(旧Twitter)、Instagram、TikTokおよびMirrativ等のサービスまたはシステムにおいて、当社著作物またはこれを利用した動画や静止画を投稿し、収益を得ること
3. ●団体または個人が主催する大会(入場料を徴収する場合を含みます。以下同様とします。)で、ネットワーク対戦ゲームを使用すること、およびその大会におけるプレイ動画を動画の共有サイトに投稿すること
4. ●当社著作物を利用した静止画を、団体または個人が主催する大会において掲載すること
5. ●部活動、道場およびこれに類する場、指導対局、レッスンにおいて使用すること
(2) 利用条件
1. ●当社以外の第三者が有する知的財産権が利用されている場合には、本ガイドラインとは別に、その第三者から知的財産権の利用許諾を得る必要があります。
2. ●(1) に規定される利用可能な様態により適正な利用または、当社が利用を許諾する場合において、その著作物の利用については引用のみを行えるものとし(当社およびネットワーク対戦ゲーム名を引用元として明確に表示することを要する)、改変、翻案、編集、複製、再配布、二次的著作物の作成その他当社の権利を侵害する一切の行為をしてはなりません。
3. ●他人の投稿を転載したもの、当社が制作した動画を転載したもの、ネットワーク対戦ゲームそのもの、ネットワーク対戦ゲームのサウンドトラックや特定のシーン、イラスト集等をコピーしただけの投稿は認められません。
4. ●お客様の創作物やコメントとともに、当社著作物を投稿または掲載することは問題ありませんが、当社著作物そのものを改変することはできません。
5. ●ネットワーク対戦ゲームの対戦や観戦以外の目的による利用や、他者を誹謗中傷するような態様での利用は禁止いたします。
6. ●事実に反して、当社や当社関係者から、協賛や提携を受けているようなことを示唆し、または第三者が誤診するような利用は禁止いたします。
7. ●ネットワーク対戦ゲームから出力された結果(AIプログラムが生成した棋譜等であるがこれに限らない)に基づいて他社媒体へ応募をおこなうことを禁止いたします。
8. ●当社著作物を利用して創作した動画や静止画を、当社の許可なく販売することは禁止いたします。
9. ●当社著作物を利用する際または利用した結果、第三者の権利や利益を侵害した場合、いかなる理由であっても当社は一切責任を負いません。
10. ●万が一、本ガイドラインに違反する行為、違法または不適切な行為、公序良俗に反する行為がなされた場合には、当社は、サイト運営者に対する投稿の削除請求その他必要な法的措置をとる権利を有しています。当社以外の知的財産権の権利者から依頼を受けて、その権利者に代わって削除請求をする場合があります。
(3) その他
1. ●本ガイドラインは随時更新されますので、利用前に必ず最新のガイドラインをご確認ください。
2. ●本ガイドラインへのお問合せにはお答えいたしません。ただし、当社著作物の利用許諾を必要とするお客様は、当社にご一報ください。
2019年7月5日制定
2025年11月1日改訂
2026年2月24日改訂
実行結果
Rev.1 と Rev.2 の差分
Twitter が X(旧Twitter) に変わったのところの変化点は分かり易いですね。
TwitCasting が Instagram に入れ替わったところの差分表示がちょっと不自然に見えますが,仕様に沿った正しい動作です。
おそらく,この改訂で一番議論を呼んだのは 2.(1) 利用態様 が 2.(1) 禁止される利用態様 に変わったところだと思います。
Rev.2 と Rev.3 の差分
前回の改訂で議論を呼んだ(と思われる)2.(1) 禁止される利用態様 が 2.(1) 利用可能な利用態様 に変わりましたが,完全に元に戻った訳ではありません。
また AI プログラムが生成した棋譜利用の項目が移動していますね。
まとめ
今回のサンプルのファイルサイズ(文字コードは Shift_jis です)および文字数(Unicode 単位)を以下に示します。
| Rev. | 制定/更新 | ファイルサイズ (bytes) |
文字数 |
|---|---|---|---|
| Rev.1 | 2019年7月5日 | 2,918 | 1,604 |
| Rev.2 | 2025年11月1日 | 3,722 | 2,034 |
| Rev.3 | 2026年2月24日 | 3,714 | 2,033 |
Core i5-12500, 3.0GHz(base)/4.6GHz(MAX), 16GB, Windows11 25H2 で下記の実行時間でした。
Rev.1 と Rev.2 の比較:約2.5秒
Rev.2 と Rev.3 の比較:約3.2秒
$\color{red}{\Huge\textsf{遅 過 ぎ る}}$
このスピードだと Qiita の利用規約4のサイズ(プレーンテキストでも 20kBytes 以上)になるとお手上げです。実際にはメモリ不足になると思いますが。
JavaScript が遅いせいなのか,アルゴリズムが悪いせいなのか分かりませんが,小さな例題にも関わらず(筆者にとっては)既に限界性能です。ちゃんとした diff アルゴリズムを参考文献5を読んで勉強中です。