基于CRF的分区倒排索引压缩算法

doi:10.3969/j.issn.1006-2475.2024.02.006

摘要/Abstract

摘要： 摘要：倒排索引是大型搜索引擎的核心数据结构，本质是倒排列表中整数序列的集合。倒排索引压缩可以有效减少倒排索引所占空间，提高对关键词的检索效率。本文提出的基于条件随机场（CRF）的分区倒排索引压缩算法主要关注域值分区的分区方式。该算法对序列进行预分区，并且使用条件随机场对预分区进行标注并重组，有效减少了压缩时间。根据分区类型，该算法使用相应的编码方式，进一步减少了压缩后的空间占用。与其他倒排索引压缩算法进行对比实验分析，结果表明本文算法在压缩率上超过目前一些域值分区的算法，并且在解压时间上与其他域值分区算法相当。该算法在时间和空间上取得了较好的平衡。

关键词: 关键词：倒排索引, 数据压缩, 域值分区, 条件随机场, 搜索引擎

Abstract: Abstract： The inverted index is the core data structure of a large search engine， which is essentially a collection of integer sequences in an inverted table. Inverted index compression can effectively reduce the space occupied by inverted indexes and improve retrieval efficiency of keywords. The partition inverted index compression algorithm based on conditional random field （CRF） mainly focuses on the partition mode of universe partition. The algorithm pre-partitions the sequence and uses conditional random fields to label and reorganize the pre-partitions， which effectively reduces the compression time. According to the partition type， the algorithm uses the corresponding encoding method to further reduce the space occupation after compression. Compared with other inverted index compression algorithms， this algorithm outperforms some current universe partition algorithms in compression ratio， and is equivalent to other universes partition algorithms in decompression time. The algorithm achieves a good balance between time and space.

Key words: Key words： inverted index, data compression, universe partition, conditional random field, search engines

中图分类号:

TP311

王子琛, 瞿有利. 基于CRF的分区倒排索引压缩算法[J]. 计算机与现代化, 2024, 0(02): 36-42.

WANG Zi-chen, QU You-li. A Partition Inverted Index Compression Algorithm Based on CRF[J]. Computer and Modernization, 2024, 0(02): 36-42.

参考文献

［1］ ILIC M， SPALEVIC P， VEINOVIC M. Inverted index search in data mining［C］// 2014 22nd Telecommunications Forum Telfor （TELFOR）. 2014：943-946.
［2］ SHIN Y， AHN J， IM D H. Join optimization for inverted index technique on relational database management systems［J］. Expert Systems with Applications， 2022，198. DOI: 10.1016/j.eswa.2022.116956.
［3］ WANG H， YUAN Q P， HU W H， et al. A new subsequence similarity retrieval method based on inverted index in EAST［J］. Fusion Engineering and Design， 2022，182. DOI: 10.1016/j.fusengdes.2022.113246.
［4］ CATENA M， MACDONALD C， OUNIS I. On inverted index compression for search engine efficiency［C］// Advances in Information Retrieval. 2014：359-371.
［5］ PIBIRI G E， VENTURINI R. Techniques for inverted index compression［J］. ACM Computing Surveys， 2020，53（6）. DOI: 10.1145/3415148.
［6］ CHMIELOWIEC A， LITWIN P. Efficient inverted index compression algorithm characterized by faster decompression compared with the Golomb-rice algorithm［J］. Entropy， 2021，23（3）. DOI： 10.3390/e23030296.
［7］ LIU X Z， PENG Z Y. An efficient random access inverted index for information retrieval［C］// Proceedings of the 19th International Conference on World Wide Web. 2010：1153-1154.
［8］ ELIAS P. Efficient storage and retrieval by content and address of static files［J］. Journal of the ACM， 1974，21（2）：246-260.
［9］ PIBIRI G E. On slicing sorted integer sequences［J］. arXiv preprint arXiv：1907.01032， 2019.
［10］ CHAMBI S， LEMIRE D， KASER O， et al. Better bitmap performance with roaring bitmaps［J］. Software Practice and Experience， 2014，46（5）：709-719.
［11］ ANH V N， MOFFAT A. Improved word-aligned binary compression for text indexing［J］. IEEE Transactions on Knowledge and Data Engineering， 2006，18（6）：857-861.
［12］ ANH V N， MOFFAT A. Index compression using fixed binary codewords［C］// Proceedings of the 15th Australasian Database Conference-Volume 27. 2004：61-67.
［13］ ZUKOWSKI M， HEMAN S， NES N， et al. Super-scalar RAM-CPU cache compression［C］// 22nd International Conference on Data Engineering （ICDE’06）.2006. DOI: 10.1109/ICDE.2006.150.
［14］ RICE R， PLAUNT J. Adaptive variable-length coding for efficient compression of spacecraft television data［J］. IEEE Transactions on Communication Technology， 1971，19（6）：889-897.
［15］ KAUSHIK R， KRISHNAMURTHY R， NAUGHTON J F， et al. On the integration of structure indexes and inverted lists［C］// Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 2004：779-790.
［16］ MAHAPATRA A K， BISWAS S. Inverted indexes： Types and techniques［J］. International Journal of Computer Science Issues， 2011，8（4）：384-392.
［17］ DING S， ATTENBERG J， SUEL T. Scalable techniques for document identifier assignment in inverted indexes［C］// Proceedings of the 19th International Conference on World Wide Web. 2010：311-320.
［18］ SONG X S， YANG Y X， JIANG Y， et al. Optimizing partitioning strategies for faster inverted index compression［J］. Frontiers of Computer Science. 2019，13（2）：343-356.
［19］ PIBIRI G E， PETRI M， MOFFAT A. Fast dictionary-based compression for inverted indexes［C］// Proceedings of the 12th ACM International Conference on Web Search and Data Mining. 2019：6-14.
［20］ LEMIRE D， SSI-YAN-KAI G， KASER O. Consistently faster and smaller compressed bitmaps with roaring［J］. arXiv preprint arXiv：1603.06549， 2016.
［21］ OTTAVIANO G， VENTURINI R. Partitioned elias-fano indexes［C］// Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval. 2014：273-282.
［22］ SUTTON C， MCCALLUM A. An introduction to conditional random fields［J］. arXiv preprint arXiv：1011.4088， 2010.
［23］ LAFFERTY J D， MCCALLUM A， PEREIRA F C N. Conditional random fields： Probabilistic models for segmenting and labeling sequence data［C］// Proceedings of the 18th International Conference on Machine Learning. 2001：282-289.
［24］ VOGEL S， NEY H， TILLMANN C. HMM-based word alignment in statistical translation［C］// Proceedings of the 16th Conference on Computational Linguistics-Volume 2. 1996：836-841.
［25］ VIGNA S. Quasi-succinct indices［C］// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. 2013：83-92.
［26］ SHREE M R， SHAMBHAVI B R. POS tagger model for kannada text with CRF++ and deep learning approaches［J］. Journal of Discrete Mathematical Sciences and Cryptography， 2020，23（2）：485-493.
［27］ SILVESTRI F. Sorting out the document identifier assignment problem［C］// Advances in Information Retrieval. 2007：101-112.

