2011-06-21 22:02:23Morris

[轉貼*] Suffix Array [SA算法]

轉貼至 http://gisyhy.blog.163.com/blog/static/1293903432010590730281/

1、概念

2、倍增算法

3、涉及的所有定理的证明。

4、对于height[]数组的求解和理解。

5、程序模板

一、概念:

1、字符集:简单的说就是字符的集合,但是有个条件,所有字符具有可比性,即有大小关系。

2、字符串:我们用S表示,起始下标为1,终止为n。

3、子串:S中连续的字符串,表示为S[i...j],1<=i <=j <=n。

4、后缀:用suffix(i)表示S[i....n]子串。

5、后缀数组:sa[1-n],sa[i]表示第i小的后缀为suffix(sa[i])。即suffix(sa[i])<=suffix(sa[i+1])。

6、名次数组:rank[1-n],rank[i]表示suffix(i)的名次,第rank[i]小。

备注:字符串的大小怎么定义的?

定义两个字符串s1[],s2[],那么我只说明if(len(s1) < len (s2)),那么s1串要小。

那么我们将S字符串的尾部加入一个'$',他表示字符集中大小最小的字符。即S[n]='$'。

二、倍增算法(DA):

定义:

uk :表示字符串u的前k个字符组成的字符串。

k<=len(u),那么uk= u[1...k];

k>len(u),那么uk= u。

就有性质:suffix(i)2k < suffix(j)2k ,那么<=> suffix(i)k < suffix(j)k  或者 (suffix(i)k= suffix(j)k  且 suffix(i+k)k < suffix(j+k)k)。

怎么求sa,rank?

定义:sa[]k,rank[]k。

sa[i]k:表示k前缀的后缀中第i小的字符串为suffix(sa[i]k)k。

rank[i]k:表示k前缀的后缀suffix(i)k的名次为rank[i]k。

如果求sa[]2k,rank[]2k,那么我们可以通过sa[]k,rank[]k得到,怎么得到的呢?

我们利用性质可以通过rank[]k得到sa[]2k:

if(suffix(sa[i]2k)2k < suffix(sa[j]2k)2k)  ,那么 <=>  rank[i]k < rank[k]  或者 (rank[i]k == rank[j]k  且

(i+k <=n ? rank[i+k]k:0)< (j+k <=n ? rank[j+k]k :0))。

我们看到要限制i+k <=n ,j+k <=n,这是因为如果超出了S串那么肯定为最小字符串,这里用0表示最小就可以。

我们可以用sort排序就可以得到,但是还可以用基数排序为o(n),但是我觉得一般情况下没必要。

三、定理证明:

这里我们要有些定义:

lcp(suffix(i),suffix(j)):表示它们的最长公共前缀。

LCP(i,j):表示LCP(i,j)= lcp(suffix(sa[i]), suffix(sa[j]))。

height[i]:表示height[i]=LCP(i-1,i),height[1]=0;

h[i]:表示h[i]=height[rank[i]]。

定理概括:

1、LCP(i,j) = LCP(j,i)。

2、LCP(i,i) = len(suffix(i))。

3、LCP(i,j) = min{LCP(k-1,k)} , i+1 <=k <=j。

4、对于 1<=i< j<k<=n,LCP(i,k) = min{LCP(i,j),LCP(j,k)}。

5、对于 1<=i<=j<k<=n,LCP(j,k) >= LCP(i,k)。

6、对于i >1 , rank[i] >1 , 那么 h[i] >=h[i-1] -1。

定理1、2是显然成立的,就不证明了。

定理4证明:

对于 1<=i<j <k <=n,那么LCP(i,k) =min{LCP(i,j),LCP(j,k)}。

我们令p = min{LCP(i,j),LCP(j,k)}.         (1)

如果我们证明LCP(i,k) >=p 且 LCP(i,k)<=p ,就ok了。

令suffix(sa[i]) =u,suffix(sa[j]) =v, suffix(sa[k]) =w;

那么由(1)可以知道:up=vp, vp=wp。所以up= wp => LCP(i,k) >=p。 (2)

我们令LCP(i,k)= q > p。

那么可以推出:up =vp =wp 。                    (3)

由(1)我们还可以知道:u[p+1]!=v[p+1] 或者 v[p+1]!=w[p+1],(4)

分析:如果u[p+1]=v[p+1] 且 v[p+1]=w[p+1] ,那么min{LCP(i,j),LCP(j,k)} =p+1>p与(1)矛盾。

我们令u[p+1]=x,v[p+1]=y,w[p+1]=z 。

由 1<=i <j<k<=n,up = vp=wp ,我们知道 x <=y<=z      (5)

又有q>p => q>=p+1, =>  x= z 。 联合(5)可以知道:x=y=z   (6)

好了很明显(4)和(6)矛盾了。因此我们知道  LCP(i,k)  =q <=p。(7)

通过(2)和(7)得到了结论:LCP(i,k)=p = LCP(i,j),LCP(j,k)}。

定理3证明:

其实通过定理4可以顺利证明定理3。

LCP(i,j) = min{LCP(k-1,k)} , i+1 <=k <=j。

 令1<=i<k<j<=n。

min{LCP(i,i+1), ...,  LCP(k-1,k),LCP(k,k+1),..., LCP(j-1,j)} = min{min{LCP(i,i+1),...,LCP(k-1,k)},min{LCP(k,k+1),...,LCP(j-1,j)}}

= min{LCP(i,k),LCP(k,j)} = LCP(i,j)。[定理3]

