JavaScript: 頻出部分文字列問題

文字列 S 中に閾値以上出現する部分文字列を全て列挙する方法を紹介します(列挙するだけでなく位置、長さ、出現回数もろもろを高速に求める)。率直に言うと接尾辞配列構築する過程で処理を打ち切ると、いい感じに求まります。

手法

• multi key quicksort(3分割法)
• 頻出でない部分文字列とそれを含む上位部分文字列は処理を打ち切る

接尾辞木を利用するより遥かにmemory消費は少なく、下ごしらえも遥かに軽微。計算量はO(n log n)っぽいですが,長大な繰り返しや連長があるとO(n^2)程度になりそうです。

実装編

let minsup=2; // 閾値. これ以上出現する文字を抽出
/*
ssmine(T,SA,a,z,lv)
@T: 文字列を数値配列化したもの
@SA: Tの接尾辞配列もどき
@a: 始点(最初の呼び出しは0)
@z: 終点(最初の呼び出しはS.length)
@lv:部分文字列長(最初の呼び出しは0)
*/
function ssmine(T,SA,a,z,lv){
	if(z-a<minsup)return;
	var p=a+Math.random()*(z-a)|0,r=SA[a];
	SA[a]=SA[p],SA[p]=r;
	for(var t=T[SA[a]+lv],i=a+1,c=z-1,b=i,d=c;;SA[c--]=r){
		for(;b<=c&&(r=T[SA[b]+lv]-t)<1;b++)
			r||(r=SA[i],SA[i++]=SA[b],SA[b]=r);
		for(;b<=c&&(r=T[SA[c]+lv]-t)>=0;c--)
			r||(r=SA[c],SA[c]=SA[d],SA[d--]=r);
		if(b>c)break;
		r=SA[b],SA[b++]=SA[c]
	}
	p=i-a,r=b-i;if(p<r)r=p;
	for(p=a,b-=r;r--;SA[b++]=t)t=SA[p],SA[p++]=SA[b];
	p=d-c,r=z+~d;if(p<r)r=p;
	for(p=b,z-=r;r--;SA[z++]=t)t=SA[p],SA[p++]=SA[z];
	ssmine(T,SA,a,a+=b-i,lv),b+=z+~d;
	if(b-a>=minsup&&~t)lv&&T.get(T,SA,a,b-a,lv),ssmine(T,SA,a,b,lv+1);
	ssmine(T,SA,z-d+c,z,lv)
}

実行例

minsup=2;	// 2未満不可
var S=[97,98,114,97,99,97,100,97,98,114,97],
	a=S.length,n=a,
	I=Array(a);
S[a]=-1; //終端に番兵追加
for(;I[--a]=a;);

//列挙関数の例
//S:文字(数値)配列. I:位置配列. i:I上の出現位置. c:出現数. d:文字列長
function print(S,I,i,c,d){
	console.log("位置",I[i],"数",c," 長さ",d+1,S.slice(c=I[i],c+d+1))
}
S.get=print; //callbackもどき
ssmine(S,I,0,n,0);

codepen的実験装置。画面横幅が狭いと表示しきれない親切設計

See the Pen Mining Frequent Substrings by xezz (@xezz) on CodePen.

参考文献

頻出部分文字列のマイニング