《Introduce to IR》布尔检索模型

档案学中的信息检索模型与算法档案学是一门研究如何有效管理和利用各类档案信息的学科。

在信息时代的今天，随着信息量的爆炸式增长，如何快速准确地检索所需信息成为了档案学的重要研究方向之一。

信息检索模型与算法是档案学中的重要组成部分，它们通过建立一套系统性的理论框架和算法方法，帮助人们更好地获取和利用档案信息。

一、信息检索模型信息检索模型是信息检索系统的基础，它描述了信息检索过程中的各个环节和关键要素。

传统的信息检索模型主要包括布尔模型、向量空间模型和概率模型。

布尔模型是最早被提出的信息检索模型之一，它基于布尔代数的逻辑运算，将检索问题转化为逻辑表达式的求解。

布尔模型简单直观，适用于处理简单的检索问题，但对于复杂的检索需求，其表达能力较弱。

向量空间模型是一种基于向量空间理论的信息检索模型，它将文档和查询表示为向量，通过计算向量之间的相似度来判断文档的相关性。

向量空间模型具有较强的表达能力，能够处理复杂的检索需求，但在处理大规模数据时，计算量较大。

概率模型是一种基于概率统计的信息检索模型，它通过建立文档和查询之间的概率模型，计算文档的相关性概率。

概率模型考虑了文档和查询之间的语义关系，能够更准确地判断文档的相关性，但对于查询的理解和语义分析要求较高。

二、信息检索算法信息检索算法是实现信息检索模型的具体方法和技术。

常见的信息检索算法包括倒排索引、TF-IDF算法和PageRank算法。

倒排索引是一种常用的信息检索算法，它通过将文档中的关键词和对应的文档ID建立映射关系，快速定位包含关键词的文档。

倒排索引具有高效的检索速度和灵活的扩展性，是大规模信息检索系统的核心技术。

TF-IDF算法是一种用于衡量关键词在文档中重要性的算法，它通过计算关键词的词频和逆文档频率，得出关键词在文档中的权重。

TF-IDF算法能够准确地反映关键词的重要性，提高检索结果的准确性。

PageRank算法是一种用于评估网页重要性的算法，它通过分析网页之间的链接关系，计算网页的权重。

[信息检索]第⼀讲布尔检索BooleanRetrieval第⼀讲布尔检索Boolean Retrieval主要内容：1. 信息检索概述2. 倒排记录表3. 布尔查询处理⼀、信息检索概述什么是信息检索？Information Retrieval (IR) is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers).信息检索是从⼤规模⾮结构化数据（通常是⽂本）的集合（通常保存在计算机上）中找出满⾜⽤户信息需求的资料（通常是⽂档）的过程。

