lecture1-布尔检索

《lecture1-布尔检索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1讲布尔检索BooleanRetrieval2016/9/5提纲信息检索概述倒排索引布尔查询的处理2提纲信息检索概述倒排索引布尔查询的处理3信息检索(InformationRetrieval)InformationRetrieval(IR)isfindingmaterial(usuallydocuments)ofanunstructurednature(usuallytext)thatsatisfiesaninformationneedfromwithinlargecollections(usuallystored

2、oncomputers).信息检索是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。Document–文档Unstructured–非结构化Informationneed–信息需求Collection—文档集、语料库4文本检索本课程主要关注文本检索（TextRetrieval）(1)文本检索是最早的检索应用，也仍然是目前最主要的应用文本检索理论可以用于其他领域……5IRvs数据库:结构化vs非结构化数据结构化数据即指“表”中的数据6EmployeeMan

3、agerSalarySmithJones50000ChangSmith6000050000IvySmith数据库常常支持范围或者精确匹配查询。e.g.,Salary<60000ANDManager=Smith.非结构化数据通常指自由文本(freetext)允许关键词加上操作符号的查询如奥运会AND游泳更复杂的概念性查询找出所有的有关药物滥用(drugabuse)的网页经典的检索模型一般都针对自由文本进行处理7半结构化数据没有数据是完全无结构的，比如网页就是一种半结构化数据

4、y>……半结构化查询TitlecontainsdataANDBulletscontainsearch严格来说，即使是文本也是有“语言”结构比如主谓宾结构8传统信息检索vs.现代信息检索传统信息检索主要关注非结构化、半结构化数据现代信息检索中也处理结构化数据9非结构化数据(文本)vs.结构化数据(数据库)@1996年10数据量市场规模非结构化数据(文本)vs.结构化数据(数据库)@2009年11数据量市场规模布尔检索针对布尔查询的检索，布尔查询是指利用AND,OR或者NOT操作符将词项连接起来的查询信息A

5、ND检索信息OR检索信息AND检索ANDNOT教材Google的高级搜索？12提纲信息检索概述倒排索引布尔查询的处理13一个简单的例子(《莎士比亚全集》)需求：莎士比亚的哪部剧本包含Brutus及Caesar但是不包含Calpurnia？将需求表示为布尔表达式：BrutusANDCaesarANDNOTCalpurnia。14不到100万单词，假设每个英文单词平均长度为8字节，则整个全集不到10MB一个简单的例子(《莎士比亚全集》)暴力方法：从头到尾扫描所有剧本，对每部剧本判断它是否包含BrutusANDCaesar

6、，同时又不包含Calpurnia暴力方法有什么不足?速度超慢(特别是大型文档集)处理NOTCalpurnia并不容易（不到末尾不能停止判断）不太容易支持其他操作(e.g.,寻找靠近countrymen的单词Romans)不支持检索结果的(灵活)排序(排序时只返回较好的结果)暴力方法的优点？实现简单很容易支持文档动态变化15词项-文档(term-doc)的关联矩阵若某剧本包含某单词，则该位置上为1，否则为0BrutusANDCaesarBUTNOTCalpurnia关联向量(incidencevectors)关联矩阵的

7、每一列(对应一篇文档)都是0/1向量，每个0/1都对应一个词项。关联矩阵的每一行(对应一个词项)也可以看成一个0/1向量，每个0/1代表该词项在相应文档中的出现与否给定查询BrutusANDCaesarANDNOTCalpurnia取出三个词项对应的行向量，并对Calpurnia的行向量求反，最后按位进行与操作110100AND110111AND101111=100100.17上述查询的结果文档AntonyandCleopatra,ActIII,SceneiiAgrippa[AsidetoDOMITIUSENOBAR

8、BUS]:Why,Enobarbus,WhenAntonyfoundJuliusCaesardead,Hecriedalmosttoroaring;andheweptWhenatPhilippihefoundBrutusslain.Hamlet,ActIII,SceneiiLordPolonius:IdidenactJuliusCaesarIw