当前位置：文档之家 › 《Introduce to IR》布尔检索模型

《Introduce to IR》布尔检索模型

  • 格式：doc
  • 大小：127.50 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

【企业导师】布尔检索模型&索引构建

【企业导师】布尔检索模型&索引构建

储存开销计算
如何快速构建索引?快速定位词项。 如何减少存储开销?
布尔查询的处理 假定索引已经构建好 1. 如何利用该索引来处理查询? 2. 如何处理不同类型的查询? 比如带通配符的查询 “信息*检索” AND查询的处理 考虑如下查询（从简单的布尔表达式入手）: Brutus AND Caesar 在词典中定位 Brutus 返回对应倒排记录表(对应的docID) 在词典中定位Caesar 再返回对应倒排记录表 合并(Merge)两个倒排记录表，即求交集，这步操作很关键
非结构化数据(文本) vs. 结构化数据(数据库)
@2009年
@1996年 传统信息检索主要关注非结构化、半结构化数据 现代信息检索中也处理结构化数据
信息检索 处理数据的规模 • Web搜索，需要处理数百亿的文档
如何采集到这种规模的文档？ 如何在这种大规模数据量的情况下建立高效运行的系统？ 如何应对Web 特性所带来的特殊问题，比如SEO？
布尔检索的缺点
布尔查询构建复杂，不适合普通用户。构建不当，检索结果过多或者过少 没有充分利用词项的频率信息 1 vs. 0 次出现 2 vs. 1次出现 3 vs. 2次出现, … 通常出现的越多越好，需要利用词项在文档中的词项频率(term frequency, tf)信息 不能对检索结果进行排序
搜索引擎系统与应用 索引构建
提纲 1. 简介 2. BSBI算法 3. SPIMI算法 4. 分布式索引构建 5. 动态索引构建
简介
布尔检索的优点
构建简单，或许是构建IR系统的一种最简单方式 在30多年中是最主要的检索工具 当前许多搜索系统仍然使用布尔检索模型: 电子邮件、文献编目、Mac OS X Spotlight工具

档案学中的信息检索模型与算法

档案学中的信息检索模型与算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

布尔检索模型

布尔检索模型
• 当两篇文档需要比较时，最好的情况就是所有的 特征均不同，结果为0，此时的相异度就为1。 当有 k（比如设k为0.2）以上特征不同时，则判 定两篇文档为非相似文档；如有0.2 以下的特征 不同，则需要计算这些不同特征总的频度(Tf)。 表2为文档D1和D2相异度的计算实例。
表二 D1和D2相异度的计算
布尔检索模型
XXXX
布尔检索模型
• 概述
布尔检索法是指利用布尔运算符连接各个检索词，然后由计 算机进行逻辑运算，找出所需信息的一种检索方法。 • 设文本集D中某一文本i, 则该文本可表示为: 其中 设另一用户检索表达式为 Q j (t1 t 2) (t 3 t 4) 对于该检索式，系统响应并输出的一组文本应为:它们都含 有标引词 t 1 和 t 2 或者含有标引词 t 3 和 t 4 。
▲其中id代表特征的唯一表示，Doic表示出现了该特
征的文档的唯一标识符。当两篇文档相互比较而相异 结果为1时，就将它们分别插入它们之间不同的特征 链表中；否则，插入相同特征链表中。 ▲当再有新的文档需要比较时，根据该文档中出现的 特征，选择应该与它相同的集合，以减少比较次数。
布尔模型在网页查重中的应用
• 使用这种算法的优点：
• 由于一些词在所有文档中都大量出现，这些词将 不会作为文档的特征值，可以忽略大量常用停用 词的影响，如in，and，the等，这样读取文档时 就不需要特别过滤常用词，节约了处理文档和提 取特征的时间。 • 特征值的比较结果只有1和0两种状态，节约资源 ，易于实现。
布尔模型在网页查重中的应用 相异度的计算:
布尔算符
• 运算符之间的优先级： NOT > AND > OR，如检索表达式：雪花 NOT 啤酒 AND 歌曲 OR 小说，搜索结果为：名字叫 《雪花》的歌曲或者小说。 • 利用小括号（）可以设置出个性化的检索方程。 例如检索出不包含日本在内的有关教育或法律方 面的信息： （university OR college） AND （ education OR Law ）NOT Japan