Document –⽂档Unstructured – ⾮结构化Information need –信息需求Collection—⽂档集、语料库⼆、倒排记录表1、什么是布尔查询？布尔查询是指利⽤ AND, OR 或者 NOT操作符将词项连接起来的查询如：信息 AND 检索2、⼀个信息检索的例⼦（莎⼠⽐亚全集）不到100万单词，假设每个英⽂单词平均长度为8字节，则整个全集不到10MB查询需求：莎⼠⽐亚的哪部剧本包含Brutus及Caesar但是不包含Calpurnia？查询的布尔表⽰：Brutus AND Caesar AND NOT Calpurnia解决⽅案：⽅法⼀：暴⼒⽅法从头到尾扫描所有剧本，对每部剧本判断它是否包含Brutus AND Caesar ，同时⼜不包含Calpurnia不⾜之处：速度超慢 (特别是⼤型⽂档集)处理NOT Calpurnia 并不容易（不到末尾不能停⽌判断）不太容易⽀持其他操作 (e.g., 寻找靠近countrymen的单词Romans)不⽀持检索结果的(灵活)排序 (排序时只返回较好的结果)优点：实现简单很容易⽀持⽂档动态变化⽅法⼆：倒排记录表词项-⽂档（term-doc）关联矩阵若某剧本包含某单词，则该位置为1，否则为0.关联矩阵的每⼀列(对应⼀篇⽂档)都是 0/1向量，每个0/1都对应⼀个词项关联矩阵的每⼀⾏(对应⼀个词项)也可以看成⼀个0/1向量，每个0/1代表该词项在相应⽂档中的出现与否给定查询Brutus AND Caesar AND NOT Calpurnia取出三个词项对应的⾏向量，并对Calpurnia 的⾏向量求反，最后按位进⾏与操作110100 AND 110111 AND 101111 = 100100.问题：当出现更⼤的⽂档集假定N = 1 百万篇⽂档(1M), 每篇有1000个词(1K)假定每个词平均有6个字节(包括空格和标点符号)，那么所有⽂档将约占6GB 空间.假定词汇表的⼤⼩(即词项个数) M = 500K此时，词项-⽂档矩阵将⾮常⼤矩阵⼤⼩为 500K x 1M=500G但是该矩阵中最多有10亿(1G)个1：词项-⽂档矩阵⾼度稀疏(sparse)更好的办法：仅仅记录1的位置，即倒排索引对每个词项t, 记录所有包含t的⽂档列表.每篇⽂档⽤⼀个唯⼀的 docID来表⽰，通常是正整数，如1,2,3…磁盘上，顺序存储⽅式⽐较好，便于快速读取内存中，采⽤链表或者可变长数组⽅式倒排记录表按docID排序索引构建过程：1、词条序列：<词条，docID>⼆元组2、排序按词项排序，然后每个词项按docID排序1. 词典&倒排记录表某个词项在单篇⽂档中的多次出现会被合并拆分成词典和倒排记录表两部分每个词项出现的⽂档数⽬(doc frequency, DF)会被加⼊3、布尔查询的处理假定索引已经构建好了，如何利⽤索引来处理查询？AND查询的处理：考虑如下查询（从简单的布尔表达式⼊⼿）:Brutus AND Caesar在词典中定位 Brutus返回对应倒排记录表(对应的docID)在词典中定位Caesar再返回对应倒排记录表合并(Merge)两个倒排记录表，即求交集合并过程：每个倒排记录表都有⼀个定位指针，两个指针同时从前往后扫描, 每次⽐较当前指针对应倒排记录，然后移动某个或两个指针。

《Introduce to IR》索引创建文章分类:互联网该系列文章是《An Introduce to Information Retrieval》Chapter 4 的读书笔记。

对于大规模数据的信息检索，倒排索引的建立其实并没有想象中的那么简单。

在实际应用中，倒排索引的建立算法必须考虑到硬件的约束。

可以这样说：计算机硬件的参数性能是促动IR系统的设计发展的决定因素。

索引创建(Index construction)要点：(1) 介绍BSBI 算法建立大规模数据的倒排索引(2) 分布式索引的建立算法4.1 硬件基础介绍下图是2007年典型计算机的系能参数：参数符号性能指标统计值s 磁盘数据定位时间5ms=5*10^(-3)s(在磁盘中查找数据所在的位置)b 每字节数据传输时间0.02us=2*10^(-8)s(从磁盘传入1字节数据进内存)CPU时钟周期10^(-9)sp 内存大小several GB磁盘大小1TB or more(1) 内存中读取数据远比磁盘中读取数据要快的多。

从内存中读取1byte数据只需要几个CPU时钟周期(大概5*10^(-9)s)，而从磁盘中读入1byte数据需要2*10^(-8)s。

因此，我们要尽可能的让更多的数据保存在内存中，特别是使用频率高的数据。

将使用频率高的磁盘数据保存在内存中的技术叫做缓存(caching)。

(2) 磁盘数据读取的代价主要花费在磁盘数据定位的时间上(5*10^(-3)s)。

而磁盘每次定位到一个磁盘存储块(详见《外部存储器——磁盘》)。

定位1byte数据和定位一个磁盘存储块(可能是8,16,32或64KB)的时间是一样。

因此，需要一起读取的数据块应该连续存储在磁盘上。

这样，我们把一整块磁盘存储块数据读入内存中的连续空间叫做缓冲区(buffer)。

举个例子：假设我们要读入磁盘中的10M数据，这些数据连续存储在100个磁盘存储块中。

那么所花费的时间代价：从磁盘中读入内存中的时间：t1=10^(7)*2*10^*(-8)=0.2s在磁盘中定位数据的时间：t2=100*(5*10^(-3))=0.5s总代价为: t=t1+t2=0.7s当然，如果10M数据分散存储在1W个存储块中(而且这些存储块分散在杂乱无章的磁道和柱面上)，那么可能要多付出几个数量级的t2代价。