加载中…
个人资料
success
success
  • 博客等级:
  • 博客积分:0
  • 博客访问:36,373
  • 关注人气:1
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

DC3算法理解记录

(2012-11-17 23:23:45)
标签:

it

    今天主要就是理解DC3算法了。

在写关于这个算法的理解之前,我想说一下我对学习算法知识的一点点看法。虽然抄袭是一种很不好的学习习惯。但是写代码确实是一点点积累的过程。要参考别人优秀的代码实现,然后跟学英语什么的一样,模仿,记住。如果自己两眼一闭就开始写代码。发现很难提高,而且总是被一些细节搞的团团转。以后学习过程中要多学习多总结。

好了下面开始写今天看的DC3算法。

还是跟倍增算法的顺序一样,要了解DC3算法,必备的一些知识:基数排序,计数排序等基础知识。

一. DC3的思想介绍:

这一点,我觉得百度一下,好多介绍的。DC3算法主要分为3步:

1)  先将后缀分成两部分,然后最第一部分的后缀排序。

第一部分:后缀kk%3=0);第二部分是后缀kk%3==0)。先对第一部分后缀进行排序。具体做法如下:

suffix1)和suffix2)连接。不过这两个后缀的长度必须都是3的倍数。如果不是3的倍数,那先各自在末尾添0使他们各自为3的倍数。然后每3个字符一组,进行基数排序。把每一组字符合并成一个新的字符之后,用递归的方法求新的字符串的后缀数组。如下图:

后缀数组之DC3算法 - sxnuwhui - sxnuwhui

 

这里有一个问题:原来的字符串必须以一个最小且前面没有出现过的字符结尾,这样才能保证正确,现在我也不太理解。

2)  利用(1)的结果,对第二部分进行排序

剩下的后缀是起始位置%3==0的后缀了。而这些后缀都可以看成是一个字符加上一个已经在1)中排序好的后缀。所以可以利用跟倍增算法一样的排序手段进行排序,可以快速得到这些后缀的sa

3)  1)和2)的结果合并,就可以得到所有后缀的排序结果。

合并操作分两种情况考虑:

1.       suffix3*i)和suffix3*j+1)比较,表示方法如下:

suffix3*i=r[3*i]+suffix(3*i+1)

suffix3*i+1=r[3*j+1]+suffix(3*j+2)

       r[3*i]r[3*j+1]以及suffix3*i+1)和suffix3*i+2)都可以很快得到。

2.       suffix(3*i)suffix(3*j+2)比较,表示方法如下:

suffix(3*i)=r[3*i]+r[3*i+1]+suffix(3*i+2)

suffix(3*j+2)=r[3*j+2]+r[3*j+3]+suffix(3*(j+1)+1)

其中分离的部分的比较都可以通过2)的结果很快得到。这也是之前为什么要合并3个字符的原因。

二. 代码分析:

   #define F(x) ((x)/3+((x)%3==1?0:tb))
    #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) 
    int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; 
    int c0(int *r,int a,int b) 
    {return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];} 
    int c12(int k,int *r,int a,int b) 
    {if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1); 
    else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];} 
    void sort(int *r,int *a,int *b,int n,int m) 
    { 
        int i; 
        for(i=0;i<n;i++) wv[i]=r[a[i]]; 
        for(i=0;i<m;i++) ws[i]=0; 
        for(i=0;i<n;i++) ws[wv[i]]++; 
        for(i=1;i<m;i++) ws[i]+=ws[i-1]; 
        for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i]; 
        return; 
    }
    void dc3(int *r,int *sa,int n,int m)
    {
        int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p; 
        r[n]=r[n+1]=0; 
        for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i; 
        sort(r+2,wa,wb,tbc,m); 
        sort(r+1,wb,wa,tbc,m); 
        sort(r,wa,wb,tbc,m); 
        for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++) 
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++; 
        if(p<tbc) dc3(rn,san,tbc,p); 
        else for(i=0;i<tbc;i++) san[rn[i]]=i;
        for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3; 
        if(n%3==1) wb[ta++]=n-1; 
        sort(r,wb,wa,ta,m); 
        for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i; 
        for(i=0,j=0,p=0;i<ta && j<tbc;p++) 
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++]; 
        for(;i<ta;p++) sa[p]=wa[i++]; 
        for(;j<tbc;p++) sa[p]=wb[j++]; 
        return; 
    }

