JavaScriptで,文字列の差分(diff)をブラウザ上でグラフィカルに可視化するコード

f:id:SourceCode-Student:20141227163941p:image

JavaScriptで,文字列のdiff差分を計算するコード。

テキストベースおよびグラフィカルの両方で,差分を明示する。

上の画像のような出力を得られる。

 

前回のコードを改良したもの。

JavaScriptで,文字列のdiff差分を計算するコード。アルゴリズム動的計画法 - ソフトウェア勉強ログとサンプルコード
http://source-code-student.hatenablog.jp/entry/20141226/p1


今回のコードの改良点:

  • 計算した差分を視覚化できるようにした。おかげで,動作チェックが一目で行なえるようになった。
  • ブラウザ上での実行に最適化した。


今回の保留点:

  • diff差分を文字列(操作シンボル文字列)として毎回求めている。本当は,これをassertして,動作が正しいかどうかをコードで自動的に検証できるようになっており,回帰テストを充実させたい。
  • エディットグラフもきれいに整形したい。
  • 三つ以上の文字列の比較結果をわかりやすく表示できるだろうか?
  • できれば動的計画法の部分だけを抜き出してライブラリ化し、コードを使い回せるようにしたい。


コード:

<input type="button" value="計算開始" onclick="f()"><br>
<br>

<!-- グラフィカルに結果を表示 -->
<div id="my_div" style="font-size:250%;letter-spacing:1px;"></div>
<br>
<br>

<!-- テキストベースで結果を表示 -->
<pre id="my_pre"></pre>


<style>

/* ログ出力領域 */
#my_div, #my_pre {
	height : 400px;
	overflow-y : scroll;
	padding : 10px;
	margin : 10px;
	background-color : ghostwhite;
}

/* 差分操作の着色 */

span._diff_remove {
	color : red;
	font-weight : bold;
	
	text-decoration : line-through;
	-moz-text-decoration-color : maroon;
}

span._diff_add {
	color : blue;
	font-weight : bold;
}

span._diff_keep {
	color : dimgray;
}

</style>


<script>


function f(){

	new DiffTaker()
		.set_output_target( $("my_pre") )
		.set_richtxt_target( $("my_div") )

		.test( "通報しました", "通報しますた" )
		.test( "go", "goes" )
		.test( "go", "went" )
		.test( "go", "gone" )
		.test( "make", "made" )
		.test( "take", "takes" )
		.test( "take", "took" )
		.test( "take", "taken" )
		.test( "choose", "chose" )
		.test( "chose", "chosen" )
		.test( "have", "has" )
		.test( "abcdef", "bbacddg" )//.assert_symbols("")
	;

}




// TODO:2次元配列のラッパーOBJがほしい


// ※Array拡張時は,配列の要素をthisに代入しないよう気をつける。
// http://d.hatena.ne.jp/language_and_engineering/20141226/JavaScriptCallMethodArg

// 配列のイテレータ
Array.prototype.each = function( func ){
	for( var i = 0; i < this.length; i ++ ){
		func.call( this, this[i], i ); 
	}
	return this; // チェインを継続
};

// map
Array.prototype.map = function( func ){
	var _arr = [];
	this.each(function( item, ind ){
		_arr.push( func.call( _arr, item, ind ) );
	});
	return _arr;
};

Array.prototype.filter = function( func ){
	var _arr = [];
	this.each(function( item, ind ){
		if( func( item, ind ) ){
			_arr.push( item );
		}
	});
	return _arr;
};


function $( dom_id ){
	return document.getElementById( dom_id );
}


// 以下はメインの計算オブジェクト


