主题：[推荐]《An Introduction to Information Retrieval》参考译文之二——布尔检索

1  布尔检索
1．1 信息检索
信息检索的概念非常宽泛，比如为了写信用卡号码而从钱包中找出信用卡的过程就是一个信息检索。但是作为一个学术性的定义，通常表述如下：信息检索就是从计算机中大量信息集合内找到满足信息需求的、无结构化的各种资料，如从大量文本文档中搜索所需文档。
按照这种定义，信息检索的参与者并不多，如图书馆员、律师助手和相似的职业检索者。但是随着世界的快速变化，成千上万的人们每天都要通过使用搜索引擎或者搜索邮件的方式参与到信息检索的实践中来。因此，信息检索已经快速成为当代信息获取活动（information access）的一种重要的形式，超过了传统的数据库检索形式
当然，信息检索除了包含它的核心定义所涵盖的内容外，它也覆盖了其他方面的数据处理和信息处理问题。术语“无结构化数据（unstructured data）”是指那些不具有内容繁杂、语义清晰和易于计算机处理等特点的数据。它和结构化数据（structured data）相反，结构化数据通常表现为关系型数据库中具有规范格式的数据，这些通常都是公司用于处理产品目录和人事记录的数据。在现实世界中，几乎没有什么数据能够是纯粹的无结构化数据，如考虑到人类语言中潜在的语义信息特征，所有的文本信息都是应该具有一定结构的信息。即便是假定所谓的结构化是指结构化较为明显，大多数文本信息仍然还是具有结构化特点，如具有标题、段落和脚注等，这些内容都会显式的在文档中被标注出来，如Web网页中可以使用不同的标记来标注网页中的不同成分内容。信息检索通常也被用于对半结构化数据（semistructured data）的搜索活动中，如搜索标题包含“Java”或者内容包含“线程”的相关文档。
信息检索领域还包含对用户浏览行为的支持、文档集合过滤和对被检索文档的进一步处理等。如给定一组文档，聚类就是一种基于内容的常见文档分组方法，它类似于按照书籍主题重新摆放书架上的书籍。再如，给定一组主题、信息需求或者其他的类目（如按照不同年龄划分的类别），分类行为就是一种将现有文档进行归类的常见方法。更为常见的方法就是首先使用人工方式对部分文档先行分组，然后利用计算机进行新增文档的自动归类。
信息检索还可以按照它所处理的数据规模分为三种不同类型。
1）Web搜索：Web信息检索系统需要能够对存储在Web网页上的海量信息资源进行检索。由于Web网络具有商业上的重要性，所以它所涉及的问题很多，如如何有效收集文档以进行索引处理，对大规模数据的处理具有缩放性，并且能够充分考虑Web网络的特点，如对超链关系的分析和防止通过恶意操纵网页内容来提升在搜索引擎中的排名等。
2）个人信息检索：在最近的几年中，个人操作系统陆续集成了很多内在的信息检索功能，如Apple机器Mac系统中的Spotlight和微软Vista系统中的即席搜索（Instant Search）。电子邮件系统通常不仅提供搜索功能而且还提供文本归类功能，这通常包含提供垃圾邮件（junk mail）的过滤功能，或者通过人工或自动的方式将邮件自动归类放置在特定的文件夹中。更有特色的内容还有对个人计算机上各种异质文档格式的广泛支持，同时使得信息检索系统的维护更为简单易行，不致于因为启动、运行和相关的存储消耗而增加所在计算机的用户使用负担。
3）企业搜索（机构搜索或者面向特定的搜索）：这种方式的特点介于上述两种形式特点之间，它所处理的文档多半都是企业内部的文件资源、专利数据或者研究文档等。在这种情况下，文档通常都存储于一台或多台中央文件系统中来给整个组织的所有用户提供服务。

1．2 信息检索的一个例子
很多人都拥有一本厚书《莎士比亚选集》。假设你想知道那部戏剧包含关键词“Brutus”和“Caesar”但是不包含“Calpurnia”，一种方法就是从头到尾的阅读一遍，标注满足上述条件的所有戏剧。作为计算机系统而言，这就是一种对文档的典型线形扫描过程，通常这种操作也被称为“grepping”，来自于Unix系统中用于处理线形扫描的grep命令。考虑到现代计算机的高速运算特点，这种扫描其实是很高效的，甚至可以使用一些含有通配符的正则表达式。使用现代计算机，查询诸如莎士比亚选集这样的文档是非常简单的。注意：莎士比亚选集全部的字数不大于100万个字符。
但是对于其他目标的查询而言，上述做法存在不足：
1）能够快速对海量文档集合进行查询处理，如Web网络上的网页文档数量规模是快速增长的，因此我们希望对10亿或者1万亿词语数量规模的文档集合能够进行快速检索。
2）能够使用更为灵活的匹配算法，如假设两个词语的间隔词语不超过5个，或者位于同一个句子中，我们称这两个词语是邻近的，那么使用grep命令并不能查询哪些文档中的“Romans”词语和“countrymen”词语具有邻近的关系。
3）能够对检索结果进行排序，在很多情况下，我们只想获取众多文档中包含所需关键词的一个最好文档。
为了避免对每个查询都进行线形扫描的操作过程，可以预先对文档进行索引。如上述例子，我们可以对每篇文档，即一篇莎士比亚的戏剧，标记其中所有莎士比亚使用词语的出现情况（莎士比亚大概只使用32000个不同的词语）。这个结果是一个二值的项文档发生矩阵（binary term-document incidence matrix），如图所示：

