正規表現を使わずに「*」限定のワイルドカード検索を作ってみた

Programming a wildcard string search without regular expression.
URLがユーザー定義とマッチするかどうかのプログラムをJavaScript組んでいます。これにワイルドカードを実装してみたのですが、一番手っ取り早い、正規表現による手法だと、文字列エスケープや正規表現のコンパイルやテストの実行などいろいろな計算が介入するので、個人的には処理速度が気になってしまいました。
match.js 
function matchRegKey(keydef, key){
	var s = keydef.replace(/[\-\[\]\/\{\}\(\)\+\?\.\\\^\$\|]/g, "\\$&"); // ワイルドカード以外のエスケープ
	s = s.split("*").join(".*?"); // ワイルドカード「*」を正規表現における表記に変換
	var rex = new RegExp(s);
	return rex.test(key);
}
いろいろ探しても良い情報が見つからなかったので、indexOfとsubstringを駆使した文字列照合によるプログラムを作ってみました。
matchkey.js 
function matchKey(key, keyword){
	var d1 = keydef.indexOf("*");
	if(d1 == -1 && keydef == key) {
		return true;
	}else if(d1 > 0){
		if(keydef.substring(0, d1) != key.substring(0, d1)) return false;
	}
	
	var k1 = 0, klen = keydef.length, match = false, ss;
	while(d1 != -1 && d1 < klen){
		d1++;
		var d2 = keydef.indexOf("*", d1);
		if(d2 == -1){
			d2 = klen;
		}
		
		ss = keydef.substring(d1, d2);
		k1 = key.indexOf(ss, k1);
		
		var kk = key.substring(k1, k1 + (d2 - d1));
		if(kk != ss) return false;
		
		match = true;
		d1 = d2;
	}
	return match;
}
一通りのテストは通ったので、ベンチマークを実施。
test.js 
function TestLoop(){
	var keydef = "*yahoo.*.*";
	var key = "www.yahoo.co.jp";
	
	console.time("regex");
	for(var i =0; i < 100000; i++) matchRegKey(keydef, key);
	console.timeEnd("regex");

	console.time("index");
	for(var i =0; i < 100000; i++) matchKey(keydef, key);
	console.timeEnd("index");
}
私のパソコンでの結果はこのようになりました。正規表現はやはり時間がかかりますね。
2016/07/19
[ 目次 ]