[科普中国]-通用信息索引

信息索引技术

经过网页预处理后，可以建立索引数据库。对于数目庞大的文档数据库使用简单匹配方法是不可行的，需要对文档的表示建立索引。为了提高检索效率，应该按照一定的规则建立索引。索引文件一般是按照倒排文件的格式存放的，通用的信息索引的建立包括：

(1) 分析：处理文件中可能的错误；

(2) 索引：完成分析的文件被编码存入索引数据库；

(3) 排序：将索引数据库按照一定的规则排序，产生全文索引。1

顺排索引技术顺排索引的主要思想是将文档中的每一条记录依次去匹配用户的检索提问集合，文档处理完毕后，将各提问的命中结果归并分发给有关用户。顺排索引是用文档中记录一条一条去匹配提问的，是顺序对文档记录检索的方法，所以也称为顺排文档检索。常用的顺排索引方法主要有：表展开法、逻辑树法等。

顺排索引的关键技术是采用列表(正派表)处理方法将提问逻辑式(检索式)变换成等价的提问展开式，按提问展开表的内容对顺排文档的每篇文献进行检索。

正排表是以文档的ID为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个文档中字的信息直到找出所有包含查询关键字的文档。正排表结构如图1所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护；因为索引是基于文档建立的，若是有新的文档加入，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。若是有文档删除，则直接找到该文档号文档对应的索引信息，将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。

倒排索引技术倒排文档是一种而向单词的索引机制，相对顺排文档而言，是将顺排文档中可检索字段的作者名、关健词、分类号等取出，按一定规则排序，归并相同词汇，并把在顺排文档中相关记录的记录号集合赋予其后，以保证通过某一特征词能够快速、方便地获取相关记录。图2是倒排索引的结构图。

倒排表以字或词为关键字进行索引，表中关键字所对应的记录表项记录了出现这个字或词的所有文档，一个表项就是一个字表段，它记录该文档的ID和字符在该文档中出现的位置情况。

由于每个字或词对应的文档数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排表。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，尽管效率相对低一些，但不会影响整个搜索引擎的效率。倒排表的结构图如图3所示。

倒排文档倒排文档的组成倒排文档的组成元素主要包括：关键字(作者、主题词、分类号等)、目长(含有该关键字记录的条数)、记录号集合(所有与该关键字有关的记录号)。

倒排文档的建立倒排文档的建立是建筑在顺排文档(主文档)的基础之上，它是从主文档中提取可检索字段内容，也有采取自动从标题、文摘或全文中提取关键词，利用所得到的这些属性词来建立倒排文档。

由顺排文档构造倒排文档需要经过抽词、排序、归并和组织等过程，具体实现步骤如下：

（1）选择需要做索引的字段属性(如作者、关键词等)，抽出其中的内容，并在其后附上其记录号；

（2）对抽出的内容进行排序，使之便于归并相同内容；

（3）对相同内容进行归并，把合并后的内容放入倒排文档的主键字段(如标引词、作者等)，统计每一数据的频次作为目长，把每一内容后的记录号顺序放在记录号集合字段。

通用信息索引的建立通用信息索引的构建相当于从正排表到倒排表的建立过程。主要的构建方法有简单法和合并法。

简单法当分析完网页时，得到的是以网页为主码的索引表。当索引建立完成后，应得到倒排表，流程描述如下：

（1）将文档分析称单词term标记；

（2）使用hash去重单词term；

（3）对单词生成倒排列表。

倒排列表就是文档编号DocID，没有包含其他的信息(如词频，单词位置等)，这就是简单的索引。

简单索引功能可以用于小数据，例如索引几千个文档。然而它有两点限制：

（1）需要有足够的内存来存储倒排表，对’J几搜索引擎来说，都是G级别数据，特别是当规模不断扩大时，难以提供这么多的内存。

（2）算法是顺序执行，不便于并行处理。

合并法（1）页面分析，生成临时倒排数据索引A、B，当临时倒排数据索引A,、B占满内存后，将内存索引A、 B写入临时文件生成临时倒排文件；

（2）对生成的多个临时倒排文件，执行多路归并，输出得到最终的倒排文件。

通用信息索引更新策略完全重建策略当新增文档到达一定数量，将新增文档和原先的老文档整合，然后利用静态索引创建方法对所有文档重建索引，新索引建立完成后老索引会被遗弃。此法代价高，但是主流商业搜索引擎一股是采用此方式来维护索引的更新。

再合并策略当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排表列表末尾追加倒排表列表项;一旦临时索引将指定内存消耗光，即进行一次索引合并，这里需要倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高排序，这样直接顺序扫描合井即可。其缺点是：因为要生成新的倒排索引文件，所以对老索引中的很多单词，尽管其在倒排列表并未发生任何变化，也需要将其从老索引中取出来并写入新索引中，这样对磁盘消耗是没必要的。

原地更新策略试图改进再合并策略，在原地合并倒排表，这需要提前分配一定的空间给未来插入，如果提前分配的空间l不够了需要迁移。

混合策略能够结合不同索引更新策略的长处，将不同索引更新策略混合，以形成更高效的方法。1