JavaScriptで,文字列のdiff差分を計算するコード。アルゴリズムは動的計画法


2つの文字列を比較して,動的計画法によりdiffを生成するJavaScriptコード。

コード

// ※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;
};




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

	// 渡した瞬間に計算を開始
	this.calculate();
};
DiffTaker.prototype = {

	// 比較対象の文字列
	str_old : null,
	str_new : null,
	
	
	// edit graph
	
	// eg[ i ][ j ] のようにi座標とj座標でアクセス
	eg : null,
	
	// すみっこに各文字列がセットされる。はじめは空文字列なので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 ]
					)
				);
			}
		}
	},
	
	// 計算を実行
	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();
	},
	
	// グラフ上の各点に距離を算出
	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
			});
			
			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;
	},


	// ----- デバッグ出力用 ----
	
	
	// エディットグラフを文字列にダンプして表示
	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 );
	},
	
	// ある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;
	}
	,
	
	log : function( s ){
		WScript.Echo( 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 );
	},
	
	// 経路をグラフ上の道として文字列にダンプして表示
	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 );
	}
	,
	
	// 差分の生成操作を文字列にダンプして表示
	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 );
	}
	
};
// 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 + "を削除"
			};
		}
		else
		if( this.bp_jminus ){
			return { 
				i : this.i,
				j : this.j - 1,
				s : "j - 1",
				w : "←",
				desc_seq : "新文字" + this.char_j + "を追加"
			};
		}
		else
		if( this.bp_ijminus ){
			return { 
				i : this.i - 1,
				j : this.j - 1,
				s : "ij - 1",
				w : "\",
				desc_seq : "同文字" + this.char_i
			};
		}
		else
		{
			return {
				s : null,
				w : "○",
				desc_seq : "差分をスタート"
			};
		}
	}
	,
	
	// 保有している2文字について
	
	charPair : function(){
		return "(" + this.char_i + "," + this.char_j + ")";
	}
	,
	
	hasSameChars : function(){
		return ( this.char_i == this.char_j );
	}
};


var str_old = "abcdef";
var str_new = "bbacddg";

var dt = new DiffTaker( str_old, str_new );

実行結果

計算済みのエディットグラフのアスキーアート表示と,diff生成手順が出力される。

	null	a	b	c	d	e	f


null	0 ←←←	1 ←←←	2 ←←←	3 ←←←	4 ←←←	5 ←←←	6
	(null,null)	(a,null)	(b,null)	(c,null)	(d,null)	(e,null)	(f,null)	

	↑	 \	 	 	 	 	 
	↑	   \_	 	 	 	 	 

b	1 ←←←	2	1 ←←←	2 ←←←	3 ←←←	4 ←←←	5
	(null,b)	(a,b)	(b,b)	(c,b)	(d,b)	(e,b)	(f,b)	

	↑	 \	 	 	 	 	 
	↑	   \_	 	 	 	 	 

b	2 ←←←	3	2 ←←←	3 ←←←	4 ←←←	5 ←←←	6
	(null,b)	(a,b)	(b,b)	(c,b)	(d,b)	(e,b)	(f,b)	

	↑\	 	 	 	 	 	 
	↑  \_	 	 	 	 	 	 

a	3	2 ←←←	3 ←←←	4 ←←←	5 ←←←	6 ←←←	7
	(null,a)	(a,a)	(b,a)	(c,a)	(d,a)	(e,a)	(f,a)	

	↑	↑	 \	 	 	 	 
	↑	↑	   \_	 	 	 	 

c	4	3 ←←←	4	3 ←←←	4 ←←←	5 ←←←	6
	(null,c)	(a,c)	(b,c)	(c,c)	(d,c)	(e,c)	(f,c)	

	↑	↑	 	↑\	 	 	 
	↑	↑	 	↑  \_	 	 	 

d	5	4 ←←←	5	4	3 ←←←	4 ←←←	5
	(null,d)	(a,d)	(b,d)	(c,d)	(d,d)	(e,d)	(f,d)	

	↑	↑	 	↑\	 	 	 
	↑	↑	 	↑  \_	 	 	 

d	6	5 ←←←	6	5	4 ←←←	5 ←←←	6
	(null,d)	(a,d)	(b,d)	(c,d)	(d,d)	(e,d)	(f,d)	

	↑	↑	 	↑	↑	 	 
	↑	↑	 	↑	↑	 	 

g	7	6 ←←←	7	6	5 ←←←	6 ←←←	7
	(null,g)	(a,g)	(b,g)	(c,g)	(d,g)	(e,g)	(f,g)	

(0, 0), (null, null) null
(0, 1), (null, b) j - 1
(0, 2), (null, b) j - 1
(1, 3), (a, a) ij - 1
(2, 3), (b, a) i - 1
(3, 4), (c, c) ij - 1
(3, 5), (c, d) j - 1
(4, 6), (d, d) ij - 1
(4, 7), (d, g) j - 1
(5, 7), (e, g) i - 1
(6, 7), (f, g) i - 1

○←←←←←←←
↑↑↑\←←←←
↑\\↑↑↑↑↑
↑↑↑↑\←←←
↑↑↑↑↑\\←
↑↑↑↑↑↑↑↑
↑↑↑↑↑↑↑↑

abcdef
差分をスタート
新文字bを追加
新文字bを追加
同文字a
旧文字bを削除
同文字c
新文字dを追加
同文字d
新文字gを追加
旧文字eを削除
旧文字fを削除
bbacddg

仕様と工夫した点

文字列の差分生成のアルゴリズムは,下記のページを参考にした。

文字列の差分(diff)を算出するアルゴリズム:レーベンシュタイン距離とエディットグラフについて- アルゴリズム数値計算法の勉強
http://algorithm-introduction.hatenablog.jp/entry/2015/10/19/145143

  • マトリックスの各点について距離を求め,最短経路を末尾からたどりなおす方法


冒頭のコードは,WSH/JScriptとして動作する。
つまりJSファイルとして保存してダブルクリックすれば単体で動く。

工夫した点は,エディットグラフを見やすくAAで表示できるようにしたところ。

また,専用のオブジェクトに処理を任せたところ。

今後の改善案

タブ区切りだと,WScriptで実行する分には良いのだが,
このようにWebページで見た時に表示がそろわない。
なので別の方法でエディットグラフがきれいに整形されて表示されるように改良したい。

また差分の計算結果を,文字列としてではなく,JSONや配列でデータ構造として吐けるようにしたい。そうすればテストケースを増やせるし,応用しやすい。

また,テストケースをたくさん増やして,回帰テストとしたい。そうすれば安心してリファクタリングできる。

そして,コードがあまりきれいではないと思うので,リファクタリングしたい。

さらに,エディットグラフ上の全点を調査する必要は実際にはないので,処理の高速化の余地がある。改良したら,ベンチマークを取って速度を比較したい。

WSHモードとブラウザモードを自動的に判別し、ログの出力方法を切り替える機能も必要だ。

また、レーベンシュタイン距離を算出して、二つの文字列の類似度を数値的に判定するという機能もつけたい。