中文搜索引擎分块倒排索引存储模式

doi:10.11772/j.issn.1001-9081.2013.07.2031

计算机应用 ›› 2013, Vol. 33 ›› Issue (07): 2031-2036.DOI: 10.11772/j.issn.1001-9081.2013.07.2031

中文搜索引擎分块倒排索引存储模式

马健¹,张太红¹,²,陈燕红¹

1. 新疆农业大学计算机与信息工程学院，乌鲁木齐 830052
2. 中国农业大学信息与电气工程学院，北京 100083

收稿日期:2013-01-25 修回日期:2013-03-06 出版日期:2013-07-01 发布日期:2013-07-06
通讯作者: 张太红
作者简介:马健(1984-)，男，新疆乌鲁木齐人，硕士，主要研究方向：搜索引擎、数据库；张太红(1965-)，男，甘肃静宁人，教授，主要研究方向：数据库；陈燕红(1979-)，女，新疆乌鲁木齐人，讲师，硕士，主要研究方向：数据库。
基金资助:
新疆维吾尔自治区科技攻关项目(200931103)

New inverted index storage scheme for Chinese search engine

MA Jian¹,ZHANG Taihong¹,²,CHEN Yanhong¹

1. College of Computer and Information Engineering, Xinjiang Agricultural University, Urumqi Xinjiang 830052, China
2. College of Information and Electrical Engineering, China Agricultural University, Beijing 100083, China

Received:2013-01-25 Revised:2013-03-06 Online:2013-07-06 Published:2013-07-01
Contact: ZHANG Taihong

摘要/Abstract

摘要： 针对开源搜索引擎ASPSeek中的倒排索引的内部结构和访问模式，抽象出了倒排索引的形式化定义。为解决ASPSeek倒排索引更新困难和直接采用操作系统文件缓冲访问机制带来的效率问题，以125万张中文农业网页为样本，结合其特点，提出了一种块大小可变的分块倒排索引存储模式和基于CLOCK替代策略的专用缓冲管理机制。实验结果表明在禁用和启用缓冲的情况下，分块访问模式检索效率都优于ASPSeek。在启用缓冲并使用16万中文词条或5万高频中文词条作为测试集合的条件下，分块存储模式在访问倒排索引100万次后的检索时间趋于常量，即使以全部的827309个词条作为测试集合的条件下，分块存储模式在访问倒排索引200万次后的检索时间趋于收敛。

关键词: 倒排索引, 搜索引擎, 全文检索, 分块结构, 检索效率

Abstract: After analyzing inverted index structure and access mode of an open source search engine-ASPSeek, this paper gave an abstract definition of "inverted index". In order to solve the difficulties of inverted index updating and the efficiency issues caused by directly accessing inverted index through file caching of operating system in ASPSeek, considering the characteristics of 1.25 million Chinese agricultural Web pages, this article proposed a new blocking inverted index storage scheme with a buffer mechanism which was based on CLOCK replacement algorithm. The experimental results show that the new scheme is more efficient than ASPSeek whether the buffer system is disabled or enabled. When the buffer system got enabled and 160 thousand Chinese terms or 50 thousand high-frequency Chinese terms were used as a test set, the retrieval time of new scheme tended to be a constant after one million accesses. Even when using entire 827309 terms as a test set, the retrieval time of new scheme began to converge after two million accesses.

Key words: inverted index, search engine, full-text retrieval, blocking structure, retrieval efficiency

中图分类号:

TP311

马健张太红陈燕红. 中文搜索引擎分块倒排索引存储模式[J]. 计算机应用, 2013, 33(07): 2031-2036.

MA Jian ZHANG Taihong CHEN Yanhong. New inverted index storage scheme for Chinese search engine[J]. Journal of Computer Applications, 2013, 33(07): 2031-2036.

参考文献

［1］袁津生，李群．搜索引擎基础教程［M］．北京：清华大学出版社，2010.

［2］李晓明，闰宏飞，王继民．搜索引擎—原理、技术和系统［M］．北京：科学出版社，2006．

［3］MANNING C D, RAGHAVAN P, SCHUTZE H. An introduction to information retrieval ［M］. Cambridge: Cambridge University Press, 2008.

［4］MARGARITIS G, ANASTASIADIS S V. Low-cost management of inverted files for online full-text search ［C］// Proceedings of the 18th Association for Computing Machinery Conference on Information and Knowledge Management. New York: ACM Press, 2009: 2-6.