信息检索模型

信息检索模型
countries =&grest 组合词: 北京大学 中文切词（word segmentation），或称分词，主要在中文信息处理中使用，即把一句话 分成一个词的序列。如，“网络与分布式系统实验室”，分词为“网络 与 分布式 系 统 实验室”。
2．依据共有词汇假设的信息检索
存在共有：如果 dj 有 q 含有的某些 ki , 则 relevant(q, dj )=1 全部共有：如果 dj 有 q 含有的所有的 ki , 则 relevant(q, dj )=1 比例共有：如果 q 和 dj 共有多于 m%的 ki , 则 relevant(q, dj)=1
sim(d j , q)
=
⎧1 ⎨ ⎩0
if ∃qcc | (qcc otherwise
∈ qdnf
) ∧ (∀ki , gi (d j )
=
gi (qcc ))
如果 sim(d j , q) = 1，则表示文献 dj 与 q 相关，否则为不相关。
sim(dj, q) 为该模型的匹配函数。
3．简单实例：
一、 布尔检索模型 这是一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上。 遵循两条基本规则: 1）。每个索引词在一篇文档中只有两种状态：出现或不
出现，对应权值为 0 或 1。2）。查询是由三种布尔逻辑运算符 and, or, not 连接 索引词组成的布尔表达式。
1．可以将查询转化为一个主析取范式 DNF。
五、现代信息检索包括的主要内容
DB Manager Module
Text Databas
建模、文献分类、系统构建、用户界面、数据可视化、信息过滤和查询语言 等。
第二节 信息检索模型 一、相关概念
停用词（stop word），指文档中出现的连词，介词，冠词等并无太大意义词。例如在英 文中常用的停用词有 the，a, it 等；在中文中常见的有“是”，“的”，“地”等。 索引词（标引词，关键祠）:可以用于指代文档内容的预选词语,一般为名词或名词词组. 词干提取:

[信息检索]第一讲布尔检索BooleanRetrieval

[信息检索]第一讲布尔检索BooleanRetrieval

[信息检索]第⼀讲布尔检索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)两个倒排记录表，即求交集合并过程：每个倒排记录表都有⼀个定位指针，两个指针同时从前往后扫描, 每次⽐较当前指针对应倒排记录，然后移动某个或两个指针。

信息检索模型

信息检索模型

例子：
q = 病毒 AND （计算机 OR 电脑）AND NOT医 d1: …据报道，计算机病毒近日猖獗… d2: …小王虽然是学医的，但对研究电脑病毒也很感兴趣，最近 发明了一种… d3: …计算机程序发现了爱滋病病毒的传播途径… 哪些文档会被检索出来？
布尔模型的优点
到目前为止，布尔模型是最常用的检索模型， 因为：
信息检索模型
信息检索模型是指如何对查询和文档进行表示，然 后对它们进行相似度计算的框架和方法。 本质上是对相关度建模。 信息检索模型是IR中的核心内容之一。
信息检索模型
一个信息检索模型是由文档表示、查询、关 系、模型框架构成的四元组。 四元组：System=(D,Q,F,R(dj,qi)) D 文档集的表示 Q 用户需求的表示 F 文档表示、查询表示和他们之间关系的 模型框架（Frame） R(dj ，qi) 给出Query qi和Document dj 的评 分
1
Sim(dj,q)=
如果存在qcc|(qcc∈qdnf)且对于任意ki, 有
gi(dj) = gi(qcc)
0 其他 例如: 文档集合D存在两篇文档d1和d2,其中,d1含有关键 词k1和k2,d2含有关键词k1和k3,则它们的文档向量分别为: d1 =(1,1,0) , d2 =(1,0,1) 根据匹配函数的定义,显然,d1与提问式q = k1 and （k2 or not k3）的匹配函数值是1,即d1与提问q是相关的; d2与 提问式q的匹配函数值是0, 表明d2与提问q是不相关的。
信息检索模型
内容提要
信息检索系统的形式化表示 布尔逻辑模型 向量空间模型 概率模型 其他检索模型
什么是模型？
模型是采用数学工具，对现实世界某种事物 或某种运动的抽象描述 面对相同的输入，模型的输出应能够无限地 逼近现实世界的输出

