Space and time optimized algorithm of n-Gram/2L index structure

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (5): 180-183.

• 数据库与信息处理 • Previous Articles Next Articles

Space and time optimized algorithm of n-Gram/2L index structure

LIU Feng-chen¹,LIU Qing-wen²,HU Yue²,HUANG He¹

1.College of Software，Beijing University of Aeronautics and Astronautics，Beijing 100083，China
2.Department of Computer Science，Beijing University of Science and Technology，Beijing 100083，China

Received:2007-06-05 Revised:2007-08-13 Online:2008-02-11 Published:2008-02-11
Contact: LIU Feng-chen

n-Gram/2L索引结构的存储与时间优化算法

刘凤晨¹,刘庆文²,胡玥²,黄河¹

1.北京航空航天大学软件学院，北京 100083
2.北京科技大学计算机科学系，北京 100083

通讯作者: 刘凤晨

Abstract

Abstract: This paper presents an improved algorithm of n-Gram/2L index for text retrieval by adding document identifier index into the secondary level inverted index，and proposes a retrieval algorithm：n-Gram/2LZ（n-Gram/2L on Zigzag join） based on Zigzag join.This algorithm retains the advantage of former n-Gram/2L algorithm and reduces redundancy and storage of the document index，while retrieving and indexing large data.And the optimization of the query algorithm decreases the system overhead when processing query as well as enhances query efficiency by reducing reading the same record repeatedly.

Key words: algorithms, indexing, n-gram, inverted index

摘要： 对分词检索算法n-Gram/2L的索引结构作了改进，在第二级倒排表中加入对文章标识的索引，提出一种基于Zigzag的分词检索算法n-Gram/2LZ（n-Gram/2L on Zigzag join）。在对数据量较大的文章进行检索和索引时，该算法在保留原有算法特性的基础上进一步减少了索引冗余，降低了索引的存储量，同时对查询算法的优化降低了查询时的系统开销，并且减少索引中记录访问次数，提高了查询效率。

关键词: 算法, 索引, n-gram, 倒排表

LIU Feng-chen¹,LIU Qing-wen²,HU Yue²,HUANG He¹. Space and time optimized algorithm of n-Gram/2L index structure[J]. Computer Engineering and Applications, 2008, 44(5): 180-183.

刘凤晨¹,刘庆文²,胡玥²,黄河¹. n-Gram/2L索引结构的存储与时间优化算法[J]. 计算机工程与应用, 2008, 44(5): 180-183.

[1]	WU Hao, XU Xingjian, MENG Fanjun. Knowledge Graph-Assisted Multi-task Feature-Based Course Recommendation Algorithm [J]. Computer Engineering and Applications, 2021, 57(21): 132-139.
[2]	CHEN Yuanwen. Application of MapReduce Technology in Problem of Material Transportation and Stowage [J]. Computer Engineering and Applications, 2021, 57(12): 273-278.
[3]	CHEN Lin, ZHONG Weidong, YANG Xiaoyuan, LIU Wenchao. Mixed Intelligent Side Channel Analysis Attack Method for SM4 [J]. Computer Engineering and Applications, 2019, 55(23): 86-91.
[4]	CUI Liqun, ZHANG Ping, HE Qingjie, LU Hao. Research on Saliency Detection of Contrast and Detail Enhancement [J]. Computer Engineering and Applications, 2019, 55(23): 200-208.
[5]	ZHU Xuefeng, XU Tianyang, WU Xiaojun. Correlation Filter Tracking Based on Self-Learning Features [J]. Computer Engineering and Applications, 2019, 55(20): 58-64.
[6]	CHEN Chao, ZHANG Li. Three-Dimensional Path Planning Based on Improved Ant Colony Algorithm [J]. Computer Engineering and Applications, 2019, 55(20): 192-196.
[7]	ZENG Chunyan, YE Jiaxiang, WANG Zhifeng, WU Minghu. Survey of Compressed Sensing Reconstruction Algorithms in Deep Learning Framework [J]. Computer Engineering and Applications, 2019, 55(17): 1-8.
[8]	WANG Yongkang, YUAN Weihua, ZHANG Zhijun, WEN Peng. Recommendation Algorithm Integrating Time Based Latent Semantic Completion Model with Subgroup Partitioning [J]. Computer Engineering and Applications, 2019, 55(16): 130-137.
[9]	AN Zhaoxiang, QU Youli. Research on Inverted Index Compression Algorithm with Variable Coding Units [J]. Computer Engineering and Applications, 2019, 55(15): 82-88.
[10]	XIA Yangyang, LIU Yuan, HUANG Yadong. Central-constraints possibilistic C-means algorithms based on source domain [J]. Computer Engineering and Applications, 2018, 54(5): 72-78.
[11]	ZHENG Hao, DONG Mingli, PAN Zhikang. Target tracking algorithm with multiple algorithms in collaboration based on image classification [J]. Computer Engineering and Applications, 2018, 54(4): 185-191.
[12]	REN Shengbing, WANG Zhijian, WANG Yu. Layout mining and pattern matching algorithm on automatic Web page design [J]. Computer Engineering and Applications, 2018, 54(3): 227-232.
[13]	LIU Hefei1, CHEN Xiaohong2, RUAN Tong1. Survival prediction of game guild based on joint models for longitudinal and survival data [J]. Computer Engineering and Applications, 2018, 54(14): 264-270.
[14]	LIN Ting1, LOU Xiaoping1,2, LIU Feng1,2, LI Weixian1,2. Improved feature points matching algorithm on sequence image [J]. Computer Engineering and Applications, 2017, 53(9): 141-145.
[15]	FEI Yunqiao1, LIU Wenping1, LUO Youqing2, LU Pengfei2. Comparison of algorithms for unmanned aerial vehicle image segmentation in monitoring forest diseases and insect pests [J]. Computer Engineering and Applications, 2017, 53(8): 216-223.

Space and time optimized algorithm of n-Gram/2L index structure

n-Gram/2L索引结构的存储与时间优化算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics