《Introduce to IR》布尔检索模型.docVIP

《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 很多时候使用