著者アーカイブ 杉浦

著者:杉浦

if文の様な正規表現である先読み、戻り読み

　正規表現の文法には先読み、戻り読みと呼ばれる記法があります。戻り読みは後読みとも呼ばれます。ここではサクラエディタのヘルプファイルに倣って戻り読みと記述します。

　この記法は英語ではlookahead,lookbihindと呼ばれます。正規表現の途中でこの記法が現れた時、正規表現エンジンは先読み後読みで括られた部分式が文字列のまだ読んでいない先の方やもう読み終わった戻った方にマッチするかしないかを判断します。このマッチング判断は読んでいる文字列の位置を変えません。(?=)(?!)(?<=)(?
　この正規表現はhogeを含まない文字列中のfugaにマッチする正規表現です。先読みはまだ読んでいない先の方を見るだけ、lookaheadするだけで文字列を消費しない記法です。そのため、以下の様なマッチもできます。

　ハイライト部分がマッチしている部分です。行頭から見て.*hogeが成り立たない行のfugaをマッチしているわけです。

著者:杉浦

問題の細分化とソースコードの関数化

　よく関数にまとめることでソースコードが読みやすくなる、再利用しやすくなると言われますが、いきなりその様ことだけ知ってもすぐにできるものではありません。関数化の指針の一つに問題の細分化というものがあります。これは分割された小さな問題ごとに関数にしていくというやり方です。例えば次のコードがあります。

// 与えられた緯度経度に最も近い 'array' の要素を返す。
// 地球が完全な球体であることを前提としている。
var findClosestLocation = function (lat, lng, array) {
	var closest;
	var closest_dist = Number.MAX_VALUE;
	for (var i = 0; i < array.length; i += 1) {
		// 2 つの地点をラジアンに変換する。
		var lat_rad = radians(lat);
		var lng_rad = radians(lng);
		var lat2_rad = radians(array[i].latitude);
		var lng2_rad = radians(array[i].longitude);
		// 「球面三角法の第二余弦定理」の公式を使う。
		var dist = Math.acos(Math.sin(lat_rad) * Math.sin(lat2_rad) +
				Math.cos(lat_rad) * Math.cos(lat2_rad) *
				Math.cos(lng2_rad - lng_rad));
		if (dist < closest_dist) {
			closest = array[i];
			closest_dist = dist;
		}
	}
	return closest;
};
Dustin Boswell; Trevor Foucher. リーダブルコード (Kindle の位置No.1930-1939). 株式会社オライリー・ジャパン. Kindle 版. 

　これはコードの最上部のコメントにあるように、与えられた緯度経度に最も近い 'array' の要素を返す、ことが最終目的の関数です。この目的を達成するためにこのコードは、2地点間の距離を算出する、最小の距離になる'array'の要素を発見する、という二つの問題を解いています。前者の2地点間の距離を算出する、という問題は最終目的から分割して考えられます。分割するという考えに沿ってコードを改造すると次の様になります。

// 与えられた緯度経度に最も近い 'array' の要素を返す。
// 地球が完全な球体であることを前提としている。
var findClosestLocation = function (lat, lng, array) {
	var closest;
	var closest_dist = Number.MAX_VALUE;
	var dist = spherical_distance(lat, lng, array[i].latitude, array[i].longitude);
	for (var i = 0; i < array.length; i += 1) {
		if (dist < closest_dist) {
			closest = array[i];
			closest_dist = dist;
		}
	}
	return closest;
};
function spherical_distance(lat, lng, lat_2, lng_2){
	//地点(lat,lng)と地点(lat_2,lng_2)の球面距離を返す
	// 2 つの地点をラジアンに変換する。
	var lat_rad = radians(lat);
	var lng_rad = radians(lng);
	var lat2_rad = radians(lat_2);
	var lng2_rad = radians(lng_2);
	// 「球面三角法の第二余弦定理」の公式を使う。
	return Math.acos(Math.sin(lat_rad) * Math.sin(lat2_rad) +
		Math.cos(lat_rad) * Math.cos(lat2_rad) *
		Math.cos(lng2_rad - lng_rad));
}

　最初より簡単な関数であるfindClosestLocationとspherical_distanceの二つが出来ました。また、この関数化は再利用等のコードの変更を容易にします。例えば、findClosestLocation中のspherical_distance(lat, lng, array[i].latitude, array[i].longitude)という部分は呼び出す関数名の変更だけで同じような度単位の二地点の緯度経度を引数にする別の関数を用いることが出来ます。二地点間の球面距離の算出というのは多用します。
　問題の細分化の基準として意図と実装の乖離があります。あるコードを書いている時、そのコードに当初と別の目的が存在するならば、それは別の問題である、というものです。

著者:杉浦

正規表現の難題、入れ子構造

　正規表現は便利な技法です。一行ほどの短い文字列で様々な文字列を表現できます。一行で動作させる単純な動作のためか実装されている正規表現の多くは後方参照以外の参照可能な記憶領域を持ちません。入れ子構造を正規表現で表そうとした場合、この記憶領域が無いという仕様が大きくのしかかってきます。
　単純に()の入れ子を考えてみます。

(()(()))

　人間が見やすいようにインデントを付けます。

(
	()
	(
		()
	)
)

　入れ子が正しく結ばれているか、どの始点がどの終点に対応しているかを考えるためには記憶領域が必要になります。
　正しく結ばれているかは、次のルールを守ったまま文字列の終わりまで読み取り切れるか否かで確認できます。
・終点を読み込んだ時、対応する始点が存在する
・読み取り終わった時、今まで読み取った始点、終点の数が等しい
最新以外の始点についての情報が無い場合、対応する始点が存在するか否かがわからず、入れ子の確認ができません。正規表現は後方参照以外に記憶領域を持ちません。このため多くの正規表現は入れ子構造を読み取ることができません。余談ですがデータ構造のひとつであるスタック構造を用いると簡単に入れ子を読み取ることが出来ます。下図はスタック構造のgifです。始点を積み、終点を読んだら始点を一つ取り出す、という動作を繰り返すことで実装できます。
　正規表現には方言がある、と言われるほど、実装が多種多様で様々な拡張がなされています。perlやphpの様なプログラミング言語の一部では正規表現の再帰呼び出しが実装されています。再帰は自身の処理中に自身を呼び出すことが可能な動作です。これで始点を積み上げ、終点で始点を打ち消す、というスタック処理をそのままできます。
　再帰を用いた正規表現の説明書：PHP: 再帰的パターン – Manual