第二章(1) 信息检索模型

第二章(1) 信息检索模型

布尔模型描述




文档D表示 一个文档被表示为索引项(关键词)的集合 查询项Q表示 查询项被表示为索引项的布尔组合，用“与、或、 非”连接起来，并用括弧指示优先次序 框架F 一个文档当且仅当它能够满足布尔查询式时，才将 其检索出来 检索策略基于二值判定标准 算法R 根据匹配框架F判定某一文档与查询是否相关，如 果相关，则返回该文档
优点

到目前为止，布尔模型是最常用的检索模型，因 为：

由于查询简单，因此容易理解 通过使用复杂的布尔表达式，可以很方便地控制查询 结果 相当于识别包含了一个某个特定term的文档

相当有效的实现方法


经过某种训练的用户可以容易地写出布尔查询式
问题

布尔模型被认为是功能最弱的方式

其主要问题在于不支持部分匹配，而完全匹配会导致太多或 者太少的结果文档被返回
什么是模型？


模型是采用数学工具，对现实世界某种 事物或某种运动的抽象描述 面对相同的输入，模型的输出应能够无 限地逼近现实世界的输出

举例：天气的预测模型
针对用户输入的查询，如何将文档按相关性 进行排序 如何看待文档是否与用户的查询相关

信息检索模型要解决的问题


信息检索的预备知识


方法1:对长文档进行惩罚,对短文档进行补偿 方法2:对长度进行归一化处理
由索引项构成向量空间

2个索引项构成一个二维空间，一个文档可能 包含0, 1 或2个索引项



类似的，3个索引项构成一个三维空间，n个索 引项构成n维空间 一个文档或查询式可以表示由n个元素组成的 向量

《Introduce to IR》索引创建

《Introduce to IR》索引创建

《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代价。

《信息检索模型》课件

《信息检索模型》课件

向量空间模型
向量空间模型使用向量表示文档和查询，通过计算余弦相似度来衡量文档与查询的相关性。它能够更全面地度 量文档的相关性，但需要处理高维度的向量空间。
概率检索模型
概率检索模型基于统计方法，通过建模查询与文档的概率分布来进行信息检 索。其中，BM25算法是常用的概率检索模型算法之一。
实践应用
信息检索系统由多个组成部分构成，包括文本预处理、索引构建、查询解析 和结果排序等，这些组件协同工作以提供准确和相关的搜索结果。
信息检索模型
信息检索模型是用于描述和处理信息检索过程中的相关原理和算法。常见的 模型包括布尔模型、向量空间模型和概率检索模型。
布尔模型
布尔模型使用布尔运算符进行查询匹配，根据查询关键词的逻辑关系确定文 档是否与查询匹配。它简单而直观，但缺乏对文档相关性的度量。
《信息检索模型》PPT课 件
欢迎来到本课程关于《信息检索模型》的PPT课件。本课程将带您深入了解信 息检索的不同模型、系统以及实践应用，让您对这一领域有全面的认识。
信息检索概述
信息检索是指通过计算机系统从大量的信息资源中找到用户所需信息的过程。ห้องสมุดไป่ตู้具有悠久的历史并在诸多领域 得到广泛应用。
信息检索系统
信息检索在多个领域有着广泛的实践应用，包括搜索引擎、文本分类、推荐系统等。下面我们将通过案例分析 搜索引擎的信息检索模型。
总结与展望
信息检索领域持续发展，未来的趋势包括个性化搜索、多模态检索和语义搜索等。信息检索的进步将对我们的 生活和工作产生深远影响。

现代信息检索第3章-IR模型(再次再次修正版)

现代信息检索第3章-IR模型(再次再次修正版)

