一种BWT实现方法中对后缀进行排序的方法及系统

本发明提供一种BWT实现方法中对后缀进行排序的方法及系统，通过对需要排序的后缀通过双向搜索，获得后缀位置，对所述后缀进行排序并进行信息更新的方式，通过在变换时间和资源消耗上的平衡，解决了原始BWT变换方法消耗资源大、压缩率低的问题。本发明能实现数据压缩速度快、简单，且使用资源比较合理，能节省大量资源。

1.一种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，更新所述后缀链表以及段的信息，其中所述后缀链表由后缀段组成，并按照段首元素从小到大顺序排列的，所述段首元素是每个段里面后缀的开头元素。
2.如权利要求1所述的对后缀进行排序的方法，其特征在于，所述步骤3包括：步骤31，找到段头、段尾位置对应的两个后缀；步骤32，分别将段头和段尾对应的后缀记为S_m、S_n，并与所述后缀S_i进行大小比较，如果S_i<S_n或者S_i>S_m，则执行步骤34；如果S_n<S_i<S_m，则执行步骤33；步骤33，找到S_m、S_n指向段内方向的相邻的两个后缀，将S_m、S_n替换为这两个后缀，再与S_i进行大小比较，如果S_i<S_n或者S_i>S_m，则执行步骤34；如果S_n<S_i<S_m，则执行步骤32；步骤34，结束双向搜索，记录S_i位置，如果S_i<S_n，则S_i的位置在S_n邻近的低地址，S_i>S_m，则S_i的位置在S_m邻近的高地址，其中所述段头段尾分别是段里面的最小后缀和最大后缀。
3.如权利要求1所述的对后缀进行排序的方法，其特征在于，所述步骤4包括：步骤41，令控制参数k自增1，第一次执行步骤41的时候初始化k为0，然后查看appear[i+k]和apprear[i-k]，如果appear[i+k]=1或者appear[i-k]=1，结束双向查找，然后执行步骤42；如果appear[i+k]=0并且appear[i-k]=0，则重复步骤41，其中appear[i+k]和apprear[i-k]分别代表以ASCⅡ表中数字i+k和i-k代表的元素为段首元素的段是否已经出现过的标识；步骤42，如果appear[i+k]=1，则S_i的位置在以元素i+k为段首元素的段的段尾邻近的低地址；如果appear[i-k]＝1，则S_i的位置在以元素i-k为段首元素的段的段头邻近的高地址。
4.如权利要求1所述的对后缀进行排序的方法，其特征在于，所述步骤6包括：步骤61，如果上一个步骤是步骤3，则执行步骤63；如果上一个步骤是步骤4，则执行步骤62；步骤62，将这个段的存在信息改为已经存在，令appear[i]=1，同时把max[i]的值min[i]都置为S_i在后缀链表中的地址；步骤63，更新相应段的max[i]以及min[i]信息，将段头段尾中存放的地址加1，其中所述相应段指的是断首元素大于或者等于后缀S_i的开头元素的段，min[i]记录以ASC Ⅱ表中数字i代表的元素为为段首元素的段尾对应的后缀在后缀链表中的地址，max[i]记录以ASC Ⅱ表中数字i代表的元素为为段首元素的段头对应的后缀在后缀链表中的地址。
5.如权利要求1所述的对后缀进行排序的方法，其特征在于，所述后缀链表里的后缀都是成段出现的，而且每一段的段首元素是按字典序从小到大排列的。
6.一种BWT实现方法中对后缀进行排序的系统，其特征在于，包括：提取模块，从BWT的待变换序列中取出需要排序的后缀；处理模块，判断以所述后缀的开头元素作为断首元素的段在后缀链表中是否出现过，所述后缀的开头元素的ASC Ⅱ值为i，如果寄存器appear[i]=1，则出现过，执行第一双向搜索模块；如果寄存器appear[i]=0，则未出现过，执行第二双向搜索模块，其中appear[i]代表以ASC Ⅱ表中数字i代表的元素为段首元素的段是否已经出现过的标识；第一双向搜索模块，在段内进行双向搜索，获得所述后缀在所述后缀链表中的位置，然后执行后缀排序模块；第二双向搜索模块，在所述后缀链表中进行双向搜索，搜索到离所述后缀最近的在所述后缀链表中存在的段，根据所述段获得所述后缀在所述后缀链表中的位置，其中所述段是以相同元素开头的后缀按从小到大顺序组成的序列，然后执行后缀排序模块；插入后缀模块，将所述后缀插入后缀链表：将所述后缀的段的高地址上的所有后缀右移一位，将所述高地址所在的位置空出，然后在所述高地址后缀所在的位置上插入所述后缀，然后执行更新模块；更新模块，更新所述后缀链表以及段的信息，其中所述后缀链表由后缀段组成，并按照段首元素从小到大顺序排列的，所述段首元素是每个段里面后缀的开头元素。
7.如权利要求6所述的对后缀进行排序的系统，其特征在于，所述第一双向搜索模块包括：后缀搜索模块，找到段头、段尾位置对应的两个后缀；比较模块，分别将段头和段尾对应的后缀记为S_m、S_n，并与所述后缀S_i进行大小比较，如果S_i<S_n或者S_i>S_m，则执行记录位置模块；如果S_n<S_i<S_m，则执行替换比较模块；替换比较模块，找到S_m、S_n指向段内方向的相邻的两个后缀，将S_m、S_n替换为这两个后缀，再与S_i进行大小比较，如果S_i<S_n或者S_i>S_m，则执行记录位置模块；如果S_n<S_i<S_m，则执行比较模块；记录位置模块，结束双向搜索，记录S_i位置，如果S_i<S_n，则S_i的位置在S_n邻近的低地址，S_i>S_m，则S_i的位置在S_m邻近的高地址，其中所述段头段尾分别是段里面的最小后缀和最大后缀。
8.如权利要求6所述的对后缀进行排序的系统，其特征在于，所述第二双向搜索模块包括：初始化处理模块，令控制参数k自增1，第一次执行初始化处理模块的时候初始化k为0，然后查看appear[i+k]和apprear[i-k]，如果appear[i+k]=1或者appear[i-k]=1，结束双向搜索，然后执行位置确定模块；如果appear[i+k]=0并且appear[i-k]=0，则重复执行初始化处理模块，其中appear[i+k]和apprear[i-k]分别代表以ASC Ⅱ表中数字i+k和i-k代表的元素为段首元素的段是否已经出现过的标识；位置确定模块，如果appear[i+k]＝1，则S_i的位置在以元素i+k为段首元素的段的段尾邻近的低地址；如果appear[i-k]＝1，则S_i的位置在以元素i-k为段首元素的段的段头邻近的高地址。
9.如权利要求6所述的对后缀进行排序的系统，其特征在于，所述更新模块包括：判断执行模块，如果上一个模块是第一双向搜索模块，则执行信息处理模块；如果上一个模块是第二双向搜索模块，则执行信息修改模块；信息修改模块，将这个段的存在信息改为已经存在，令appear[i]=1，同时把max[i]的值min[i]都置为S_i在后缀链表中的地址；信息处理模块，更新相应段的max[i]以及min[i]信息，并将段头段尾中存放的地址加1，其中所述相应段指的是断首元素大于或者等于后缀S_i的开头元素的段，min[i]记录以元素i为段首元素的段尾对应的后缀在后缀链表中的地址，max[i]记录以元素i为段首元素的段头对应的后缀在后缀链表中的地址。
10.如权利要求6所述的对后缀进行排序的系统，其特征在于，所述后缀链表里的后缀都是成段出现的，而且每一段的段首元素是按字典序从小到大排列的。