此主题相关图片如下：

其中，项是索引的基本单位，通常为词语，即便是一些很难看成是词语的项，在大多数情况下，都可以将其看成是一个词语，如“1－9”和“Hong Kong”。根据行和列的两个角度划分，可以得到不同的向量，一种是可以表示哪些文档出现了该词项的词向量，另一种是可以表示文档出现了哪些词项的文档向量。一般情况下，会对上述矩阵进行转置处理，以使得每个列向量都是词向量。
为了回答上述问题，只需直接取出三个词语所对应的词向量，对其进行数位布尔运算，结果为：
110100 AND 110111 AND 101111 = 100100
结果只有《Anthony and Cleopatra》和《Hamlet》，如：

此主题相关图片如下：

因此，布尔检索模型是一种可以利用布尔表达式表示查询要求和进行检索的信息检索模型。其中，查询关键词可以使用AND、OR和NOT操作符连接起来构成布尔表达式，这种查询将每篇文档都看成是一个词语集合。
为了介绍新的术语和记号，我们来考虑一下更为现实的场景。假设已有N篇文档，设N为100万，这里的文档是指用于检索的单元，它可能是一篇备忘录或者书的一章。文档的集合被称为“Collection“或者“Corpus”。假设每篇文档大概有1000个词语（2到3页的词语数）。考虑空格和标点符号，假设每个词语的平均字节数为6，则最终的文档集合大小大致为6GB。设这些文档所包含的不同词语个数为M，一般情况下M为50万。这里所涉及的一些数值并没有什么特别的含义，事实上它们即可能会发生量级的变化，不过由此我们可以清楚的发现所要处理的问题是一个规模非常巨大的问题。
最终的目标是要设计一个系统能够进行即席检索（ad hoc retrieval），这也是一种常见的查询方式。这样的系统要能够对用户的任意信息需求，利用用户构造的一次性查询，从已有的文档集合中找到命中结果。这里的信息需求（information need）是指用户想要知道的主题，它和事实的信息查询（information query）并非一回事，信息查询是用户利用计算机所提供的方式向计算机表达的信息需求（显然在现实中，这种映射往往是不准确的）。如果一篇文档包含用户所需的内容，则可以说它是相关的文档。应当说，上述例子显得有点不真实，因为信息需求只是通过特定的词语来体现的，事实上，如果用户希望得到“pipeline leak”的相关主题，那么含有“pipeline rupture”的文档也能算用户所要的文档。为了表达信息检索系统的有效性，即信息检索的质量，通常使用两个关键指标来测度系统返回的查询结果效果：一是精度（Precision），即返回结果中与用户真实信息需求相关的文档比重有多少，二是完整度（Recall），即文档集合中所有相关文档被返回的比重。
我们不可能按照直观的理解来构造项文档矩阵。一个500K×1M的矩阵至少含有5千亿个0或者1，这远远超过了计算机内存所能够存储的容量。而且，更为麻烦的是，这种矩阵非常稀疏，它所含有的非零项非常少。如果每篇文档有1000个词语，那么整个矩阵中1的元素数量不超过10亿个，也就是说，所有矩阵元素中至少有99.8％的元素都是0。显然，更好的处理方式应该是只标记词语的出现情况，也就是值为1的元素。
这种思想是信息检索当中第一个重要的概念，那就是倒排索引（inverted index）。事实上，这个名称是同义反复，索引当然是用来标注哪些项出现在哪些文档当中。但是，倒排索引和倒排文档已经成为信息检索中的标准术语，而且还形成了很多其他相关术语，如把所有项组成的结构称为字典（dictionary），所有的项组成的集合叫词表（vocabulary，lexicon）。每个项都有一个列表（list）用于标明它出现在哪些文档中，这个列表的每个元素（item）通常为项所在的偏移地址，被称为标记（posting），所以列表也被称为标记列表（posting list），或者倒排列表（inverted list），所有标记列表的组合被称为“postings”。注意：为了方便查找，字典中的所有项都按照字母次序排列，每个标记列表都按照文档ID号来排序。