中国科学院研究生院课程2006
向量空间模型(3)
权重计算(1)
Term的频率TF：Term在文档中出现的次数，TF 越高权重越高。TF取0或1称为布尔权重。 TF的归一化：将一篇文档中所有Term的TF值归 一化到[0,1]之间。 通常可以采用以下三种方式之一：
Maximum Normalization
i i
d •q Jaccard: Sim( d , q ) = = 2 2 || d || + || q || − d • q
∑ (a * b ) ∑ a + ∑ b − ∑ (a
i i i 2 2 i i i i i
i
* bi )
中国科学院研究生院课程2006
向量空间模型(8)
向量空间模型经过不断发展，也提出了 很多公式，下面是一个最常用的公式：
布尔模型(1) 基于模糊集的模型(3) 扩展布尔模型(4)
基于代数论的IR模型(Algebraic models)
向量空间模型(2) 潜性语义索引模型 (5)
基于概率统计的IR模型(Probabilistic models)
回归模型(6) 二元独立概率模型(7) 语言模型建模IR模型(8)
中国科学院研究生院课程2006
普通集合和模糊集合
普通集合论
对于论域U上的一个子集A，可以定义函数：
χ A ( x) = ⎨
⎧1, if x ∈ A , 即χ A: U → {0,1} 0, if x ∉ A ⎩
该函数刻画了论域U上的元素x到A的隶属度，当隶属度为1时， x属 于A，当隶属度为0时，x不属于A，该函数是二值函数 例子：“大于1的实数”用集合表示为 A={x|x>1, x∈R}

信息检索的三个经典模型

信息检索的三个经典模型

信息检索的三个经典模型
1. 布尔模型
布尔模型是最简单和最早的信息检索模型之一。

它基于布尔逻辑，并
使用逻辑运算符（如AND、OR和NOT）组合查询词来匹配文档集合。

在这种模型中，文档要么与查询匹配（1），要么不匹配（0），没有其
他评分标准。

布尔模型适用于处理简单的查询和需求明确的场景，特
别是在较小的文档集合中。

2. 向量空间模型
向量空间模型是一种常用的信息检索模型，根据向量表示文档和查询，并计算它们之间的相似度进行排序。

在这种模型中，将文档和查询表
示为权重向量，每个维度表示一个词项，并使用词频、逆文档频率等
权重策略进行建模。

通过计算文档与查询之间的余弦相似度，可以衡
量它们的相关性并进行排序。

向量空间模型适用于大规模的文档集合
和较复杂的查询需求。

3. 概率检索模型
概率检索模型基于概率统计理论，对文档与查询之间的概率关系进行
建模和计算。

最典型的概率检索模型是基于贝叶斯理论的朴素贝叶斯
模型。

该模型假设文档生成过程是随机的，并使用贝叶斯公式计算查
询的后验概率。

通过比较不同文档的概率得分，可以将其排序。

概率
检索模型适用于处理较复杂的查询和在语义理解方面有一定要求的场景。

信息检索布尔逻辑检索

信息检索布尔逻辑检索

信息检索布尔逻辑检索1 前言随着互联网信息量的不断增长，如何高效地获取所需信息成为了人们关注的焦点。

信息检索技术应运而生，为用户提供便捷、快速的信息检索服务。

本文主要介绍信息检索中的布尔逻辑检索，为读者深入了解该技术提供帮助。

2 什么是布尔逻辑检索布尔逻辑检索，又称为布尔代数检索，是信息检索中最基本的检索模型之一。

其运用布尔代数中的符号和运算符来表示文档集合中的文档关系，通过运算符组合检索表达式，最终返回符合检索表达式的文档集合。

常用的布尔运算符有与（&）、或（|）、非（!）三种。

其中，“与”运算符表示在多个检索词的情况下，只有同时满足多个检索词的文档才会被检索出来；“或”运算符表示满足其中一个检索词的文档都会被检索出来；“非”运算符用于过滤掉指定检索词的文档。

3 布尔逻辑检索的优缺点优点：（1）可简单地组合多个检索词进行检索，精确度高。

（2）布尔逻辑运算符简单明了，易于理解。

（3）在大规模数据中的检索可以非常快速地进行。

缺点：（1）对用户的搜索语句要求较高，需要了解检索词之间的关系，具有一定的技术门槛。

（2）只能匹配精确词语，无法识别同义词和相关词。

