vc++编程实现基于倒排索引的信息检索.pdfVIP

～ ～～ ～～¨ 一一 一 一一一一 ～智 ～慧 一密 ～集 ～～～ ～一一一 一～实～ 用一 第一 兰．。．．．一，．．．． 一一一 一 Vc++编程实现基于倒排索引的信息检索 张研 摘要：介绍经典的信息检索方法——倒排索引，分析倒排索引的设计思路、数据结构勇L．Y-作原 理，并用VC++编程实现。 关键词：倒排索引：信息检索 供诸如词在文档中的位置等更多的信息。利用倒排索引。在信 1 引言 息检索时无需扫描整个文档集．而是对文档进行预处理，识别 信息检索(InformationRetrieval)是把信息按一定的方式出文档集中的每一个词。并为这些词构造索引表，通过索引表 组织起来．并根据用户的需要找出有关信息的过程和技术。例 中的索引词能够快速确定相关的文档．大大提高了检索效率。 如．熟悉的有哪些信誉好的足球投注网站引擎采用的就是信息检索技术，用户输入一个 212数据结构 或多个关键词．检索系统就会有哪些信誉好的足球投注网站出含有这些词语的文档的信 息。然而，随着计算机和网络技术的迅猛发展，当今社会的信 息量激增，这使得获取有用的信息资源变得越发困难，因此． 实现高效快捷的信息检索便显得尤为重要。下面介绍一种实用 的信息检索方法．并给出该方法的C++语言实现。 2倒排索引 2．1 方法概述 田2饲排索引的结构 倒排索引主要由索引表和倒排表两部分组成。索引表存 储供检索使用的索引词，倒排表用于存储与索引词对应的文档 的信息。首先看如何构造索引表，构造索引表需要识别出文档 中的每一个词，这就需要对文档进行词语的切分处理．由于英 文以单词为基本单元，分词较易实现，并且旨在讨论信息检索 固1倒排索引示意圉 技术而非分词技术，所以不妨以英文为例，实现英文文档的检 在实现信息检索的诸多技术中，倒排索引(Inverted index)因其性能优越得到比较广泛的应用。倒排索引指的是用 表．并采用“拉链法”解决冲突，使索引词在索引表中分布 户事先为信息建立索引表，这种索引表的每一项都包括一个词 尽可能均匀．最大限度地减少HASH碰撞。采用了一个高效的 语和包含该词语的文档的相关信息。由于该技术不是通过文档 来查找词语，而是通过词语来确定文档，因此称为倒排索引。 图1给出了倒排索引的示意图，图1中的Wordl到Wordn代 表n个索引词项．这i1个词项组成索引表，每个词项指向的逻 辑链表称为倒排表，倒排表记录了包含该词的文档标识符 这两个索引词在HASH数组中的人口地址。如图2所示。 (Docj)和词频(该词在文档Docj中出现的次数喝)，例如词HASH数组的指针Hash frfl】和Hashfn】分别指向两个结点。 语Wordi在文档D∞i中出现了蝎次，当然，倒排表也可以提这两个结点分别保存了两个单词的信息，为方便起见。称这类 万方数据