基于空间压缩的外存字符串词典索引算法研究  

Research on Algorithms for Dictionary Index in External Memory Based on Space Compression

作　　者：曹彦婷[1] 

机构地区：[1]苏州农业职业技术学院信息与机电工程系,江苏苏州215008

出　　处：《重庆师范大学学报（自然科学版）》2014年第6期107-115,共9页Journal of Chongqing Normal University:Natural Science

基　　金：江苏省自然科学基金(No.BK2011281);苏州市应用基础研究计划(No.SYG201241)

摘　　要：随着大数据时代的到来,大规模的数据需要处理,其中字符串词典数据占据着越来越大的比重。现有的字符串词典索引,不是空间占用过大,就是数据的本地引用性能差,无法高效地应用到外存磁盘环境。针对这些问题,提出了一种具有高效I/O的压缩索引SB-trie,该索引不仅解决了以往索引空间占用过大的问题,同时也具有良好的本地引用性能,能够很好地工作于外存磁盘环境。实验结果表明,相比现有的索引,该索引不仅在空间上得到了有效的压缩,同时在磁盘环境下具有高效的查找性能。With the coming of big data age, large scale of data needs to be processed, and string dictionaries are becoming a signifi- cant part of it. The existing string dictionary indexes are either too space-consuming, or lack of locality of access, making them in- applicable on the external disk environment settings. Targeted with these problems, we proposed a new string dictionary index data structure SB-trie, which is not only succinct on space, but also has good locality of access, making it I/O efficient on external mem- ory settings. Experiments show that SB-trie consumes less space and has great searching performance on disk environment.

关 键 词：字符串词典索引 外存数据结构 空间压缩 TRIE 大数据处理 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]