（3）难以处理不同的文档属性，不适用于复杂文档类型的检索。

4 如何应用布尔逻辑检索使用布尔逻辑检索进行信息检索，需要以下步骤：（1）确定检索关键字检索者需要根据所需信息的特点，确定准确的检索关键字。

在选择关键字时，应遵循具有代表性的词语，关键性、意义明确的原则。

（2）确定布尔逻辑运算符根据检索关键字之间的逻辑关系，选择适当的布尔逻辑运算符进行运算组合，形成检索表达式。

（3）筛选搜索结果在检索结束后，检索系统会返回符合检索表达式的内容。

检索者需要对检索结果进行筛选，将符合自己需求的信息从中筛选出来。

5 结论布尔逻辑检索技术虽然在应用过程中存在一些缺点，但是其简单明了的检索方式和高效的检索速度，仍然是信息检索领域不可替代的技术之一。

在实际应用过程中，大家可以针对具体情况来选择使用布尔逻辑检索技术，以提高信息检索效率。

一般信息检索的方法

一般信息检索的方法

一般信息检索的方法信息检索（Information Retrieval，简称IR）是指根据用户的信息需求，从大规模的信息库或文档集合中找到与需求最匹配的文档或信息。

1. 关键词检索（Keyword Search）关键词检索是最常见的信息检索方法之一、用户通过输入关键词来描述信息需求，检索系统将根据关键词匹配文档库中的文档，并返回与关键词相关的文档列表。

该方法简单直接，用户能够根据自己的需求灵活选择关键词，但是可能会遇到词义多义性、歧义性以及检索结果质量不高等问题。

2. 布尔逻辑检索（Boolean Logic）布尔逻辑检索是一种基于布尔运算的信息检索方法。

用户可以使用AND、OR和NOT等逻辑操作符来组合多个关键词，以获取更精确的检索结果。

布尔逻辑检索能够减少检索结果的数量，提高检索效率，但是对用户的检索能力要求较高，且不适用于表达复杂的查询需求。

3. 向量空间模型（Vector Space Model，VSM）向量空间模型是一种将文档和查询表示为向量的信息检索方法。

该模型通过计算文档和查询之间的相似度来确定最匹配的文档。

每个文档和查询向量中的每个维度代表一个相关的特征，如词频、权重或其他统计量。

向量空间模型能够考虑词语在文档中的重要性，较好地适应了用户的信息需求。

4. 概率检索模型（Probabilistic Retrieval Model）概率检索模型是基于概率论的信息检索方法。

常见的概率检索模型包括布尔模型、向量空间模型以及概率商模型等。

这些模型通过计算检索结果的概率，从而评估文档的相关性。

5. 自然语言处理（Natural Language Processing，NLP）自然语言处理是一种结合语言学和计算机科学的方法，用于处理和理解自然语言的方式。

在信息检索中，自然语言处理技术可以用于理解用户的查询意图、整理和处理文档内容，并进行语义分析和文本挖掘等操作，从而提高检索的准确性和效率。

推荐系统是一种基于用户个性化需求的信息检索方法。

信息检索模型

信息检索模型

信息科学技术学院 网络研究所
布尔检索模型
首先，将查询转化为一个主析取范式DNF 首先，将查询转化为一个主析取范式DNF 例如：查询为 q = k ∧ (k ∨ k ) 进一步表达为 q = (1,1,1) ∨ (1,1, 0) ∨ (1, 0, 0) 即：每一个分量都是三元组 Ka ( k a , k b , k c ) 的二值向量 (1,1,0)
实例： 实例：搜索引擎
搜索引擎（ 搜索引擎（search engine，SE），Web上的一种应 engine，SE） Web上的一种应 用软件系统， 它以一定的策略在Web 上搜集和发 用软件系统 ， 它以一定的策略在 Web上搜集和发 现信息， 对信息进行处理和组织后 ， 现信息 ， 对信息进行处理和组织后， 为用户提供 Web信息查询服务 Web信息查询服务 搜索引擎三段式工作流程
信息科学技术学院 网络研究所
信息检索模型
信息检索模型（ 信息检索模型（IR model），依照用户查询， model） 依照用户查询， 对文档集合进行相关排序的一组前提假设和 算法。IR模型可形式地表示为一个四元组 算法。IR模型可形式地表示为一个四元组 < D, Q, F, R(qi,dj) > 其中D是一个文档集合， 是一个查询集合， 其中D是一个文档集合，Q是一个查询集合， F 是一个对文档和查询建模的框架 ， R(qi,dj) 是一个对文档和查询建模的框架， 是一个排序函数，它给查询q 是一个排序函数，它给查询qi和文档 dj 之间 的相关度赋予一个排序值
信息科学技术学院 网络研究所
信息检索模型
结构化模型：非重叠链表模型、 结构化模型：非重叠链表模型 、 临近节点 模型 浏 览 型 数 学 模 型 ： 平 面 (Flat) 、 结 构 导 航 (Structure Guided)、超文本(Hypertext) Guided)、超文本(Hypertext)

