一种大规模字符串文本的后缀索引构造方法及装置

摘要

本发明公开了一种大规模文本的后缀索引构造方法及装置，本发明在后缀索引构造过程中至少配置大规模字符串读取器，后缀前驱信息处理器，LMS后缀识别器，两个外存优先级队列容器和外存排序器。通过大规模字符串读取器读取字符串，LMS识别器识别字符串中的LMS子串或后缀，外存优先级队列容器实现子串或后缀的排序，最终完成大规模字符串文本的后缀索引构造。在索引构造过程中，利用了低成本的计算机外存资源，使得后缀索引构造不再受限于内存容量；从而在任意一台普通计算机环境下，本发明能完成超过该内存大小的字符串文本数据的后缀索引构造，突破现有后缀索引构造技术方案的局限性。且本发明具有运行速度快、I/O量小和简单易行等优点。

主权项

一种大规模文本的后缀索引构造方法，其特征在于，所述方法包括：收缩字符串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的后缀索引。