4.2.5 hit list hit list是一篇文档中所出现的词的列表，包括位置，字号，大小写。Hit list占很大空间，用在正向和反向索引中。因此，它的表示形式越有效越好。我们考虑了几种方案来编码位置，字号，大小写—简单编码（3个整型数），紧凑编码（支持优化分配比特位），哈夫曼编码。Hit的详细信息见图3。我们的紧凑编码每个hit用2字节。有两种类型hit，特殊hit和普通hit。特殊hit包含URL，标题，链接描述文字，meta tag。普通hit包含其它每件事。它包括大小写特征位，字号，12比特用于描述词在文档中的位置（所有超过4095的位置标记为4096）。字号采用相对于文档的其它部分的相对大小表示，占3比特(实际只用7个值，因为111标志是特殊hit)。特殊hit由大小写特征位，字号位为7表示它是特殊hit，用4比特表示特殊hit的类型，8比特表示位置。对于anchor hit八比特位置位分出4比特用来表示在anchor中的位置，4比特用于表明anchor出现的哈希表hash of the docID。短语查询是有限的，对某些词没有足够多的anchor。我们希望更新anchor hit的存储方式，以便解决地址位和docIDhash域位数不足的问题。 因为搜索时，你不会因为文档的字号比别的文档大而特殊对待它，所以采用相对字号。 hit表的长度存储在hit前。为节省空间hit表长度，在正向索引中和wordID结合在一起，在反向索引中和docID结合存储。这就限制它相应地只占8到5比特（用些技巧，可以从wordID中借8bit）如果大于这些比特所能表示的长度，用溢出码填充，其后两字节是真正的长度。 Figure 3. Forward and Reverse Indexes and the Lexicon
精品推荐