信息检索模型

信息检索模型

概率模型
基本假设前提和理论 a．相关性独立原则。文献对一个检索式的相关性与文献集合 中的其他文献是独立的。 b．词的独立性。标引词和检索式中词与词之间是相互独立。 c．文献相关性是二值的，即只有相关和不相关两种。 d．概率排序原则。该原则认为，检索系统应将文档按照与查 询的概率相关性的大小排序，那么排在最前面的是最有可能 被获取的文档 e．贝叶斯(Bayes)定理，用公式表示为： P(R I d)=(d I R)· P(R)/P(d)
布尔模型（Boolean Model）
布尔模型：查询和文档均表示为标引词(“是否存 在”) 的布尔表达式，通常表示成D(t 1，t 2，⋯ ，t i)的形 式。 布尔操作(关系) :与(AND) 或(OR) 非(NOT) 相似度计算：查询布尔表达式和所有文档的布尔表 达式进行匹配，匹配成功的文档的得分为1，否则 为0。 类似于传统数据库检索，是精确匹配
权重计算


标引词的文档频率DF（Document Frequency）：标引词在 整个文档集合中出现的文档篇数，DF反映了标引词的区分 度， DF越高表示标引词越普遍，因此其区分度越低，其权 重也越低。 逆文档频率（Inverse DF ，IDF）DF的倒数，通常采用如下 公式计算：（N是文档集合中所有文档的数目）

布尔模型的优点
简单、易理解、易实现 现代很多搜索引擎中仍然包含布尔模型的思 想，如Google的高级检索

布尔模型的局限性



只能严格匹配，文献要么相关、要么不相关，并没有一个相 关级别的概念，因此很难有好的检索效果 构造布尔逻辑式不容易，对于一般用户而言，很难用AND、 OR、NOT运算符的结合来准确地表达一个检索语句，标引 词的简单组配不能完全反映用户的实际需要； 检索输出完全依赖于布尔提问与文献的匹配情况，很难控制 输出量的大小 结果不能按用户定义的重要性排序输出，用户只能从头到尾 浏览输出结果才能知道哪些文献更适合自己的需要

第四章 信息检索模型

第四章 信息检索模型

匹配计算函数R(di, q)
R(di, q)→文档与用户查询之间相关度计算函数 匹配函数R(di, q)用于计算任一信息di（di∈D）与 任一提问q（q∈Q）形成的信息—提问对（di，q） 之间的相似度大小。一般地， R(di, q)的函数值为 一实数，其取值区间为[0，1] 匹配函数的特点： 计算方法简单，计算量小； 函数值在取值区间均匀分布； 针对某一提问所获取的相关文档集合，能够实 现合理的排序输出。
相关概念
合取范式：若干个互不相同的合取项的析
取称为一个合取范式 例：
析取范式：在布尔逻辑中，析取范式(DNF)
是逻辑公式的标准化（或规范化），它是 合取子句的析取。
布尔提问的析取范式
根据布尔逻辑的运算规定，提问式q可以被表示成由合取 子项（conjunctive components）组成的析取范式 （disjunctive normal form,简称dnf）形式。 如：提问式 q = k1 and （k2 or not k3）可写成等价的析取 范式形式： q dnf = (k1 and k2 and k3) or (k1 and k2 and not k3) or (k1 and not k2 and not k3 ) 这里q dnf是提问式q的主析取范式。可进一步简化表示 为： q dnf =(1,1,1) or (1,1,0) or (1,0,0) 其中： (1,1,1) or (1,1,0) or (1,0,0)是q dnf的三个合取子项 qcc，他们是一组向量，由对应的三元组(k1 , k2 , k3)的每一 个分量取0或1得到。
信息检索模型概述
本质上是对相关度建模。 信息检索模型是IR中的核心内容之一。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

