搜索引擎的软件数据结构-Hit列表
Hit列表是指特定单词word在某个页面文档doc中每次出现时的出现状态
(occurrences)的列表，包括单词出现位置、字体大小和单词大写等信息。Hit存储
的信息对于搜索引擎的页面优先算法非常有用，往往决定着单词在页面文档中的重
要程度，因此对用户查询的相关度影响重大。例如:单词出现的位置，如果单词出
现在标题、或在头一段，以及保持适当的出现频次和平均间隔，往往表明单词较高
的重要性，反映出该页面文档具有较高的用户查询相关度。又如字头大小，在上下
文中字体相对较大的，单词重要性较高。注意字体大小是相对大小，因为通篇大字
体的页面文档不能表明其重要性超过通篇较小字头的页面文档。而西文单词的大写
也表明其较为重要。
Hits分 为 两类:普通hits和特殊hits。普通hits指出现在页面文档正文里面、或
者非特殊位置的hits。特殊hit包括出现在URL、标题、锚点的文本、或者meta标
签里的hits.
其存 储 方 式如下
普通hits指出现在页面文档正文里面、或者非特殊位置的hits.
包括 : 1 位 的 大 写 标志，3位的字体大小(相对于上下文的大小，范围
为 0- 6 ，而 7 代 表 特殊hits),1 2位的单词出现位置(如果大于12位，
即大 于 4 09 5后 的 位 置，标为特殊标志)
特殊hit包括出现在标题、锚点(URL)的文本、或者meta标签里的hits.
包括 : 1 位 的 大 写 标志，3位的字体大小(固定为7，代表特殊hits),
4位 的 类 型 ( 16 种 )，8位的单词出现位置(如果大于8位，即大于255
后的 位 置 ， 标 为 特 殊标志)
锚点hit实际上是特殊hit的一种，指锚点的文本。
包括 : 1 位 的大 写 标 志，3位的字体大小(固定为7，代表特殊hits),
4位 的 类 型 ( 固 定 为巧，代表锚点hit)1 S 位的出现位置拆分为两部
分， 4 位 表 示与 该 锚 点链接对应的页面文档DocID的Hash值，4位
表示 该 单 词 出 现 在 锚点文本内的位置(如果大于4位，即大于15后的
位 置 ，标 为 特 殊 标 志)。
锚点 hit s的意义和存储方式比较特殊，这里进行一个解释和说明。这里需要说
明的是，锚点文本内的单词实际上是与该锚点链接指向的页面文档具有较强的相关
性，而不是与锚点所在的页面文档存在较强的相关性。
这是 因 为 ，一方面，锚点文本所描述的是锚点链接指向的页面文档的说明性信
息，而不是其所在页面文档的信息;另一方面，当锚点所指向的是非文本页面文档，
如图片文件、音乐文件、软件等时，锚点文本所描述的信息对其指向的非文本页面
文档具有尤其重要的意义。因为对于非文本页面文档，搜索引擎不可能从其本身的
二进制数据中抽取有意义的单词和其他有用信息，只能通过指向这些非文本页面文
档的锚点文本或URL中的单词来提取关于该非文本页面文档的实际有用信息。所
以，锚点hits实际上表示了单词与锚点链接指向的页面文档的相关性。
因而 ， 锚 点hits需要记录的是锚点链接指向的页面文档标识号DocID，以及单
词在锚点文本中的位置。由于搜索引擎专门设有链接库(Link)，存储了页面文档之
间的链入和链出关系，以及链接相关的锚点文本，所以利用锚点hits所记录的信息，
借助链接库(Link)可以找到搜索引擎所需的全部信息。
链接库(Link)存储的页面文档链接信息示意图:
当然 由 于 锚点hits存储长度的限制，不能够完整记录锚点链接指向的页面文档
标识号DocID，只能计算并存储该页面文档标识号DocID的hash值。这样一来，
当搜索引擎需要还原该页面文档标识号DocID时，还要借助链接库(Link)完成。
工作流程如下:
工作流程示例图
1.锚点hits所在的页面文档标识号DocID，记为DocID1o 其链接指向的页面
文档标识号DocID的Hash值，记为Hashl。例如:Hash (DocID2) =Hashla
2. 在 链接 库(Link)中，查找链出DocIDl 所指向的所有链入页面文档标识号
DocID，分别计算其hash值。例如，Hash(DocID2)=Hash2, Hash(DocID3)=Hash3,
Hash(DocID4)=Hash4 a
如果 其 中 仅有一个与Hash1 相同，那么它就是需要还原的页面文档。例如，仅
有Hash2=Hashl，则DocID2就是需要还原的页面文档。否则，将所有与Hash 1相
同的DocID过滤出来，进行进一步查找。例如，假设Hash3=Hash2=Hashl，则将
DocID2, DocID3过滤出来。
3， 对 上 面过滤出来的每个页面DocID，执行以下操作:
a. 在 链 接库(Link)中找出链入DocID对应的锚点文本。
b. 根 据 锚点hits中记录的单词在锚点文本中的位置，在锚点文本中找到相应单
词 。如 果 锚 点 h it s所对应的单词与找到的单词相同，则说明该DocID就是
需要 还 原 的 页 面 文 档:否则，对下一个DocID进行同样的操作。例如:假
设锚 点 h its 所 对应的单词为“下载”，则DocID2对应的锚点文本“软件下载”
中能 够 在 锚 点 h its 记录的位置找到“下载”单词，而在DocID3对应的锚点
文本 “界 面 截 图”中不能在锚点hits记录的位置找到“下载”单词，所以
Do cID 2 就 是需 要还原的页面文档。
当然 ， 上 述算法存在一定不足。因为可能存在hash值相同的多个DoclD，而且
其锚点文本在相同的位置出现相同的单词。例如，如果上例中的
Hash(DocID2)=Hash(DocJD3),而DocID3的锚点文本为“截图下载”，那么DocID2
和DocID3就无法被准确地区分出来。从理论上讲，只有完整存储DocID而非存储
其hash值才能完全避免这种情况的发生，但是为了节省存储空间，必须进行采取折
衷的hash值存储方法。
下面 对 H it的存储方法设计的合理性进行解释和说明。
由于 H it s记录了一个单词在某个页面文档中每次出现时的出现状态，它是前向
和反向索引表中最主要的内容，占据了前向和反向索引表的绝大部分存储空间，因
此需要考虑有效的紧缩存储方式。而且，为了便于在索引表中快速定位，Hits存储
结构应该采取位长固定的方式。同时，它也是搜索引擎进行单词搜索和利用页面优
先算法进行决策最主要的依据，因此必须尽量保留有用信息。
所 以 hits 的存储既要体现尽量多紧缩存储空间的原则，又要体现尽量多保存有
用信息的原则。我们对hits采取2字节等长的数据结构设计，是充分考虑各种因素
后作出的合理折衷选择。
下 面对 折 衷的合理性进行说明。
I、 普通hits可记录的单词在页面文档中的出现位置最大在40% 个单词以
内。由于普通的Web页面单词总数超过这一数字的情况极少出现，所以这一数字能
够满足绝大多数页面的要求。而且，如果一个单词在某页面文档的4096个单词以内
均未出现，那么该单词与该页面可能存在相关性可以合理地加以忽略。
2、 特殊hits可记录的单词在页面文档中的出现位置最大在256个单词以
内。由于特殊hits记录的是页面标题、meta标签和该页面相关的说明性标注信息，
这些信息都出现在页面文档的最前面部分，而且占据的位置不多，因此这一数字能
够满足大多数网页的要求。对于在256个单词以后出现的页面说明性标注信息，可
以视为冗余信息而合理地加以忽略。
3. 锚点hits可记录的单词在锚点文本内的出现位置最大在16个单词以内。
这是由于在Web页面文档中，锚点文本通常较为简洁，单词总数目不多，最大16
个单词位置通常能够满足需要。
至 于最 大 16个hash值容量限制的问题，由于一个页面文档内所有锚点链出指
向的页面文档总数量有限，经过hash值计算后，因16个hash值容量限制造成的重
复hash值数量有限，通常能够满足检索及时响应时间的需要。