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

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (5): 180-183.

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

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

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

收稿日期:2007-06-05 修回日期:2007-08-13 出版日期:2008-02-11 发布日期:2008-02-11
通讯作者: 刘凤晨

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

摘要/Abstract

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

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

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索引结构的存储与时间优化算法[J]. 计算机工程与应用, 2008, 44(5): 180-183.

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.

[1]	张岐山，陈露露. 基于均衡接近度灰关联的Slope One算法[J]. 计算机工程与应用, 2021, 57(9): 96-102.
[2]	王永贵，李倩玉. 基于KNN-GBDT的混合协同过滤推荐算法[J]. 计算机工程与应用, 2021, 57(9): 103-108.
[3]	孙泽宇，徐琛，苏艳超，李传锋，聂雅琳. 雾计算中跨层感知分簇路由协议[J]. 计算机工程与应用, 2021, 57(9): 109-117.
[4]	张朕通，单玉刚，袁杰. 联合多尺度和注意力机制的遥感影像检测[J]. 计算机工程与应用, 2021, 57(9): 212-216.
[5]	兰红，黄敏. 融合KNN优化的密度峰值和FCM聚类算法[J]. 计算机工程与应用, 2021, 57(9): 81-88.
[6]	闫晓燊，高强，朱思萌，奚学程，赵万生. 亮度不均匀低质量图像中压印字符分割方法[J]. 计算机工程与应用, 2021, 57(8): 185-191.
[7]	高一锴，彭力，徐龙壮. 改进AFSA算法优化TWSVM的火焰识别方法[J]. 计算机工程与应用, 2021, 57(8): 204-213.
[8]	孔继利，张鹏坤，刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237.
[9]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[10]	高铖铖，陈锡程，张瑞，宋秋月，易东，伍亚舟. 三种新型智能算法在疫情预警模型中的应用——基于百度搜索指数的COVID-19疫情预警[J]. 计算机工程与应用, 2021, 57(8): 256-263.
[11]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[12]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[13]	谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
[14]	沈新烽，姜平，周根荣. 改进SSD算法在零部件检测中的应用研究[J]. 计算机工程与应用, 2021, 57(7): 257-262.
[15]	雍玖，王阳萍，党建武，雷晓妹. 改进TLD与ORB的AR系统长时跟踪注册方法[J]. 计算机工程与应用, 2021, 57(7): 178-184.