《Introduce to IR》布尔检索模型
文章分类:互联网
该系列文章是《An Introduce to Information Retrieval》Chapter 1 的读书笔记。

IR的概念很广泛，即使从钱包中拿出一张信用卡并输入卡号也是一种形式的信息检索。

在学术领域，我们这样定义IR：
信息检索(IR)就是一种从大量数据集合中(通常指存储在计算机中文档)寻找满足信息需求的非结构化(通常指文本)得数据(通常指文档)。

布尔检索模型(Boolean Retrieval)
要点：(1) 倒排/反向索引模型inverted indexes
(2) 简单的布尔表达式如何处理这些索引
1.1 词—文档的关联矩阵索引 a term-document matrix
(1) Unix/Linux grep- 命令
这个命令或许大家都用过，它是Unix/Linux中用于在指定文件中查找特定的搜索字符串的命令。

它的原理是利用正则表达式在文档集合中进行线性顺序扫描(sort of linear scan)。

这种方式对于现代计算机的运行速度而言，在有限的数据规模下做简单的查询足够应付了。

(2) Web data 的搜索面临的现实问题
▲ 网络在线数据量(web data/online data)巨大，其增长的速度远大于计算机的硬件发展速度。

如何快速的检索需要查询的内容？这一点线性顺序扫描时永远做不到的。

▲ web搜索面临的是广大用户群，其查询表达式的方式灵活多样(并不一定是布尔表达式)。

甚至有的时候并没有准确的查询含义。

比如查询query：Romans NEAR courtyman。

这里的NEAR到底是指Romans，courtyman 这两词需要在文章中同一个句子里出现，还是相隔若干词。

如何更好的响应用户的灵活多变的查询方法，提供更加人性化得服务呢？
▲ 检索结果的排序问题也是一个现实问题。

用户需要看到的是最满意的答案，那么查询返回的若干文档，到底哪些与用户查询最相关呢？
(3)布尔模型的词—文档关联矩阵索引模型
线性顺序扫面对于web data来说是不可能的。

目前，解决高效检索大量非结构化的信息的公认最好手段就是建立索引(indexes)。

下面就是一个简单的索引模型——关联矩阵。

1. 词—文档关联矩阵如下图，列表示文档，行表示文档中的词。

其中如果Term1出现在Doc1中，则矩阵(1,1)标示为1，否则为0。

2. 建立布尔查询表达式(boolean query)。

Antony and Brutus not Caesar 也就是我们需要找到包含Antony ,Brutus同时不包含Caesar 词语的文档。

3. 使用位运算: Antony and Brutus not Caesar = 110001 & 110100 & (~110111) =000000. 很可惜，一篇都没有。

(4) 关联矩阵模型的缺陷
上面这个简单索引模型并不适合Web data的检索。

对于大数据量而言，这个矩阵实在是太大了，不可能全部放进内存。

而且更严重的是矩阵太稀疏了。

况且对于检索结果的排序问题也是解决不了的。

1.2 倒排索引inverted index
倒排索引绝对是一个伟大的发现。

当前很多搜索引擎或者开发包都使用了这个模型，比如Lucene。

(1) 倒排索引结构：1. 词语组成的字典结构——Dictionary如下图左侧
2. 文档组成的位置链—— Postiong 如下图右侧
(2) 创建过程
1. 将每一个文档中的词语与文档ID(唯一标示文档)组成一个Pair，存入index。

如左图A
2. 将index中的词语按字典序排序。

如中图B
3. 如果相同词语来自同一个文档，则只记录一次。

