Signature File Index 签名文件索引

时间:2024-03-18 09:31:03



作为一种常用的索引组织方式,它在很多领域得到了应用。下面从存储和查询两个阶段对它进行介绍。

1.存储阶段
对于每个关键字,分配一个固定大小的向量(k-bit),这个向量叫做签名(Signature);对于一个网页文件,经过词典切分后,形成由对应 关键字序列构成的向量,即P=<key1,key2,…,keym>,对这些关键字的签名做OR运算,就形成了网页文件的签名。这个过程也被 称为重叠编码(Superimposed Coding),然后把网页文件的签名结果依次存入一个个独立的文件中,形成对应的签名文件,这样形成的签名文件比原文件小很多。
例如:有一页网页分词后有这样一些关键字“文本”、“英语”、“单词”、“信件”,假设将这些关键字经某哈希表散列成固定位的数字向量(以6位为 例),分别为hash(文本)=000110,hash(英语)= 110001,hash(单词)= 001101,hash(信件)=000111,这些数字向量即为关键字的签名,然后将这些签名做OR运算,得到网页文件的签名。

2.查询阶段
接受用户查询语句A,首先把用户查询串字符串切分成关键字序列,形成查询向量,即A=<key1,key2,…,keyn>。然后把关键字映射成相应的向量签名,再与网页签名文件进行按位与运算,得到最后的匹配结果。

3.优缺点
签名文件索引方式是一种比较有效的索引机制,文件组织简单,基本和原文件顺序一致;维护容易,生成、插入、删除都很方便;所需空间小,特别是采用重 叠编码之后;实现比较简单,更新比较容易;适合并行处理和分布式存储。但是签名向量的大小选择是一个需要研究的问题,而且对于大的文本文件,必须进行分块 处理,检索速度慢,需要顺序扫描。

Quelle: 王鹏,机械工业出版社,《移动搜索引擎原理与实践》,5.2.3 签名文件索引(Signature File Index)