只要搜索DC3算法,这个代码便是铺天盖地。我来一步一步分析一下代码:

void sort(int *r,int *a,int *b,int n,int m) 
    { 
        int i; 
        for(i=0;i<n;i++) wv[i]=r[a[i]]; 
        for(i=0;i<m;i++) ws[i]=0; 
        for(i=0;i<n;i++) ws[wv[i]]++; 
        for(i=1;i<m;i++) ws[i]+=ws[i-1]; 
        for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i]; 
        return; 
    }//
这个sort函数是典型的计数排序,如果之前理解了倍增算法,这个就是小意思了。

//不过在后来调用的时候可能会有点绕,这个下面会讲到

r[n]=r[n+1]=0; //方便排序操作

 

for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i; 

   //tbc为初始位置%3=0的后缀的个数

   //wa数组存储初始位置%3=0的后缀的第一个字符的下标

   sort(r+2,wa,wb,tbc,m);

   //r+2作为初始地址,那么sort函数实际是将初始位置%3=0的后缀的第3个字符进行//排序,wb数组中存储第1个字符(但是是按照第三个字符有序的)。

   sort(r+1,wb,wa,tbc,m); 

   //同理,排序第2个字符,此时wa数组中为按照后两个字符有序的第一字符的下标

   sort(r,wa,wb,tbc,m);

   //同理,排序第一关键字,此时,wb数组中存储的是按照三个关键字排序完整的后缀的//第一个元素的下标

 

 

   for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++) 
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;

//这个很好理解,就是想判断是否有完全相同的关键字,相同,则rn数组内存的值相等

 

#define F(x) ((x)/3+((x)%3==1?0:tb))

//F(x)计算出原字符串中suffix(x)在新字符串中的位置,参照上图进行分析

int c0(int *r,int a,int b) 
    {return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];} 

//简单的判定是否三个关键字都相等

 

 

if(p<tbc) dc3(rn,san,tbc,p); 

//如果p<tbc,则说明新的字符串中有相等的字符,递归调用dc3,得到新的字符串的sa
      else for(i=0;i<tbc;i++) san[rn[i]]=i;

//如果没有相等的字符,则说明这些后缀已经暂时排序完毕

for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3; 

//先令san[i]==j;如果j<tb,说明i%3==1。此时j*3为为第一关键字的下标

if(n%3==1) wb[ta++]=n-1;

//因为san中没有suffix(n),所以要特殊处理

Sort(r,wb,wa,ta,m);

//wb中存储按照第二关键字有序的第一关键字的下标。排好第一关键字后,wa中存放

//按照两个关键字有序的的第一关键字的下标。及%3==0的下标开始后缀数组的排序结//果。

 

#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) 

//G(x)是和F(x)互逆的操作,G(x)是新字符串的suffix(x)在原字符串中的位置

 

for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i; 

//此时wv相当与第一部分的一个rank,及以G(san[i])开始的的后缀排名为i

 

for(i=0,j=0,p=0;i<ta && j<tbc;p++) 
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++]; 

//这里的思想已经在第三步思想的部分说明的很清楚了
   for(;i<ta;p++) sa[p]=wa[i++]; 
   for(;j<tbc;p++) sa[p]=wb[j++]; 

//上述几行代码就是对这两个部分的合并了。DC3算法理解记录DC3算法理解记录




 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
后一篇:KA理解
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    后一篇 >KA理解
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有