定理5证明:

对于 1<=i<=j<k<=n,LCP(j,k) >= LCP(i,k)。

如果1<=i=j<k<=n。LCP(j,k)= LCP(i,k).

如果1<=i<j<k<=n,那么LCP(i,k) =min{LCP(i,j),LCP(j,k)}. =>  LCP(j,k) >=LCP(i,k)。

定理6的证明:

对于i >1 , rank[i] >1 , 那么 h[i] >=h[i-1] -1。

如果h[i-1]<=1 ,h[i]>=0 >= h[i-1]-1。

如果h[i-1]>1,令j= i-1, k = sa[rank[j]-1]。

显然 suffix(k) < suffix(j)。(因为rank[k]=rank[j]-1 < rank[j])。(1)

h[i-1]= height[rank[i-1]]=LCP(rank[i-1]-1,rank[i-1]) = LCP(rank[j]-1,rank[j])=lcp(suffix(k),suffix(j)) > 1。(2)

由(2)可以知道:lcp(suffix(k+1),suffix(j+1))=lcp(suffix(k+1),suffix(i)) =h[i-1]-1。

分析:因为lcp(suffix(k),suffix(j)) > 1,因此我们知道s[k]=s[j],因此lcp(suffix(k+1),suffix(j+1)) =lcp(suffix(k),suffix(j)) -1。

由(1)、(2)可以得到rank[k+1]  < rank[j+1]=rank[i]  => rank[k+1] <= rank[i]-1。

因为1<=rank[k+1] <=rank[i]-1 < rank[i],通过定理5可以知道:

LCP(rank[i]-1,rank[i]) >= LCP(rank[k+1],rank[i]) = lcp(suffix(k+1),suffix(i)) = h[i-1]-1。

h[i]=height[rank[i]]= LCP(rank[i]-1,rank[i]) >= h[i-1]-1。的证。

好了,运用定理6,我们可以得到非常想要的结果。

四、height[]数组的求解过程和理解:

其实定理6是为求解height数组做准备,以便优化时间而得到的定理。

有了定理6,我们可以在线性时间(具体复杂度求解就不说了)内得到height数组。

通过分析,我们发现,rank[i]=1,的情况下其实就i=n,因为最后末尾的'$'字符串肯定为最小后缀。

如果i=1, 则说明是起始位置,因为我们suffix(sa[rank[i]-1])和suffix(sa[rank[i]])的0位置开始比较,得到最大公共前缀个数。

如果h[i-1] <=1,那么h[i-1]-1 <=0,对于当前开始比较位置依旧为0,因为最小肯定从开头开始比较啦。

如果rank[i] >1 且 i >1 ,且h[i-1] >1,那么就可以从h[i-1]开始比较,我们知道h[i-1]是最大公共前缀个数,我们知道对于h[i]>=h[i-1]-1,那么也就是 说对于suffix(sa[rank[i]-1])和suffix(sa[rank[i]]),肯定有h[i-1]-1个字符已经匹配了,那么我们从下一 个字符开始匹配就可以了。

求出h数组在用o(n)时间将height数组求出,h[i]=height[rank[i]]。

五、程序模板:

求sa[],rank[],height[]的程序模板:

const int N =20002;

int n,s[N];//原始字符串
int sa[N],rank[N],K,height[N],rk[N],h[N];
bool cmp1(const int & a,const int & b)
{
 return s[a] < s[b];
}
bool cmp2(const int & a,const int & b)
{
 return ((rank[a] < rank[b]) || (rank[a]==rank[b] && 
  ((a+K<=n ? rank[a+K]:0) <(b+K <=n ? rank[b+K]:0))));
}
void suffix_array()
{
 int i;
 for(i=1;i<=n;i++)
  sa[i]=i;
 sort(sa+1,sa+n+1,cmp1);//初始sa[]1
 for(i=1;i<=n;i++){//初始化rank[]1
  if(i==1 || s[sa[i]]!=s[sa[i-1]])
   rank[sa[i]]=i;
  else rank[sa[i]]=rank[sa[i-1]];
 }
 for(K=1; K<n; K*=2){
  sort(sa+1,sa+n+1,cmp2);//求出sa[]2K
  for(i=1;i<=n;i++){
   if(i==1 || cmp2(sa[i],sa[i-1]) || cmp2(sa[i-1],sa[i]))
    rk[sa[i]]=i;
   else rk[sa[i]]= rk[sa[i-1]];
  }
  memcpy(rank,rk,(n+1)*sizeof(int));//求出rank[]2K
 }

 int k;
 for(i=1;i<=n;i++)//求h[]
 {
  if(rank[i]==1){h[i]=0;continue;}
  if(i==1 || h[i-1]<=1)k=0;
  else k = h[i-1]-1;
  while(s[sa[rank[i]-1]+k]==s[sa[rank[i]]+k])k++;
  h[i]=k;
 }
 for(i=1;i<=n;i++)height[rank[i]]=h[i];//求height[]
 }

我们可以在求h的时候就用height代替,h[i]=height[rank[i]],就可以节约o(n)的空间复杂度。

就可以把求height简化一下:

int k;
 for(i=1;i<=n;i++)
 {
  if(rank[i]==1){height[1]=0;continue;}
  if(i==1 || height[rank[i-1]]<=1)k=0;
  else k = height[rank[i-1]]-1;
  while(s[sa[rank[i]-1]+k]==s[sa[rank[i]]+k])k++;
  height[rank[i]]=k;
 }