###
DOI:
Journal of Software:2002.13(10):1933-1942

基于邻接矩阵的全文索引模型
周水庚,胡运发,关佶红
(复旦大学,计算机科学与工程系,上海,200433;武汉大学,计算机学院,湖北,武汉,430079)
Adjacency Matrix Based Full-Text Indexing Models
ZHOU Shui-geng,HU Yun-fa,GUAN Ji-hong
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3237   Download 3346
Received:January 18, 2002    Revised:July 01, 2002
> 中文摘要: 文本信息的急剧增加和越来越多的用户通过在线方式获取文本信息,使得查询效率成为信息检索系统一个突出瓶颈.提出两种新型全文索引模型,用于改善信息检索系统的查询效率.通过使用有向图表示文本串,引出关于文本串的邻接矩阵;采用两种不同的方式实现文本串邻接矩阵,导出了两种基于邻接矩阵的新型全文索引模型,即基于邻接矩阵的倒排文件和基于邻接矩阵的PAT数组.给出了基于新模型的文本查询算法;分析了新模型的存储空间和查询时间的开销,并分别与两种传统索引模型进行了比较.对实际文本库进行了测试以证实新模型的效能.新模型能够以相对于原文较小的空间代价获得较大幅度的查询效率的提高,因此适合于在大规模文本检索系统中应用.
Abstract:With the rapid growth of online text information and user accesses, query-processing efficiency has become the major bottleneck of information retri eval (IR) systems. This paper proposes two new full-text indexing models to impr ove query-processing efficiency of IR systems. By using directed graph to repres ent text string, the adjacency matrix of text string is introduced. Two approach es are proposed to implement the adjacency matrix of text string, which leads to two new full-text indexing models, I.e., adjacency matrix based inverted file and adjacency matrix based PAT array. Query algorithms for the new models are dev eloped and performance comparisons between the new models and the traditional models are carried out. Experiments over real-world text collections are conducted to validate the effectiveness and efficiency of the new models. The new models can improve query-processing efficiency considerably at the cost of much less amount of extra storage overhead compared to the size of original text database, so are suitable for applications of large-scale text databases.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60173027 (国家自然科学基金); the Natural Science Foundation of Hubei Province of China under Grant No.2001ABB050 (湖北省自然科学基金) Supported by the National Natural Science Foundation of China under Grant No.60173027 (国家自然科学基金); the Natural Science Foundation of Hubei Province of China under Grant No.2001ABB050 (湖北省自然科学基金)
Foundation items:
Reference text:

周水庚,胡运发,关佶红.基于邻接矩阵的全文索引模型.软件学报,2002,13(10):1933-1942

ZHOU Shui-geng,HU Yun-fa,GUAN Ji-hong.Adjacency Matrix Based Full-Text Indexing Models.Journal of Software,2002,13(10):1933-1942