［5］JARUSKULCHAI C, KRUENGKRAI C. Building inverted files through efficient dynamic hashing ［EB/OL］. ［2012-12-20］.http://canasai.tcllab.org/pubs/ncsec02-hashing.pdf.

［6］ZOBEL J, MOFFAT A. Inverted files for text search engines ［J］. Association for Computing Machinery Computing Surveys, 2006, 38(2): 6.

［7］彭波，李晓明.搜索引擎倒排文件的一种分块组织技术［J］.电子学报,2005，33(2):1-10.

［8］刘小珠，彭智勇，陈旭.高效的随机访问分块倒排文件自索引技术［J］.计算机学报,2010,33(6):977-987

［9］邓攀，刘功申.一种高效的倒排索引存储结构［J］.计算机工程与应用,2008,44(31):149-152

［10］WITTEN I H, MOFFAT A, BELL T C. Managing gigabytes: compressing and indexing documents and images ［M］. 2nd ed. Waltham, MA: Morgan Kaufmann, 1999.

［11］ANH V N, MOFFAT A. Inverted index compression using word-aligned binary codes ［J］. Information Retrieval, 2005, 8(1): 151-166.

［12］SHIEH W-Y, SHANN J J, CHUNG C-P. An inverted file cache for fast information retrieval ［J］. Journal of Information Science and Engineering, 2003, 19(4): 681-695.

［13］杨晓波.倒排文件索引缓存机制的优化［J］.计算机系统应用,2012,21(5):96-99.

［14］吴文娟，车明．搜索引擎倒排索引技术的改进［J］．微处理机，2006,27(6):83-85.

［15］MARKATOS E P. On caching search engine query results ［J］. Computer Communications, 2001,24(2): 137-143.

［16］SARAIVA P C, de MOURA E S, ZIVIANI N, et al. Rank-preserving two-level caching for scalable search engines ［C］// Proceedings of the 24th Annual International Association for Computing Machinery Special Interest Group on Information Retrieval Conference on Research and Development in Information Retrieval. New York: ACM Press, 2001: 51-58.

[1]	吴悦, 雒江涛, 刘锐, 胡钟尹. 基于感知哈希和切块的视频相似度检测方法[J]. 计算机应用, 2021, 41(7): 2070-2075.
[2]	姜琨, 刘征, 朱磊, 李晓星. 基于有向无环图的倒排链等字长划分压缩算法[J]. 计算机应用, 2021, 41(3): 727-732.
[3]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[4]	戴厚乐, 杨庚, 闵兆娥. 分布式环境下多关键词并行密文检索方案[J]. 计算机应用, 2019, 39(10): 2948-2954.
[5]	张硕望, 欧阳纯萍, 阳小华, 刘永彬, 刘志明. 融合《知网》和搜索引擎的词汇语义相似度计算[J]. 计算机应用, 2017, 37(4): 1056-1060.
[6]	胡庆辉, 魏士伟, 解忠乾, 任亚峰. 基于递归自编码器的广告短语相关性[J]. 计算机应用, 2016, 36(1): 154-157.
[7]	冶忠林, 杨燕, 贾真, 尹红风. 基于语义扩展的短问题分类[J]. 计算机应用, 2015, 35(3): 792-796.
[8]	王景中, 邱铜相. 基于TF-IDF改进算法的聚焦主题网络爬虫[J]. 计算机应用, 2015, 35(10): 2901-2904.
[9]	冯汝伟谢强丁秋林. 基于文本聚类与分布式Lucene的知识检索[J]. 计算机应用, 2013, 33(01): 186-188.
[10]	杨欣欣李培峰朱巧明. 基于查询扩展的人名消歧[J]. 计算机应用, 2012, 32(09): 2488-2490.
[11]	张维刚徐永东雷小强何辉. Web全文检索中间件的设计与应用[J]. 计算机应用, 2011, 31(08): 2261-2264.
[12]	薛献鹏彭明田贺怀清. 基于Memcached的日历搜索引擎系统优化设计与实现[J]. 计算机应用, 2011, 31(03): 865-868.
[13]	谭龙江. 基于搜索引擎优化的网络宣传机模型[J]. 计算机应用, 2010, 30(8): 2232-2234.
[14]	张妤芝刘海涛. P级文件系统搜索概述[J]. 计算机应用, 2010, 30(3): 813-817.
[15]	张祖莲卡米力·木衣丁王命全. 一种有效预防点击欺诈的算法[J]. 计算机应用, 2010, 30(07): 1794-1796.

中文搜索引擎分块倒排索引存储模式

New inverted index storage scheme for Chinese search engine

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics