JavascriptでSuffixArray

プログラミング Javascript

全文検索エンジンを試作してみたよ - やればできる子の日記とJavascriptを組み合わせてもうちょっとなにかできないかなあと思って、JavascriptでSuffixArrayを作ってみました。
上手い具合に組み合わせるアイデアが思いつけなかった(どうせ全文検索用のインデックスを保持しちゃうので、別途SuffixArrayを保持する意味がなさそう)ので、素のまま公開しちゃいます。
ちなみに、Javascriptも自信ないです。僕はJSでのべ2000行程度しか書いたことないはず。

/* Suffix Array構築のアルゴリズムは色々研究されています。
   以下のコードはかなり最悪なアルゴリズムなので、実用の際は調査してください。*/
function genSA(text){
	var sa = new Array(text.length)
	for(var i = 0; i < text.length; ++i){
		sa[i] = i
	}
	sa.sort(function(l, r){
		substr_l = text.substring(sa[l], text.length)
		substr_r = text.substring(sa[r], text.length)
		if(substr_l > substr_r){
			return +1
		} else if(substr_l < substr_r){
			return -1
		} else {
			return 0
		}
	})
	return sa
}

/* queryにマッチする文字位置を走査するイテレータを返す */
function getSearchIterator(query, text, sa){
	var pos = 0
	var it = {
		hasNext : function(){
			return query == text.substring(sa[pos], sa[pos] + query.length)	
		},
		next : function(){
			return pos++
		}
	}
	/* バイナリサーチすべきだけど面倒なのでリニアサーチ */
	for(;pos < text.length && query != text.substring(sa[pos], sa[pos] + query.length); ++pos){}

	return it
}

/* Rhinoで動かすときのテストコード */
/* jrunscript -encoding utf-8 -f suffixarray.js */
if(print){
	var text = "The GNU General Public License is a free, copyleft license for " +
"software and other kinds of works." + 
"The licenses for most software and other practical works are designed " +
"to take away your freedom to share and change the works.  By contrast, " +
"the GNU General Public License is intended to guarantee your freedom to " +
"share and change all versions of a program--to make sure it remains free " +
"software for all its users.  We, the Free Software Foundation, use the " +
"GNU General Public License for most of our software; it applies also to " +
"any other work released this way by its authors.  You can apply it to " +
"your programs, too."
		var sa = genSA(text)
		for(var it = getSearchIterator("er", text, sa); it.hasNext();){
			var pos = sa[it.next()]
			print(text.substring(pos, pos + 20) + "\n")
		}
}

実行結果は以下の通り。"er"で始まるテキストが抽出できています。

er kinds of works.Th
er practical works a
er work released thi
eral Public License
eral Public License
eral Public License
ers. We, the Free S
ersions of a program

こんな短くてシンプルなアルゴリズムで全文検索ができるようになるなんて、SuffxArrayは良いアルゴリズムだなあと思いますよね。

ところで、作ってる際にSaryを途中までJavaに移植してたのを思い出しました……。
GoogleのAndroidがソフトウェア賞金コンテストをやるというのを聞いて、IMEは良いねらい目かなあと思ってPOBoxやらPrimeやらの移植を検討していたんですよね。Primeは辞書を保持するのにSaryを使っていたんで、PrimeをJavaで動かすにはPrimeの移植(といっても辞書引きの部分だけ)が必要だったのです。
結局、AndroidにIMEを実装するためのインタフェースがない & Primeの作者である小松弘幸さんは現在Google社員→今まさにIME作ってんじゃね?ということに気づき、途中で投げちゃったんですが。や、やろうと思えばできるんだからね!