搜索
第5章非结构化数据处理IR布尔检索倒排表模糊检索相似性TFIDF提纲信息检索概述倒排索引布尔查询的处理信息检索INFORMATIONRETRIEVALInformationRetrieval(IR)isfindingmaterial(usuallydocuments)ofanunstructurednature(usuallytext)thatsatisfiesaninformationneedfromwithinlargecollections(usuallystoredoncomputers).信息检索是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。Document–文档Unstructured–非结构化Informationneed–信息需求Collection—文档集、语料库3IRVS数据库:结构化VS非结构化数据结构化数据即指“表”中的数据EmployeeManagerSalarySmithJones50000ChangSmith6000050000IvySmith数据库常常支持范围或者精确匹配查询。e.g.,Salary60000ANDManager=Smith.非结构化数据通常指自由文本允许•关键词加上操作符号的查询•更复杂的概念性查询,•找出所有的有关药物滥用(drugabuse)的网页经典的检索模型一般都针对自由文本进行处理半结构化数据没有数据是完全无结构的title李甲主页/titlebody…/body…半结构化查询•TitlecontainsdataANDBulletscontainsearch•…这里还没有提文本的语言结构非结构化数据(文本)VS.结构化数据(数据库)@1996年020406080100120140160180200DatavolumeMarketCapUnstructuredStructured数据量市场规模非结构化数据(文本)VS.结构化数据(数据库)@2009年数据量市场规模布尔检索•针对布尔查询的检索，布尔查询是指利用AND,OR或者NOT操作符将词项连接起来的查询•信息AND检索•信息OR检索•信息AND检索ANDNOT教材提纲①信息检索概述②倒排索引③布尔查询的处理一个简单的例子(《莎士比亚全集》)莎士比亚的哪部剧本包含Brutus及Caesar但是不包含Calpurnia？布尔表达式为BrutusANDCaesarANDNOTCalpurnia。笨方法：从头到尾扫描所有剧本，对每部剧本判断它是否包含BrutusANDCaesar，同时又不包含Calpurnia笨方法为什么不好?•速度超慢(特别是大型文档集)•处理NOTCalpurnia并不容易（一旦包含即可停止判断）•不太容易支持其他操作(e.g.,findthewordRomansnearcountrymen)•不支持检索结果的排序(即只返回较好的结果)词项-文档(TERM-DOC)的关联矩阵AntonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbethAntony110001Brutus110100Caesar110111Calpurnia010000Cleopatra100000mercy101111worser101110若某剧本包含某单词，则该位置上为1，否则为0BrutusANDCaesarBUTNOTCalpurnia关联向量(INCIDENCEVECTORS)关联矩阵的每一列都是0/1向量，每个0/1都对应一个词项给定查询BrutusANDCaesarANDNOTCalpurnia取出三个列向量，并对Calpurnia的列向量求补，最后按位进行与操作110100AND110111AND101111=100100.上述查询的结果文档AntonyandCleopatra,ActIII,SceneiiAgrippa[AsidetoDOMITIUSENOBARBUS]:Why,Enobarbus,WhenAntonyfoundJuliusCaesardead,Hecriedalmosttoroaring;andheweptWhenatPhilippihefoundBrutusslain.Hamlet,ActIII,SceneiiLordPolonius:IdidenactJuliusCaesarIwaskilledi'theCapitol;Brutuskilledme.IR中的基本假设文档集Collection:由固定数目的文档组成目标:返回与用户需求相关的文档并辅助用户来完成某项任务相关性Relevance•主观的概念•反映对象的匹配程度•不同应用相关性不同典型的搜索过程文档集任务信息需求查询自然语言描述结果搜索引擎查询重构GetridofmiceinapoliticallycorrectwayInfoaboutremovingmicewithoutkillingthemHowdoItrapmicealive?mousetrap是否转义?是否转义?是否转义?检索效果的评价正确率(Precision):返回结果文档中正确的比例。如返回80篇文档，其中20篇相关，正确率1/4召回率(Recall):全部相关文档中被返回的比例，如返回80篇文档，其中20篇相关，但是总的应该相关的文档是100篇，召回率1/5正确率和召回率反映检索效果的两个方面，缺一不可。•全部返回，正确率低，召回率100%•只返回一个非常可靠的结果，正确率100%，召回率低大文档集假定N=1百万篇文档(1M),每篇有1000个词(1K)假定每个词平均有6个字节(包括空格和标点符号)•那么所有文档将约占6GB空间.假定词汇表的大小(即词项个数)M=500K词项-文档矩阵将非常大矩阵大小为500Kx1M=500G但是该矩阵中最多有10亿(1G)个1•词项-文档矩阵高度稀疏(sparse).•稀疏矩阵应该有更好的表示方式•比如我们仅仅记录所有1的位置Why?倒排索引(INVERTEDINDEX)对每个词项t,记录所有包含t的文档列表.•每篇文档用一个唯一的docID来表示，通常是正整数，如1,2,3…能否采用定长数组的方式来存储docID列表BrutusCalpurniaCaesar124561657132124113145173231文档14中加入单词Caesar时该如何处理?17454101倒排索引(续)通常采用变长表方式•磁盘上，顺序存储方式比较好，便于快速读取•内存中，采用链表或者可变长数组方式•存储空间/易插入之间需要平衡DictionaryPostings按docID排序(原因后面再讲)PostingBrutusCalpurniaCaesar12456165713212411314517323117454101词典倒排(记录)表倒排记录Tokenizer词条流FriendsRomansCountrymen倒排索引构建Linguisticmodules修改后的词条friendromancountrymanIndexer倒排索引friendromancountryman24213161Moreontheselater.待索引文档Friends,Romans,countrymen.词条化工具语言分析工具索引构建过程:词条序列词条，docID二元组IdidenactJuliusCaesarIwaskilledi'theCapitol;Brutuskilledme.Doc1SoletitbewithCaesar.ThenobleBrutushathtoldyouCaesarwasambitiousDoc2索引构建过程:排序按词项排序•然后每个词项按docID排序索引构建的核心步骤索引构建过程:词典&倒排记录表某个词项在单篇文档中的多次出现会被合并拆分成词典和倒排记录表两部分每个词项出现的文档数目(doc.frequency,DF)会被加入为什么加入？后面会讲存储开销计算指针词项及文档频率后续章节:•如何快速构建索引?•如何减少存储开销?倒排索引docID表第一讲：布尔检索提纲①信息检索概述②倒排索引③布尔查询的处理第一讲：布尔检索假定索引已经构建好如何利用该索引来处理查询?•后面会讲–如何处理不同类型的查询?比如带通配符的查询“信息*检索”今天主要内容第一讲：布尔检索AND查询的处理考虑如下查询（从简单的布尔表达式入手）:•BrutusANDCaesar•在词典中定位Brutus•返回对应倒排记录表(对应的docID)•在词典中定位Caesar•再返回对应倒排记录表•合并(Merge)两个倒排记录表，即求交集12834248163264123581321BrutusCaesar合并过程每个倒排记录表都有一个定位指针，两个指针同时从前往后扫描,每次比较当前指针对应倒排记录，然后移动某个或两个指针。合并时间为两个表长之和的线性时间3412824816326412358132112834248163264123581321BrutusCaesar28假定表长分别为x和y,那么上述合并算法的复杂度为O(x+y)关键原因:倒排记录表按照docID排序上述合并算法的伪代码描述其它布尔查询的处理•OR表达式：BrutusANDCaesar•两个倒排记录表的交集•NOT表达式：BrutusANDNOTCaesar•两个倒排记录表的减一般的布尔表达式(BrutusORCaesar)ANDNOT(AntonyORCleopatra)查询处理的效率问题！查询优化查询处理中是否存在处理的顺序问题？考虑n个词项的AND对每个词项，取出其倒排记录表，然后两两合并BrutusCaesarCalpurnia123581621342481632641281316查询:BrutusANDCalpurniaANDCaesar查询优化按照表从小到大(即df从小到大)的顺序进行处理:•每次从最小的开始合并这是为什么保存df的原因之一相当于处理查询(CalpurniaANDBrutus)ANDCaesar.BrutusCaesarCalpurnia123581621342481632641281316更通用的优化策略e.g.,(maddingORcrowd)AND(ignobleORstrife)•每个布尔表达式都能转换成上述形式(合取范式)获得每个词项的df(保守)通过将词项的df相加，估计每个OR表达式对应的倒排记录表的大小按照上述估计从小到大依次处理每个OR表达式.布尔检索的优点构建简单，或许是构建IR系统的一种最简单方式•在30多年中是最主要的检索工具•当前许多搜索系统仍然使用布尔检索模型:•电子邮件、文献编目、MacOSXSpotlight工具布尔检索例子:WESTLAW(付费用户数目)最大的商业化法律搜索服务引擎(1975年开始提供服务;1992年加入排序功能)几十T数据，700,000用户大部分用户仍然使用布尔查询查询的例子:•有关对政府侵权行为进行索赔的诉讼时效(Whatisthestatuteoflimitationsincasesinvolvingthefederaltortclaimsact?）•LIMIT!/3STATUTEACTION/SFEDERAL/2TORT/3CLAIM•/3=within3words,/S=insamesentence布尔检索例子:WESTLAW另一个例子:•残疾人士能够进入工作场所的要求（Requirementsfordisabledpeopletobeabletoaccessaworkplace）•disabl!/paccess!/swork-sitework-place(employment/3place扩展的布尔操作符很多专业人士喜欢使用布尔搜索•非常清楚想要查什么、能得到什么但是这并不