[1]	郑立瑞, 肖晓霞, 邹北骥, 刘彬, 周展. 基于BERT的电子病历命名实体识别[J]. 计算机与现代化, 2024, 0(01): 87-91.
[2]	周慧, 徐名海, 许晓东. 基于Attention-BIGRU-CRF的中文分词模型[J]. 计算机与现代化, 2022, 0(08): 7-12.
[3]	王运乾, 王以松, 陈攀峰, 邹龙. 融合注意力机制的药用植物文本命名实体识别[J]. 计算机与现代化, 2021, 0(11): 100-105.
[4]	许梦笛, 王金华. 基于深度学习和语法规约的需求文档命名实体识别[J]. 计算机与现代化, 2021, 0(01): 105-110.
[5]	邵诗韵, 周宇, 杨蕾, 钟茂生, 戴芮, 赵家乐. 基于条件随机场的电力工程标书文本实体识别方法[J]. 计算机与现代化, 2020, 0(12): 72-77.
[6]	张诗林. 基于Bi-LSTM和CRF的中文网购评论中商品属性提取[J]. 计算机与现代化, 2019, 0(02): 93-.
[7]	王芮1，韩锐2，贾玉祥1. 基于Spark的分布式大数据机器学习算法[J]. 计算机与现代化, 2018, 0(11): 119-.
[8]	李健龙，王盼卿，韩琪宇. 面向军事领域的中文分词技术研究[J]. 计算机与现代化, 2018, 0(11): 115-.
[9]	程树东，胡鹰. 基于BI-LSTM-CRF模型的限定领域知识库问答系统[J]. 计算机与现代化, 2018, 0(07): 53-.
[10]	张磊. 特定领域的命名实体识别方法的研究[J]. 计算机与现代化, 2018, 0(03): 60-.
[11]	张剑，吴青，羊昕旖，王彬聪，吴宣为，徐向英，吕强. 基于条件随机场的农业命名实体识别[J]. 计算机与现代化, 2018, 0(01): 123-126.
[12]	盛沈阳，何新. 分布式电源监控信息管理系统设计[J]. 计算机与现代化, 2017, 0(1): 89-95.
[13]	戴杨,陈芳. 实时数据库中数据的分类压缩算法[J]. 计算机与现代化, 2016, 0(6): 123-126.
[14]	田洪周1，2，应蓓华2. 无线传感器网络二代小波压缩的性能分析与研究[J]. 计算机与现代化, 2015, 0(9): 81-89.
[15]	贾遂民，张玉,张腾飞. 一种基于介词用法的灾难事件信息抽取方法[J]. 计算机与现代化, 2015, 0(7): 116-.