主权项 |
一种BWT实现方法中对后缀进行排序的方法,其特征在于,包括:步骤1,从BWT的待变换序列中取出需要排序的后缀;步骤2,判断以所述后缀的开头元素的,作为断首元素的段在后缀链表中是否出现过,所述后缀的开头元素的ASC Ⅱ值为i,如果寄存器appear[i]=1,则出现过,执行步骤3;如果寄存器appear[i]=1,则未出现过,执行步骤4,其中appear[i]代表以ASC Ⅱ表中数字i代表的元素为段首元素的段是否已经出现过的标识;步骤3,在段内进行双向搜索,获得所述后缀在所述后缀链表中的位置,然后执行步骤5;步骤4,在所述后缀表中进行双向搜索,搜索到离所述后缀最近的在所述后缀链表中存在的段,根据所述段获得所述后缀在所述后缀链表中的位置,其中所述段是以相同元素开头的后缀按从小到大顺序组成的序列,然后执行步骤5;步骤5,将所述后缀插入后缀链表:将所述后缀的段的高地址上所有后缀右移一位,将所述高地址所在的位置空出,然后在所述高地址后缀所在的位置上插入所述后缀,然后执行步骤6;步骤6,更新所述后缀链表以及段的信息,其中所述后缀链表由后缀段组成,并按照段首元素从小到大顺序排列的,所述段首元素是每个段里面后缀的开头元素。 |