// 文字列のdiffを計算するオブジェクト
// 比較対象を引数に渡す
var DiffTaker = function( str_old, str_new ){
	
	// モードを判定
	this.judge_mode();


};
DiffTaker.prototype = {
	
	
	// ---------- 起動時 ---------
	
	
	// 実行モード CUI/GUI
	cui_mode : false,
	
	is_cui_mode : function(){
		return this.cui_mode;
	}
	,
	is_gui_mode : function(){
		return ! this.cui_mode;
	},
	
	judge_mode : function(){
		if( typeof( window ) == "undefined" )
		{
			// WSHで実行中とみなす
			this.cui_mode = true;
		}else{
			// ブラウザで実行中とみなす
			this.cui_mode = false;
		}
	}
	,
	
	// GUIモードの場合,ログ出力先のDOMを指定
	set_output_target : function( elem ){
		this.output_dom = elem;
		return this;
	},
	
	output_dom : null,
	
	// リッチテキストによる結果出力先
	set_richtxt_target : function( elem ){
		this.richtxt_dom = elem;
		return this;
	},
	
	richtxt_dom : null,
	
	
	// ---------- 比較処理 ---------
	
	
	// 2つの文字列の比較を実行
	test : function( str_old, str_new ){

		// まずプロパティを色々初期化
		// このメソッドが呼ばれるたびに新たな比較対象を生むから
		this.str_old             = str_old;
		this.str_new             = str_new;
		this.operation_symbols   = null;
		this.operation_rich_text = null;
		this.eg                  = null;
		this.eg_i_arr            = [ null ];
		this.eg_j_arr            = [ null ];

		// 計算を開始
		this.calculate();
		
		return this;
	}
	,

	// 比較対象の文字列
	str_old : null,
	str_new : null,
	
	
	// 計算を実行
	calculate : function(){
		// エディットグラフの作成
		this.init_edit_graph();
		this.calc_edit_graph();
		
			this.dump_edit_graph();
		
		// バックポインタをたどって最短経路を決定
		this.trace_back_pointers();
		
			//this.dump_pointers();
			//this.dump_route_on_graph();
			this.dump_operations();
			
		// 差分生成操作を表すシンボル文字列を生成
		this.calc_operation_symbols();
			this.dump_operation_symbols();
		
		if( this.is_gui_mode() ){
			// 差分生成操作を表すリッチテキストを生成
			this.generate_rich_text();
			this.display_rich_text();
		}
	}
	,
	
	
	// ---------- 動作試験用 ---------
	
	
	// 差分の生成結果をassert検査
	assert_symbols : function( expected_value ){
		var actual_value = this.operation_symbols;
		
		// テキスト形式でログ
		this.log( 
			"[ "
			+ this.assert_count
			+ " ] actual : '" 
			+ actual_value
			+ "', expected : '"
			+ expected_value
			+ "'\n"
		);
		
		this.assert_count ++;
		
		if( expected_value == actual_value ){
			this.log( "assert : OK\n" );
			
			return this;
		}else{
			this.log( "assert : NG\n" );
			
			// おかしい結果が出たらここでメソッドチェインを停止
			return null;
		}
	},
	
	// アサート回数
	assert_count : 1,
	
	
	// 差分操作を表すシンボル文字列表記を取得
	calc_operation_symbols : function(){
		this.operation_symbols = this.array_best_points.map(function( item ){
			return item.desc_sym;
		}).filter(function( item ){
			return (
				( item )
				&&
				(
					( "" + item ).length > 0 
				)
			);
		}).join(",");
	},
	
	operation_symbols : null,
	
	
	// リッチテキスト(というかHTML形式の視覚的な表示方法)を生成
	generate_rich_text : function(){
		this.operation_rich_text = this.array_best_points.map(function( item ){
			return item.desc_html;
		}).join("");
	}
	,
	
	operation_rich_text : null,
	
	// リッチテキスト表示
	display_rich_text : function(){
		this.richtxt_dom.innerHTML = ""
			+ this.richtxt_dom.innerHTML
			+ "<br>"
			+ this.operation_rich_text
		;
	}
	,
	
	
	// 以下は内部のアルゴリズム
	

	// ---------- エディットグラフ ---------

	
	// eg[ i ][ j ] のようにi座標とj座標でアクセス
	eg : null,
	
	// すみっこに各文字列がセットされる
	eg_i_arr : [ null ],
	eg_j_arr : [ null ],

	// iとjの最大値
	getMaxI : function(){
		// 文字数分に原点が加わるので-1しなくてよい
		return this.str_old.length;
	},
	
	getMaxJ : function(){
		return this.str_new.length;
	},
	
	// 表示整形用
	tb : "\t",

	// エディットグラフ上の点を操作
	
	get_point : function( i, j ){
		return this.eg[ i ][ j ];
	},
	
	// 距離(コスト)のGET/SET
	set_cost : function( i, j, cost ){
		this.get_point( i, j ).total_cost = cost;
	},
	get_cost_at : function( i, j ){
		return this.get_point( i, j ).total_cost;
	},
	

	// 初期化
	init_edit_graph : function(){
		// すみっこ
		for( var i = 0; i < this.getMaxI(); i ++ ){
			this.eg_i_arr.push( this.str_old.charAt( i ) );
		}
		for( var j = 0; j < this.getMaxJ(); j ++ ){
			this.eg_j_arr.push( this.str_new.charAt( j ) );
		}
	
		// 盤
		this.eg = [];
		for( var i = 0; i <= this.getMaxI(); i ++ ){
			this.eg.push([]);
			
			for( var j = 0; j <= this.getMaxJ(); j ++ ){
				this.eg[ i ].push( 
					// 点
					new EditGraphPoint( 
						i, 
						j, 
						this.eg_i_arr[ i ],
						this.eg_j_arr[ j ]
					)
				);
			}
		}
	},
	
	// グラフ上の各点に距離を算出
	calc_edit_graph : function(){
	
		// グラフ上の全点に対して
		for( var i = 0; i <= this.getMaxI(); i ++ ){
			for( var j = 0; j <= this.getMaxJ(); j ++ ){
			
				// この点の前までの最小コスト
				var minimum_cost_info = this.getMinimumCostBefore( i, j );
				var prev_minimum_cost = minimum_cost_info.cost;
				
				var p = this.get_point( i, j );
				
				// この点が同じ文字で,なおかつすみっこではないなら
				if( p.hasSameChars() && ( i > 0 ) && ( j > 0 ) ){
					// 左上の最小コストを引き継ぐ。
					// バックポインタも左上を指す
					this.set_cost( i, j, this.get_cost_at( i - 1, j - 1 ) );
					p.backPointerIJMinus();
				}
				else
				{
					// 前までの最小コストよりも1増える。
					// バックポインタは前の最小コストを指す。
					this.set_cost( i, j, prev_minimum_cost + 1 );
				}
			
			}
		}
		
	},
	
	
	// ある点の前までの最小コスト(バックポインタをセットしながら算出)
	// コストだけでなく,どの点からくるのが最小かという座標も返す
	getMinimumCostBefore : function( i, j ){
		var p = this.get_point( i, j );
	
		if( ( i == 0 ) && ( j == 0 ) )
		{
			// 原点ならコスト0になるように調節
			return {
				cost : -1,
				i : 0,
				j : 0
			};
		}
		else 
		if( i == 0 )
		{
			// J方向にたどる
			p.backPointerJMinus();
			return {
				cost : this.get_cost_at( 0, j - 1 ),
				i : 0,
				j : j - 1
			};
		}
		else 
		if( j == 0 )
		{
			// i方向にたどる
			p.backPointerIMinus();
			return {
				cost : this.get_cost_at( i - 1, 0 ),
				i : i - 1,
				j : 0
			};
		}
		else
		{
			// 隅っこの点ではない場合,詳しく比較
		
			// 隣接する手前の点のうち小さいほう
			var parray = [

				{
					cost : this.get_cost_at( i, j - 1 ),
					func : "backPointerJMinus",
					i : i,
					j : j - 1
				},
				{
					cost : this.get_cost_at( i - 1, j ),
					func : "backPointerIMinus",
					i : i - 1,
					j : j
				}
			];
			parray.sort(function(v1, v2){
				return ( v1.cost > v2.cost ) ? 1 : -1;
			});
			p[ parray[0].func ]();
			
			return parray[0];
		}
	},
	
	
	// 末尾からバックポインタをたどる
	trace_back_pointers : function(){
		// 末尾
		var point = this.get_point( this.getMaxI(), this.getMaxJ() );

		var continue_flag = true;
		var arr_bp = [];
		while( continue_flag ){
			// この座標と,そのバックポインタの向きを記録
			var pos = point.get_back_pointer_pos();
			arr_bp.push({
				i : point.i, 
				j : point.j,
				s : pos.s,
				desc_seq : pos.desc_seq,
				char_i : point.char_i,
				char_j : point.char_j,
				desc_sym : pos.desc_sym,
				desc_html : pos.desc_html
			});
			
			if( ( point.i == 0 ) && ( point.j == 0 ) ){
				// 始点から先へは進まない
				continue_flag = false;
			}
			else
			{
				// 手前の点へ移る
				point = this.get_point( pos.i, pos.j );
			}
		}
		
		// 先頭からに並び替える
		arr_bp.reverse();
		
		this.array_best_points = arr_bp;
	},


	// ----- デバッグ出力用 ----
	
	
	log : function( s ){
	
		// nullが来たら空文字で改行する
		if( ( "" + s  ).length < 1 ){
			s = "";
		}
	
		if( this.is_cui_mode() ){
			// コンソール出力
			WScript.Echo( s );
		}else{
			// TODO:ログ出力モードのPREまたはTEXTAREAモード?

			this.output_dom.innerHTML = s 
				+ "\n" 
				+ this.output_dom.innerHTML
			;
		}
	},
	
	// エディットグラフを文字列にダンプして表示
	dump_edit_graph : function(){
		// 表示内容:
		// 旧文字列と新文字列,
		// 各点におけるコスト,
		// 各点におけるバックポインタの向き。
		
		var s = "";
		
		// 旧文字列
		s += ( this.tb + this.eg_i_arr.map(function( item ){ 
			return ( ( item == null ) ? "null" : item ); 
		}).join(this.tb) ) + "\n\n\n";
		
		// 行ごとに2段に分けて出力
		for( var j = 0; j <= this.getMaxJ(); j ++ ){
			if( j == 0 ){
			}else{
				s += this.tb + this.dumpJLineFirst( j ) + "\n";
				s += this.tb + this.dumpJLineFirst2( j ) + "\n\n";
			}
			s += this.eg_j_arr[ j ] + this.tb + this.dumpJLineSecond( j ) + "\n";
			s += this.tb + this.dumpJLineThird( j ) + "\n\n";
		}
		
		this.log( s + "\n" );
	},
	
	// あるjについてグラフを出力(二段目)
	dumpJLineSecond : function( j ){
		var s = "";
		
		for( var i = 0; i <= this.getMaxI(); i ++ ){
			s += this.get_cost_at( i, j );
			if( i < this.getMaxI() ){
				// 右側の点が「←」を持っていれば
				if( this.get_point( i + 1, j ).bp_iminus ){
					s += " ←←";
				}else{
				}
				s += this.tb;
			}
		}
		
		return s;
	}
	,
	
	// あるjについてグラフを出力(三段目)
	dumpJLineThird : function( j ){
		var s = "";
		
		for( var i = 0; i <= this.getMaxI(); i ++ ){
			s += this.get_point( i, j ).charPair() + this.tb;
		}
		
		return s;
	}
	,
	
	// あるjについてグラフを出力(一段目)
	dumpJLineFirst : function( j ){
		var s = "";
		
		for( var i = 0; i <= this.getMaxI(); i ++ ){
 			// この点が「↑」を持っていれば
 			if( this.get_point( i, j ).bp_jminus ){
 				s += "↑";
 			}else{
 				s += " ";
 			}
 
			if( i < this.getMaxI() ){
				// 右の点が「\」を持っていれば
				if( this.get_point( i + 1, j ).bp_ijminus ){
					s += "\";
				}else{
				}

				s += this.tb;
			}
		}
		
		return s;
	}
	,
	
	// あるjについてグラフを出力(一段目+)
	dumpJLineFirst2 : function( j ){
		var s = "";
		
		for( var i = 0; i <= this.getMaxI(); i ++ ){
 			// この点が「↑」を持っていれば
 			if( this.get_point( i, j ).bp_jminus ){
 				s += "↑";
 			}else{
 				s += " ";
 			}
 
			if( i < this.getMaxI() ){
				// 右の点が「\」を持っていれば
				if( this.get_point( i + 1, j ).bp_ijminus ){
					s += " \_";
				}else{
				}

				s += this.tb;
			}
		}
		
		return s;
	}
	,
	
	// 経路を文字列にダンプして表示
	dump_pointers : function(){
		var s = "";
		
		for( var i = 0; i < this.array_best_points.length; i ++ ){
			var ap = this.array_best_points[ i ];
			s += "(" 
				+ ap.i 
				+ ", "
				+ ap.j
				+ "), ("
				+ ap.char_i
				+ ", "
				+ ap.char_j
				+ ") "
				+ ap.s
				+ "  \r\n"
			;
		}
		
		this.log( s + "\n" );
	},
	
	// 経路をグラフ上の道として文字列にダンプして表示
	dump_route_on_graph : function(){
		var s = "";
		
		for( var i = 0; i <= this.getMaxI(); i ++ ){
			for( var j = 0; j <= this.getMaxJ(); j ++ ){
				s += this.get_point( i, j ).get_back_pointer_pos().w;
			}
			s += "\r\n";
		}
		
		this.log( s + "\n" );
	}
	,
	
	// 差分の生成操作を文字列にダンプして表示
	dump_operations : function(){
		var s = this.str_old 
			+ "\n"
			+ this.array_best_points.map(function( item, ind ){
				return item.desc_seq;
			}).join("\n")
			+ "\n"
			+ this.str_new
		;
		
		this.log( s + "\n" );
	}
	,
	
	// 差分操作のシンボル文字列を出力
	dump_operation_symbols : function(){
		this.log( this.operation_symbols + "\n" );
	}
	
};
// edit graph上の座標
var EditGraphPoint = function( i, j, char_i, char_j ){
	this.i = i;
	this.j = j;
	this.char_i = char_i;
	this.char_j = char_j;
	this.total_cost = 0;
};
EditGraphPoint.prototype = {
	// 最短経路のバックポインタの方向
	bp_iminus  : false,
	bp_jminus  : false,
	bp_ijminus : false,
	
	backPointerIMinus : function(){
		this.bp_iminus  = true;
		this.bp_jminus  = false;
		this.bp_ijminus = false;
	},
	backPointerJMinus : function(){
		this.bp_iminus  = false;
		this.bp_jminus  = true;
		this.bp_ijminus = false;
	},
	backPointerIJMinus : function(){
		this.bp_iminus  = false;
		this.bp_jminus  = false;
		this.bp_ijminus = true;
	},
	
	get_back_pointer_pos : function(){
		if( this.bp_iminus ){
			return { 
				i : this.i - 1,
				j : this.j,
				s : "i - 1",
				w : "↑",
				desc_seq : "旧文字" + this.char_i + "を削除",
				desc_sym : "-" + this.char_i,
				desc_html : "<span class='_diff_remove'>"
					+ this.h( this.char_i )
					+ "</span>"
			};
		}
		else
		if( this.bp_jminus ){
			return { 
				i : this.i,
				j : this.j - 1,
				s : "j - 1",
				w : "←",
				desc_seq : "新文字" + this.char_j + "を追加",
				desc_sym : "+" + this.char_j,
				desc_html : "<span class='_diff_add'>"
					+ this.h( this.char_j )
					+ "</span>"
			};
		}
		else
		if( this.bp_ijminus ){
			return { 
				i : this.i - 1,
				j : this.j - 1,
				s : "ij - 1",
				w : "\",
				desc_seq : "同文字" + this.char_i,
				desc_sym : this.char_i,
				desc_html : "<span class='_diff_keep'>"
					+ this.h( this.char_i )
					+ "</span>"
			};
		}
		else
		{
			return {
				s : null,
				w : "○",
				desc_seq : "差分をスタート"
			};
		}
	}
	,
	
	// HTML用エスケープ
	h : function( s ){
		return (
			( "" + s )
				.replace( />/g, "&gt;" )
				.replace( /</g, "&lt;" )
		);
	},
	
	// 保有している2文字について
	
	charPair : function(){
		return ( 
			"(" 
			+ ( this.char_i == null ? "NA" : this.char_i )
			+ "," 
			+ ( this.char_j == null ? "NA" : this.char_j )
			+ ")"
		);
	}
	,
	
	hasSameChars : function(){
		return ( this.char_i == this.char_j );
	}
};


</script>