高阶熵压缩的全文自索引

作者：霍红卫; 陈晓阳; 陈龙刚; 于强

来源：计算机学报, 2016, (12): 2494-2511.

• 大数据
• 压缩索引
• 自索引
• 高阶熵
• 混合编码 big data
• compressed indexes
• self-indexes
• high-order entropy
• hybrid encoding

大数据集正在以前所未有的速度产生,研制大数据集的实用压缩全文自索引是目前的挑战问题之一.该文提出了一种高阶熵压缩的全文自索引.对于长为n的文本T以及任意k≤clog_σn-1和c<1,该压缩索引占用2nH_k(T)+n+o(n)位的空间,其中Hk(T)表示文本T的k阶经验熵,σ为字符表的大小.此外,该压缩索引可在线性时间O(n)内构造.在此基础上,该文还给出了上述压缩索引的一种实用改进.这种改进引入了混合编码方法,额外的空间开销为o(n)位.对于Pizza&Chili Corpus上的三类典型数据的实验表明:该文的压缩索引较之主流压缩索引在压缩率和查询时间上具有显著的优势.该文所述的压缩索引软...

• 单位
  西安电子科技大学