最好写的suffix tree(suffix array)算法?

其实我只是想放几个link进来,然后把相关chrome tabs都关了(省内存)。

有至少6年没写suffix array了,另外大概半年内听谁说过似乎有个OI界不怎么用的04年的算法,正好最近要用到后缀树,但我是绝对不会蛋疼尝试写Ukkonen的,抱着会不会有个比U家后缀树简单的算法的想法,所以看了看整个suffix tree有什么新东西没有……很遗憾的是好…像…没…有………………suffix array倒有一两个。

http://homepage3.nifty.com/wpage/links/suffix_trees.html 不知道这家伙的列表全不全,反正好像没什么意思,什么时候蛋特别疼的时候再看看好了…(我想可能几年内都不会这么疼的)

然后既然打算写了就顺便科普一下好了…

SA以前有个3个字母一组,按起始位移12分别递归,再根据递归结果把起始位移为0的也加进来一起排序的算法。(Juha Karkkainen and Peter Sanders 2003,或者DC-3算法?)鄙人当年觉得写起来好像不太爽、radix三层 + 2/3递归是不是常数因子有点儿大就从没写过。(所以以前一直写n log n的,而且为了省事写n log^2 n,这病得治,然而已经是慢性病了(

这个Pang Ko and Srinivas Aluru的看上去不错,简要说起来,就是如果s[i:] < s[i+1:]那么i的label是小,不然i的label是大;s[len:]也就是$的label都算。算label就倒着扫一遍。

然后先根据第一个字母把所有后缀都排序了(radix sort,但这里我们说桶排,因为排完先别把桶扔了)。然后,有个性质是起始字母相同的后缀一定是label大的比label小的小。其实假设第一个字母是x,label大的就是<xxx…的,label小就是>xxx…的,所以也可以理解为大的靠左,小的靠右。假设大后缀数目比较多,接着用递归把小后缀的想办法给排序了,反之就排大的。要排序就只能把相间的部分缩成字符集(但是变长是个大问题)。所以排序是个子问题,先说排序后的事情。

如果小后缀的顺序都排好了,那么原来每个桶中的小后缀也都可以线性排好顺序(倒过来,每个都放到它自己的桶的最后,然后把它的位置固定掉)。接着只要把大后缀的排序。大后缀有个毛病,它的下一个后缀一定排在自己前面。第一个桶其实是$,里面就一个后缀$。按顺序去读每个桶和桶中的后缀,假设这个后缀是s[i:],如果s[i-1:]是label大的后缀,就把s[i-1:]调整到s[i-1:]所在桶的第一个,并固定住它。正确性是因为,我们读到的东西都已经是顺序的了,而且根据读取过的东西立刻调整s[i-1:]的位置,每次调整一定会把被调整的东西放到正确的位置,这是因为一个桶内的后缀的从第二个字母开始排序的顺序跟整体的后缀顺序是一致的。由于大后缀一定会被之前的某个东西调整,所以能保证在读到接下来它的时候,它已经是被调整到正确的位置上了。

回来看准备递归的过程,相间substring转换成字符集最大的问题在于不定长的字符串中如果一个是另一个的前缀,就坑爹了。所以解决办法是substring定义为包含后面一个小后缀的首字母,即如果两个相邻的小后缀,分别在i和j位置开始,那么substring定义为s[i..j]。这样,如果一个substring是另一个的前缀,则长的那个是小大大大大大小而短的是小大大小,根据前面提的大比小靠左的规则,短的要靠后,长的靠前,顺序就定出来了。

现在的问题就是如何把这些不定长的字符串们排序,这还是我这!辈!子!第一次见到桶排一边排一边添新桶的!怎么用线性时间把它实现就看你自己的了。大不了用链表。其实可以用桶的最后一个元素代表这个桶。具体做法是,把所有字母装桶(具体的桶),再根据它是第几个字母分别挪到第几行,不同的桶内的字符划条竖线以示区别。根据第二行的分割,对第一行的桶进行细分(怎么做不用再说了吧),再根据第三行的分割对第一行进行细分,……就好了。字符集做好了,就可以递归了。其实这个桶的性质很好,都跟棵树一样了。那么,就只用把同一个桶中的如果有多个substring,对那个桶排序就可以了吧,但是比较可惜这里做不了太多优化,只能把原字符串中连续出现单字符桶缩成一个,递归完了之后,可以在当前的桶的基础上挪一挪。(不做这个优化就不用挪桶里的东西,利弊自己想)

上面链接的列表里面有个Ge Nong, Sen Zhang and Wai Hong Chan, Two Efficient Algorithms for Linear Suffix Array Construction, 2008. 其实就是这个算法的小改进。如果说原来是把字符串从小后缀的地方拆掉,这个方法仅仅是连续的小后缀就不再拆了,因为它们要么起始字符不同,要么在同一个桶中的顺序是已知的。也就是加了一条规则,两个连续的小中间不能拆。把能拆的地方叫做非退化小后缀好了。如果能把这样的非退化小后缀用递归排序,则用它可以把大后缀排好,方法跟之前的算法是一样的,正确性的证明也很显然,因为在原来的算法中,如果一个小后缀前面一个后缀是大后缀才会调整,而现在只是不包含这种退化的小后缀。然后用排好的大后缀又可以排好全部小后缀了。

这个算法的好处是非退化小后缀的数目是n/2的,不用再按情况分小后缀多还是大后缀多,代码简化了不少。但是多出来的这个用大后缀再排小后缀的部分略蛋疼,增加了常数因子。另外substring的排序问题又要再讨论一下了。如果一个substring是另一个的前缀,而且分别都是小小…小只是长度不同怎么办(有大的情况跟前面一样)其实这情况不会出现因为肯定要有一个大不然是不拆的,所以只要比大小,大的靠前就OK。

substrings排序的算法其实也不用变了,不过他们说他们弄了一个新的排序方法,意思是说,你不是要比第二个字母、第三个字母吗?别比了,你之前那个递归后排序的方法就是大致OK的,与其比第二个字母、第三个字母,不如用短的去更新长一个字母的,也就是用s[i:]更新s[i-1:]一样的道理,不过由于类似的原因,还是得反复做两次。原理是substring的结构是 小…小大…大小。一开始末尾的 小 的位置放对(小/大 放到桶的 小/大 部分),一轮过去 大…大小 的位置就对了,再一轮 小…小大…大小 也就对了。所以原来的KA03算法的,substring的结构是 小大…大小 跑一轮从左到右的就OK,要注意这次跑的时候,要把桶的大部分和小部分分别看待,然后不管s[i-1:]是大还是小都要按照s[i:]进行位置调整。

然后这个论文大致提了一个“新算法”似乎是把长的substring以d为大小给它切了,反正切了在substring数目上也是n/2级别的。这样就只要用radix排序substring了,后面我实在没啥兴趣看。

这个东西其实我刚看两页,就产生了一种浓浓的“中国学术道德底下”感…写个post应该还不错,实际效果好也行,发paper就,很不舒服,因为概念都[KA03]是跟一样的,如果是用软件做反抄袭我怕真的通不过,客观地说是灌水…改进就老实说,整合过来就很不好了。当然如果发的是lower conference,倒也不为过。但这个不为过理论让我想到在国外不能大肆污染环境但是中国可以,你看北京的天……总之感觉非常不好。其实在点开论文之前,我是没有偏见的,因为没觉得作者是中国人文章就一定是中国风…当然,也有可能是作者们写文章的时候没注意到尽量不要将别人的东西直接搬过来这点…

zgl(大家好久没见cmdButtons这个id了吧我增加一下这个id的存在感)给了个link http://arxiv.org/abs/1101.3448 说 lcp数组是可以跟着这个算法一起算出来的,不用那个lcp(s[i:], s[next(i):]) >= lcp(s[i-1:], s[next(i-1):]) -1的方法了,而且更快。我就不蛋疼了…

Advertisements

One response to this post.

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

w

Connecting to %s

%d 博主赞过: