一种应用于搜索引擎的索引结构研究
①
刘 畅 张 辉
(北京航空航天大学计算机学院 北京 100083)
摘 要
索引结构是搜索引擎的核心,直接影响着搜索引擎的检索性能。
本文提出了一种新的索引结构,该结构充分利用字符串前缀个数及排列顺序的潜在规律,在查找过程中有效地重用了先前的匹配信息,提高了检索的效率。
关键词:索引结构 搜索引擎 倒排文件中图分类号:TP391.1
Study of Index Structure which Supports the High E ff iciency of Searching
Liu Chang Zhang H ui
(Dept.of Computer Science and Technology ,BUAA ,Beijing 100083)
Abstract :Index structure is the core of a search engine ,it has an influence on the performance of whole search engine direct 2ly.In this paper ,a new index structure is presented ,which takes full advantage of the latent rules about the suffix number and the order of string ,makes full use of the match information got in searching process ,consequently improves the searching efficiency.
K ey w ords :structured text
,index structure ,inverted files Class number :TP391.1
1 引言
一个良好的索引结构可以在被检索数据规模庞大的情况下保证检索操作的速度,是实现高效率检索的一个决定性因素[1]。常用的文本索引形式有三类,分别是倒排文件,后缀数组和签名文件。一个搜索引擎可以选用上述任何一种形式的索引结构,但其中应用范围最广的是倒排文件[2]。
本文在倒排文件的基础上,充分利用了字符前缀及字符串排列顺序在索引结构及查找过程中的特点,提出了一种支持高效检索的索引结构。
2 搜索引擎的总体框架
本文所描述的搜索引擎的系统框架如图1所
图1 搜索引擎的基本组成
示,主要包含以下几个主要功能模块:
(1)数据预处理,对数据进行预处理,形成一定格式的结构化文本文档。
(2)词语切分,对被检索文本进行切词处理,提取有独立意义的词语。
(3)索引建立,将切分后的词语及其相关信息提交给索引器,使其以一定格式保存在索引数据库中。 (4)查询预处理,调用词法分析器将查询表达式中的词语或模式分离出来,提交检索。
(5)检索,从索引数据库中获取匹配信息。(6)组合排序,对所有匹配信息进行组合和排序处理,实现词组查询、邻近查询或布尔查询等具体处理步骤,得到最终检索结果。
由上可知,索引数据库是整个搜索引擎框架的核心部分,索引器和检索器都是在此基础上工作的,它直接关系到整个搜索引擎的性能。下一节我们将详细介绍索引结构的设计。
3 索引结构的设计
对本文所述搜索引擎,为每个参加索引的文档
分派一个唯一的文档编号,将文本中所出现有独立意义的字符串称为项。我们将数据处理成为结构
①收到本文时间:2005年1月17日
化的文本文档[4],即按其格式自有的特征划分为若干非重叠的文本区域。如,对于邮件类型的数据,我们可将其划分为“发送者”,“接受者”,“日期”,“主题”,“信体”等几个信息域。在该检索模型中,存储在不同域中的同一个字符串代表的意义是不同的,因此每个项包括三个要点:一,包含项的文档所对应的文档号;二,项所在的域;三,词在某个文档某一域中出现的频率和位置信息[3]。
在该搜索引擎对应的检索模型中,我们将索引结构分作两个部分,分别存放为项索引文件和项信息文件。项信息文件用于记录每个项所对应的要点内容,以组织反馈结果;项索引文件用于快速定位项相关信息在索引中的存放位置。它们二者有着密切的联系。
3.1项信息文件
项信息文件存储了每个项对应的要点信息,在检索过程中,须对这些信息进行处理和加工,才能得到最终的检索结果。
我们将与域有关的信息存储在一个单独的域信息文件中,作为项信息的辅助描述。域信息文件(FieldInfoFile)的结构描述如下:
FieldInfo File→FieldNum,FieldNum
其中,FieldNum指域的个数,FieldName指域的名称,FieldWeight存放的是域权值,可作为衡量各个域重要性的客观依据之一,对结果排序起到辅助作用。
项信息文件(TermInfoFile)的具体结构描述如下:
TermInfo File→TermNum,TermNum TermInfo→FieldNum,FieldNum
DocInfo→DocNum,DocNum Location→Freq,Freq
其中,TermNum指所有项的个数,FieldNum 指包含该项的域的个数,DocNum指某个域包含该项的文档个数,DocSn指具体的文档号,Freq指该项在第DocSn个文档,第FieldSn个域中出现的频率,Offset指该项在域中出现的相对位置,第一个Offset表示该项相对于域内容的起始位置的偏移量,其后的Offset均表示相对于前一个出现位置的偏移量。
3.2项索引文件
项索引文件是整个索引文件的核心部分,检索过程实际上也就是对项的查找过程。要实现高效的搜索,主要与这个部分的存储结构有关。
在文本索引的范畴中,项是由字符串组成的,而字符串是由遵循ASCII、Unicode等各类编码规则的字符组成的,更进一步,项可被看作是由0和1组成的序列。我们可以指定一个长度n,将长度为n的01序列作为不可分割的原子单元。如,指定单元长度为4,则存在”0000”至”1111”共24个不同的原子单元。在该索引结构中,我们所有的字符串都看作是由2n种原子单元(n为原子单元位长度)构成的序列。
项索引文件(TermIndexFile)的具体结构描述如下:
TermIndexFile→TermCount TermIndexNode→
Suffix→String
PrefixLength→int
Next Hop,InfoAddr→int
TermCount指项索引文件中包含的项的个数。
项的内容由PrefixLength和Suffix两部分组成,其中PrefixLength表示与前一项具有相同的前缀的个数,Suffix用来表示剩余部分的字符串内容。举例来说,若我们将字母看作是原子单元,如果“god”的前一项为“goal”,则“god”的Pre2 fixLength值为2,Suffix值为“d”。
Next Hop用来指示与该项相同前缀数目为PrefixLength的下一项的位置。
InfoAddr指示与该项相关的内容在项信息文件中的起始地址。当某一项在项索引文件中查找成功后,通过该项InfoAddr即可获取项信息文件中与之对应的内容。
本文就字符串集合{00,0000,000000, 0001,000100,00010000,000101,00010100, 0010,0100,1000,100000,100001,10000100, 100010,100011,1001,11}作为项索引文件的示例内容。将其原子单元长度取为2,直观起见,我们以”a”替换”00”,以”b”替换”01”,以”c”替换”10”,以”d”替换”11”,字符串集合内容可表示为{ a,aa,aaa,ab,aba,abaa,abb,abba,ac,ba,ca, caa,cab,caba,cac,cad,cb,d}。
图2是上述字符串集合对应的项索引文件示例。项按字典序排列,圆中的数字是对应项的Pre2 fixLength值,上方除“-”字符以外的其它字符是该项对应Suffix域的内容,下方箭头所指地址即该项Next Hop域所存放的内容。
