接尾辞Automatonとは、接尾辞を効率的に表現するData構造です(Wikipediaより)。今回はこれを利用して高速に部分文字列とその出現回数を求めます。
このprogramの主な特徴は以下の通りです
-
class State：各状態を表現し、以下の情報を保持します- 部分文字列の長さ
- suffix link
- 次の状態への遷移
- その状態が終端状態かどうか
- その状態を通過する部分文字列の出現回数
-
class SuffixAutomaton：以下の主要なmethodを提供します-
extend: 新しい文字を追加してAutomatonを拡張 -
build: 文字列からAutomatonを構築 -
calculateCount: 各状態の出現回数を計算 -
enumerateSubstrings: 部分文字列とその出現回数を列挙- 第1引数: この値を超える出現回数(既定値=1)の部分文字列のみ列挙
- 第2引数: この値を超える文字数(既定値=1)の部分文字列のみ列挙
-
//Suffix Automatonを使って部分文字列とその出現回数を列挙するprogram
class State{
constructor(){
this.len=0;//状態に対応する部分文字列の長さ
this.link=-1;//suffix link
this.next=new Map;//遷移
this.terminal=false;//終端状態かどうか
this.hit=0//この状態を通過する部分文字列の出現回数
}
}
class SuffixAutomaton{
constructor(){
this.states=[new State];
this.last=this.size=0
}
//文字を追加
extend(c){
let s=++this.size,p=this.last,S=this.states,n;
S[s]=new State;
S[s].len=S[p].len+1;
for(;~p&&!(n=S[p].next).has(c);p=S[p].link)n.set(c,s);
if(~p){
let q=n.get(c);
if(S[p].len+1===S[q].len)S[s].link=q;
else{
let clone=++this.size;
S[clone]={len:S[p].len+1,link:S[q].link,next:new Map(S[q].next),hit:0};
for(;n.set(c,clone),p=S[p].link,~p&&(n=S[p].next).get(c)===q;);
S[q].link=S[s].link=clone
}
}else S[s].link=0;
this.last=s
}
//文字列から Suffix Automaton を構築
build(s){
for(let c of s)this.extend(c);
this.calculateCount()//出現回数を計算
}
//各状態の出現回数を計算
calculateCount(){
let S=this.states,met=[];
function dfs(v){
if(met[v])return;
let s=S[v];
met[v]=true;
for(let[,u]of s.next)
met[u]||dfs(u),
s.hit+=S[u].hit;
s.terminal&&s.hit++ //終端状態の場合、その状態自体でも1回加算
}
//終端状態を記録
for(let c=this.last;~c;c=S[c].link)S[c].terminal=true;
dfs(0)
}
//全ての部分文字列とその出現回数を列挙
enumerateSubstrings(lowC=1,lowL=1){
lowC>>>=0;lowL>>>=0;
let ss=new Map,S=this.states;
const dfs=(v,str)=>{
let c=S[v].hit;
c>lowC&&str.length>lowL&&ss.set(str,c);
for(let[c,next]of S[v].next)dfs(next,str+c);
};
dfs(0,"");ss.delete("");
return ss
}
}
//使用例
function findAllSubstrings(s,lowC=1,lowL=1){
let sa=new SuffixAutomaton;
sa.build(s);
return sa.enumerateSubstrings(lowC,lowL)
}
//test
const text="カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ";
console.log("部分文字列とその出現回数:");
for(let[ss,hit]of findAllSubstrings(text))
console.log(`"${ss}": ${hit}回`)
改良
前述の関数calculateCountとenumerateSubstringsは再帰関数を連呼する事になるので、再帰の限界に達すると処理できません。非再帰版は以下のようになります。変数Qにstackを積んでいきます。
//各状態の出現回数を計算
calculateCount(){
let S=this.states,met=[],p=1,Q=[0],v=this.last;
for(;~v;v=S[v].link)S[v].terminal=true;//終端状態を記録
//深さ優先探索
for(;p;){
if(met[v=Q[p-1]]){p--;continue}
let o=p,s=S[v];
for(let[,u]of s.next)
if(!met[u])Q[p++]=u;
if(o===p){
met[v]=p--;
for(let[_,u]of s.next)s.hit+=S[u].hit;//子nodeの hitを合計
s.terminal&&s.hit++ //終端状態の場合、その状態自体でも1回加算
}
}
}
//全ての部分文字列とその出現回数を列挙
enumerateSubstrings(lowC=1,lowL=1){
lowC>>>=0;lowL>>>=0;
let S=this.states,ss=new Map,p=1,Q=[{v:0,str:""}];
for(;p;){
let{v,str}=Q[--p],s=S[v],c=s.hit;
c>lowC&&str.length>lowL&&ss.set(str,c);
s=s.next;v=p+=s.size;
//逆順に巡回する必要があるので後方から追加
for(let[c,next]of s)
Q[--v]={v:next,str:str+c}
}
ss.delete("");return ss
}
用途
文法圧縮で使えそうです。他の機能も付けられれば便利ですが保留。