相同词语来自不同文档，则合并成进posting。

如右图C
(3) 索引存储方法
很显然，对于倒排索引，我们必须把Dictionary和Posting都存储起来。

一般Dictionary可以全部加载进内存中，而Posting存放在磁盘中，当需要查找Posting的时候，再会将某一个词语所指向的Posting加载进内存。

Dictionary in menory
很多时候使用Hash表的形式，也用连续存储的数组结构。

Posting in menory：
1. 单链表( singly linked lists) ，在将新文档插入Posting中的时候付出的代价较少。

这一点很适合高频率从网上抓取内容并更新文档。

2. 可变长数组(variable length arrays)，节约了指针所需要的额外空间。

并且对于拥有内存缓存区的现代计算机而言，连续内存的结构无疑会增加查询的速度。

3. 跳跃表(skip lists)，一种很先进的存储结构。

除了需要额外耗费一些指针空间之外，查找效率极高。

Lucene就是用了这种结构。

1.3 布尔查询表达式的处理
(1) Posting的合并算法(merge algorithm)
假如我们需要在倒排索引上查找这样一个表达式：Brutus AND Calpurnia。

很明显我们需要下面几个步骤：
1. 在Dictionary中定位Brutus.
2. 检索Brutus所指向的Posting：1、2、4、11、31....
3. 在Dictionary中定位Calpurnia.
4. 检索Calpurnia所指向的Posting：2、31、54....
5. 合并两个Posting.
对于两个有序表的合并算法，可以采用下面的算法：时间复杂度为O(m+n)
C代码
//指针P1,P2分别指向两个Posting链
2Posting intersect(p1,p2){
3
4Posting answer;
5while(p1!=null&&p2!=null){
6if(p1==p2){
7add(answer, p1->docID);
8p1=p1->next;
9p2=p2->next;
10}
11if(p1>p2) p2=p2->next;
12if(p1<p2) p1=p1->next;
13
14}
15}
(2) 布尔表达式的优化
Brutus AND Caesar AND Calpurnia
表达式的AND顺序按照每一个词的文档频率递增进行优化。

比如Brutus‘s Ducument Frequence(Brutus 所在文档的数量，符号表示DF(Brutus))。

DF(Brutus)=1000，DF(Caesar)=10000，DF(Calpurnia)=100。

那么查询表达式可以优化成：(Calpurnia AND Brutus) AND Caesar。

理由很简单，Calpurnia AND Brutus的时间复杂度(利用上面的合并算法)为O(1100)，其合并后的中间结果R=DF(Calpurnia AND Brutus)<DF(Calpurnia)=100。

此时将这个中将结果R AND Caesar 的时间复杂度不会超过O(100+10000)。

而且最后结果页不会操作DF<DF(Calpurnia AND Brutus)<100。

总的时间复杂度为O(1100+10100)=O(11200)
如果使用原表达式，Brutus AND Caesa的时间复杂度为O(11000)，且中间结果为R=DF( Brutus AND Caesa )< DF(Brutus)=1000。

然后R AND Calpurnia的时间复杂度可能达到O(1000+100)。

两次AND操作的总时间复杂度为O(11000+1100)=O(12100)
明显优化之后的时间复杂度会少。

如果查询表达式更长，查询词语的DF差距更大，那么优化的效率会更明显。

根据上面的优化原理，对于更加复杂的查询表达式(madding OR crowd) AND (ignoble OR strife) AND
(killed OR slain)。

我们一般都会估算OR操作两个词的DF之和的数量，然后进行AND递增排序。

事实上，对于任意的布尔表达式，每一次操作的中间结果(intermediate)越小越好。

这是我们进行优化的原则所在。

(3) 自然语言查询AND 布尔查询表达式
为什么我们对布尔表达式的操作只将AND，很少说OR或NOT呢？
在搜索引擎实际应用的环境下，用户的查询都是自然语言叙述的，很少直接用布尔表达式(你不能要求所有的用户必须逻辑思维缜密吧)。

那么对于用户提交的这些查询，都是纯粹的合并操作。

正是这个原因，现实中很多搜索引擎的应用已经退化成了只有AND的布尔模型了。