注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

还东国的博客

行之苟有恒,久久自芬芳

 
 
 

日志

 
 

(转载)BWT算法  

2011-04-18 09:28:45|  分类: 算法及数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
BWT算法(转)
2010/12/11 16:23

bowtie使用的算法~

 

全称Burrows-Wheeler transform ,BW是两位发明者的明称,T则是强调这种算法的特性。

这种算法是非常巧妙的。

这种算法是先把输入的数据则重排列,使得相同的字符,尽量地排在一起,这样方便压缩。如果只是想把相同的字符放在一起,可以简单地对各个字符统计一下出现次数,然后放在一起。这种算法巧妙的地方是,它还可以根据重新排列后的字符串,算出原始的字符串,从而解压缩。

重排列的过程如下:

把输入串的所有rotation(所谓rotation是指轮换,比如abcd有四个轮换,abcd,bcda,cdab,dabc)排序,然后依次把这些rotation的最后一个字符串接起来成为新的串。这里要注意两个地方,一是各个字符出现的次数是否跟源串相同,二是相同的字符是否更多地放在一起。

第一点是很容易证明,取这些rotation的任意一位串连起来,各个字符出现的次数跟源串都是相同的。

第二点很难证明,现在粗略分析一下。假设源串含有the,排序的结果应该是"he"打头的ratation排在一起,这样最后一个字符是"t"的字符也应该排在一起。为什么不用这些rotation的第一位串联起来呢?用第一位的话,解释起来更直观,但是用第一位串联起来的话,无法反映射回去。

现在来讨论一下怎么反映射。反映射的算法非常巧妙,从OI到ACM都考过这道题。有O(N)的算法的,实现起来也不难,只是比较难想到。

用banana举例,它的六个rotation排序为

abanan

anaban

ananab

banana

nabana

nanaba

则转换后的结果为nnbaaa,因为是有序的,我们可以反推出第一列应该为aaabnn,从而可以知道有下列六对相邻关系

na,na,ba,ab,an,an

这些相邻关系里最小的一对应该是ab,把这六组相邻关系排序一下,为ab,an,an,ba,na,na

从而知道六个rotation的第二列分别为b,n,n,a,a,a

如果不是这样的话,则它们不应该这样排列,这其实是反证法

从而可以得出另一组相邻关系,nab,nan,ban,aba,ana,ana,继续上面的过程,可以得出长度为四的相邻关系,一步步递推,最终得出原始的所有的rotation。但是怎么知道哪个rotation是源串呢?只要在源串的结束处加一个特殊字符,然后再求rotation,最终结束符放在最后的rotation就是源串了。

上面的实现是很低效的,是O(n^2)的,O(n)的实现我也忘了,不过上面的过程已经说明这个算法可以用了。而且一般来说,都是分块压缩的,n不会很大,平方的算法也够了。


  评论这张
 
阅读(1250)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017