1．3 倒排索引
为了加快信息检索的查询效率，必须首先构建索引。主要步骤为：
1）收集需要建立索引的文档。
2）对文本进行标识化（Tokenization），将每篇文档生成一个标识序列。
3）进行语义预处理，生成标准化的标识，这些标识是构建索引的基本元素。一般情况下，标识都是词语（word）。
4）按照标识在每篇文档中的出现情况建立倒排索引，这个索引由词语字典和标记组成。
为了处理方便，可以为每篇文档分配一个唯一的序列号，称之为文档标识符（document identifier），常常标记为docID，可以在构建索引时分配一个连续的整数给要处理文档的文档标识符。可以设想在构建索引时，需要输入一个列表，它的每个元素都是由标识和文档标识符组成的值对，在构建期间，最为重要的步骤就是按照标识字母顺序来对这个列表排序，而列表中的所有元素则按照文档标识符排列。同时，对于出现在同一文档中的相同标识需要合并，简单的做法只需保留一个以说明哪些文档出现了哪些标识即可，复杂的做法可能需要统计标识在同一文档中出现的频率等信息，以供以后检索使用。然后仍然要继续合并不同文档中出现的相同标识，形成的列表如下图所示：

此主题相关图片如下：

更为详细的处理过程和相关图例如下所示：

此主题相关图片如下：

注意，这里的每个标识都使用了文档频率这个统计指标，它反映了该词语出现的文档篇数。
在上图所述的数据结构中，一般情况下，字典都位于内存，而标记常常位于外存，主要原因在于标记通常远远大于字典。对于标记的每个元素而言，可以采用多种数据结构来存储。简单的方法是定长数组，显然浪费严重。更好的两个方法是单向链表（singly linked list）和变长数组（variable length array）。单向链表允许较快的节点插入操作，适应爬虫重新遍历的要求，而且还可以扩展以增加其他的功能。变长数组往往使用连续的空间来存储数据，所以可以极大的增加处理速度，而且无需存储额外的指针数据，因此空间更为节省，事实上，它是利用偏移地址来模拟指针的效果。如果更新操作不是很经常发生，则变长数组可以提供较高的存储性能和较快的访问速度。更为合理的方法可以结合两种方式，如整个列表的所有元素使用链表来存储，而每个元素则使用变长数组来存储全部相关文档标识符。另外，为了加快外存读取速度，通常会以压缩的方式连续存储在一个连续的外存区域上。

1．4 处理布尔查询
如何使用倒排索引来处理布尔查询呢？考虑下面的检索，如：
Brutus AND Calpurnia
可以将过程简单描述如下：
1）定位字典中的Brutus标识，并读取相关标记信息
2）定位字典中的Calpurnia标识，并读取相关标记信息
3）求两者的交集

此主题相关图片如下：

这里值得注意的是交集的求法，它必须是富有效率的算法。比较直观的方法可以采用归并排序算法类似的方法，归并计算两个标记列表所有元素。具体来看，在每一次取出一对列表元素值时，如果相等，则把这个代表文档标识符的元素值作为结果，并对列表元素继续移位；如果不相等，则只需移动指向较小文档标识符的列表元素。这个方法的算法运行时间和列表元素的多少呈现线形关系。算法如下：

此主题相关图片如下：

这也可以扩展到更为复杂的查询，如：
(Brutus OR Caesar) AND NOT Calpurnia
对于这些比较复杂的查询，查询优化是必不可少的，它是指能够以最少的工作代价来取得相同的运算结果。这里的问题就是判断哪个标记元素需要首先计算。如下面这个例子：
Brutus AND Caesar AND Calpurnia
对于每个元素都要取出相关的标记并对其进行AND计算。最为直观的做法就是按照词语的文档频率，首先处理文档频率低的标识，计算它们的标记列表运算结果，由于最终生成的结果列表元素个数不可能大于这两个标记列表中最小的元素数量，所以后续的比较处理将能够持续的获得最少的比较次数。假设按照前文的例子，这个查询应该优化为：
(Calpurnia AND Brutus) AND Caesar
这也说明在字典中存储相关标识文档频率的必要性，它允许我们通过内存数据的直接读取来引导下一步的行动。
对于更为复杂的例子，如最先提出的例子，还可以使用类似的方法，即首先估算每个查询单位项的文档频率，对于OR计算可以将相关标记文档频率相加来估算最终的查询单位项文档频率。
为了提高查询性能，系统还可以缓存很多查询单位项的中间计算结果，这即可能是因为查询语言的基本属性使然，有可能是因为这些查询单位项是较为常见的查询单位项。甚至可以事先对一些具有最小文档频率的相关标记列表进行计算并缓存其结果。
1．5 扩展布尔检索
和布尔检索不一样，等级检索（ranked retrieval）往往采用向量空间模型，适用于自由文本查询，也就是说，用户不使用非常精确的查询语言，而仅仅通过键入若干查询词语，系统以此来判断哪些文档最能符合用户要求，通常按照相关度的降序顺序排序输出命中文档结果，而布尔检索只能判断是或不是。尽管人们对等级检索研究颇多，但是在90年代以前的近30年中（这个时期就是在互联网出现以前），布尔检索一直是大型商业检索系统的主要提供方法。这些系统并非仅仅支持上述三种简单的布尔运算，所以它们大都实现了一些扩展的布尔检索功能，如引入邻近运算符（term proximity operator），这个运算符可以指定查询中的两个词语在文档中的邻近程度，如同在一个句子或者段落并且中间相隔的词语个数不能多于多少等等。