(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(10)申请公布号 CN 105335481 A
(43)申请公布日 2016.02.17
(21)申请号 CN201510659972.6
(22)申请日 2015.10.14
(71)申请人 广东顺德中山大学卡内基梅隆大学国际联合研究院;中山大学
    地址 528300 广东省佛山市顺德区大良街道办广东顺德中山大学卡内基梅隆大学国际联合研究院
(72)发明人 刘伟军 农革
(74)专利代理机构 广州粤高专利商标代理有限公司
    代理人 林丽明
(51)Int.CI
      G06F17/30
                                                                  权利要求说明书 说明书 幅图
(54)发明名称
      一种大规模字符串文本的后缀索引构造方法及装置
(57)摘要
      本发明公开了一种大规模文本的后缀索引构造方法及装置，本发明在后缀索引构造过程中至少配置大规模字符串读取器，后缀前驱信息处理器，LMS后缀识别器，两个外存优先级队列容器和外存排序器。通过大规模字符串读取器读取字符串，LMS识别器识别字符串中的LMS子串或后缀，外存优先级队列容器实现子串或后缀的排序，最终完成大规模字符串文本的后缀索引构造。在索引构造过程中，利用了低成本的计算机外存资源，使得后缀索引构造不再受限于内存容量；从而在任意一台普通计算机环境下，本发明能完成超过该内存大小的字符串文本数据的后缀索引构造，突破现有后缀索引构造技术方案的局限性。且本发明具有运行速度快、I/O量小和简单易行等优点。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种大规模文本的后缀索引构造方法，其特征在于，所述方法包括：       
收缩字符串T，得到新的字符串T1，T1的规模最多为T的一半；       
以直接方式或递归方式构造T1的后缀索引；       
扫描T1的后缀索引，得到T的后缀索引；       
其中，所述收缩字符串T，得到新的字符串T1的具体过程为：       
使用大规模字符串读取器分批读取字符串T，获取T中所有LMS子串，压入外存优先级队列容
器Q1中；扫描Q1排序L子串，并使用子串命名单元对L子串和LMS子串进行命名，得到的有序L子串存放于外存优先级队列容器Q2中；扫描Q2中所有L子串排序S子串，并对S子串命名，得到有序S子串；提取S子串中所有LMS子串的名字，这些名字按照LMS子串在原字符串中的索引位置升序构成新的字符串T1；       
所述构造字符串T1的后缀索引的过程为：       
当字符串T1中所有字符都唯一，各字符的名称即为各后缀在后缀索引中的优先级次序，扫描字符串T1，每个索引位置生成相应的二元组：（T[i]，i），即（字符名称，位置索引），将这些二元组全部压入外存排序器，按照字符名称排序，排序后取各字符对应的索引号存入数组，即得到T1的后缀索引，否则以T1为新的字符串输入参数，用递归方式构造T1的后缀索引；       
所述扫描T1的后缀索引，得到T的后缀索引的过程为：       
使用大规模字符串读取器读取字符串T，识别其中的LMS后缀，根据T1的后缀索引，给相应的LMS后缀赋予优先级，并压入外存优先级队列容器Q1中；       
扫描Q1，得到的有序L后缀，L后缀存放于外存优先级队列Q2中；       
扫描Q2，得到有序S后缀序列；       
归并所有L和S后缀，得到字符串T的后缀索引。       
2.根据权利要求1所述的大规模文本的后缀索引构造方法，其特征在于，所述LMS子串的识别方法为，该子串的首字符和尾字符均为LMS字符，首字符与尾字符之间不存在任何LMS字符，则该子串为LMS子串；       
所述LMS字符的识别方法为，当后缀为LMS后缀时，则该后缀所对应字符子串的首字符为LMS字符；       
所述LMS后缀的识别方法为，若当前后缀为S后缀，且字符串T中与当前后缀相邻的左手边第一个后缀为L后缀，则该后缀为LMS后缀；       
所述L子串的识别方法为，子串的首字符为L字符，尾字符为LMS字符，且首字符与尾字符之间不存在任何LMS字符，则该子串为L子串；       
所述L/S字符的识别方法为，若某后缀为L或S后缀，则该后缀所对应字符子串的首字符分别称为L或S字符；       
所述S子串的识别方法为，子串的首字符为S字符，尾字符为LMS字符，且首字符与尾字符之间不存在任何LMS字符，则该子串为S子串；       
所述L后缀、S后缀的识别方法为，假定字符串最后一个字符为‘$’，该字符在整个字符串所包含的字符当中最小并且唯一，为S后缀；然后从字符串文本倒数第二个字符开始往前扫描，若当前字符比前一字符小，则该后缀为S后缀；或当前字符与前一字符相等且前一字符所对应的后缀为S后缀，则该后缀也为S后缀；除上述两种情况之外，后缀被识别为L后缀。       
3.一种大规模文本的后缀索引构造装置，其特征在于，包括：       
字符串长度可以用lenngtn吗js
大规模字符串读取器（1），用于顺序读取外存大规模字符串文本T；       
后缀前驱信息处理器（2），用于生成字符串文本中各后缀的前驱信息；       
其中，所述后缀前驱信息为一个元组，该元组包含了该后缀在字符串中的位置信息，前驱字
符以及前驱字符距离；前驱字符为：在字符串文本T中，后缀i对应的字符为T[i]，T[i]左侧第一个不等于T[i]的字符称为后缀i的前驱字符；       
前驱信息存储模块（3），是一种外存容器，用于存放后缀前驱信息处理器（2）所输出的各后缀前驱信息；       
LMS后缀识别器（4），用于识别具体的后缀是否为LMS后缀；       
L/S后缀识别器（5），用于识别具体的后缀是L还是S后缀；       
子串命名单元（6），用于在索引构造过程中，对字符子串进行命名，以便字符串规模的收缩；       
外存优先级队列容器（7），包括容器Q1、Q2，用于在外存上对字符子串或后缀进行排序，每次从该队列弹出的子串或后缀为当前队列中最小或最大子串或后缀；       
外存排序器（8），也是一种外存容器，可对存入其中的对象按照指定关键字排序；       
后缀索引存储模块（9），也是一种外存容器，用于存储后缀索引。                       
说  明  书
<p>技术领域   
本发明涉及后缀索引构造技术领域，尤其涉及一种利用计算机外存来构造大规模字符串文本后缀索引的方法及装置。   

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。