网站开发价格表,wordpress分行符,临沂市建设局网站简介,傻瓜内网网站建设一#xff0c;问题描述 在Shakespeare文集#xff08;有很多文档Document#xff09;中#xff0c;寻找哪个文档包含了单词“Brutus”和Caesar#xff0c;且不包含Calpurnia。这其实是一个查询操作#xff08;Boolean Queries#xff09;。 在U…一问题描述 在Shakespeare文集有很多文档Document中寻找哪个文档包含了单词“Brutus”和Caesar且不包含Calpurnia。这其实是一个查询操作Boolean Queries。 在Unix中有个工具grep它能线性扫描一篇文档然后找出某个单词是否在该文档中。因此寻找哪篇文档包含了“Brutus”和“Caesar”可以用grep来实现。但是不包含“Calpurnia”如何实现呢 有时还有一些更加复杂的情况比如寻找“Romans”附近出现“countrymen”的文档有哪些附近 表示寻找的范围比如在某篇文档中“Romans”和“countrymen”出现在同一段落中那么这篇文档就是要找的文档再比如“Romans”前后10个词内出现“countrymen”则这篇文档就是要找的文档。这种情况又如何处理 再比如寻找 包含单词“Brutus”和Caesar的文档返回的结果有很多篇文档哪篇文档最相关呢Rank retrieval。这些复杂的情况都无法用 grep 工具来实现而是使用了一些特殊的数据结构文档表示方式。比如 Term-document incidence matrices 和 倒排索引Inverted index 二Term-document incidence matrices 介绍一个新概念Term 在处理文档时经常以单词(word)作为分析处理单元(units)但有一些专有名词又不是传统意义上的单词比如Hong Kong或者一些一连串的数字。因此在IR中用term来表示index units。看到这里就明白tf-idfterm frequency–inverse document frequency 中的 term 是什么意思了。 Terms are the indexed unitsthey are usually words, and for the moment you can think of them as words, but the information retrieval literature normally speaks of terms because some of them, such as perhaps I-9 or Hong Kong are not usually thought of as words. 回到文章开头提出的那个问题哪个文档包含了单词“Brutus”和Caesar且不包含Calpurnia更专业地 哪个文档包含了 term Brutus 和 term Caesar且不包含term Calpurnia 首先将文档拆分成一个个的 term 来表示若某个term在这篇文档中出现 就用1标识未出现则用0标识。 如上图所示每一列代表一篇文档是否包含了某个term比如 文档 Julius Caesar 就包含了Antony、Brutus、Caesar、Calpurnia但是不包含Cleopatra、mercy、worser。 每一行表示 某个term 出现在哪几篇文档中。比如 term Antony出现在第一篇文档、第二篇文档Julius Caesar和最后一篇文档中。 有了这个矩阵就可以回答上面那个问题了。Brutus 在文档中出现情况是 110100Caesar在文档中出现情况是 110111 Calpurnia 出现情况是 101111将它们进行 与操作 110100 AND 110111 AND 101111 100100 得出包含了单词“Brutus”和Caesar且不包含Calpurnia的文档是第一篇文档Antony and Cleopatra 和 第四篇文档 Hamlet。而且对于计算机而言进行与操作是很快的。 从上面可看出通过Term-document incidence matrices这种文档的表示形式将 grep 线性查找操作变成了 位与 操作。 但是这种表示方式也存在着问题这个矩阵会很稀疏。比如中文汉字有几万个term 很多一篇新闻文档不会用到所有的中文汉字因此矩阵中大部分元素为0。而要存储一个很大的稀疏矩阵对内存就造成了浪费。而倒排索引就可以解决这个问题。 三inverted index 倒排索引就是如果某个term在文档中出现了才记录它。若不出现则不记录。 A much better representation is to record only the things that do occur, that is, the 1 positions.We keep a dictionary of terms Then for each term, we have a list that records which documents the term occurs in.Each item in the list – which records that a term appeared in a document– is conventionally called a posting 假设有很多文档如何构建倒排索引呢首先是从文档中选取出 term也就是对文档进行分词得到一个个的 term。比如有N篇文档如下 文档一 Friends, Romans, countrymen.
文档二 So let it be with Caesar........文档N 对文档文档分词(tokenize)得到一系列的tokensFriends、Romans、countrymen、So…… 有时还需要对分词的结果进行预处理(linguistic preprocessing)这种预处理操作一般是删除一些 stop words进行 Stemming 操作 和 lemmatization操作。stemming操作 是从词形上对单词归一化比如说复数cats 变成 cat。而 lemmatization 是寻找词根比如are, is, am 都归一化成 be Stemming usually refers to a crude heuristic process that chops off the ends of words in the hope of achieving this goal correctly most of the time, and often includes the removal of derivational affixes Lemmatization usually refers to doing things properly with the use of a vocabulary and morphological analysis of words normally aiming to remove inflectional endings only and to return the base or dictionary form of a word, which is known as the lemma。 预处理之后得到一个个的 可索引的 term 了。倒排索引如下图所示 Brutus就是一个term它关联着一个链表(list)这个链表称之为posting链表中的每个元素代表文档的标识它表示 term Brutus出现在 文档1文档2文档4文档11文档31……文档174中 若干个 term 组合起来就是一个 dictionary所有的posting的集合就是 postings 从上可看出使用倒排索引表示时每个文档都有一个唯一的文档标识(docID)而且链表是有序的。并且上面的倒排索引只关注某个term是文档中 是否 出现过并不知道出现了多少次。 现在如何根据倒排索引找出哪个文档包含了单词“Brutus”和Caesar且不包含Calpurnia这其实就是 Brutus 指向的链表 和 Caesar指向的链表 求并 操作intersection---两个有序的链表找公共元素。算法的伪代码如下 INTERSECT(p1, p2)answer ← while p1 ! NIL and p2 ! NILdo if docID(p1) docID(p2)then ADD(answer, docID(p1))p1 ← next(p1)p2 ← next(p2)else if docID(p1) docID(p2)then p1 ← next(p1)else p2 ← next(p2)return answer 时间复杂度为O(N)N就是 文档的总个数。对于两个有序链表 求并 操作时间复杂度会不会小于O(N)呢那也是有可能的那就是在链表的某些元素上存储一个skip pointer指针如下图所示 举个例子假设目前已经找到了两个链表中的第一个公共元素8现在要找下一个公共元素。链表1移动到下一个位置指向16链表2移动到下一个位置指向41。由于元素16存储了一个skip pointer该skip pointer指向28由于链表是有序的而且28小于41因此链表1可以直接跳过19、23这两个元素直接移动到28这个元素上从而不需要将 19和23 这两个元素与 链表2中的41比较。算法伪代码如下 INTERSECTWITHSKIPS(p1, p2)
1 answer ←
2 while p1 ! NIL and p2 ! NIL
3 do if docID(p1) docID(p2)
4 then ADD(answer, docID(p1))
5 p1 ← next(p1)
6 p2 ← next(p2)
7 else if docID(p1) docID(p2)
8 then if hasSkip(p1) and (docID(skip(p1)) ≤ docID(p2))
9 then while hasSkip(p1) and (docID(skip(p1)) ≤ docID(p2))
10 do p1 ← skip(p1)
11 else p1 ← next(p1)
12 else if hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
13 then while hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
14 do p2 ← skip(p2)
15 else p2 ← next(p2)
16 return answer 引入skip pointers到底是好还是坏呢这个不一而足。说几个需要考虑的因素 ①引入skip pointer 需要额外的存储空间。②移动到某个元素上时需要判断该元素是否存储了 skip pointers。③在哪些元素上存储 skip pointer比较好 skip pointers 跳过多少个元素比较好…… 额外的一点 补充上面讲到每个 term 的posting list 长度是未知的。要找某两个term的公共元素其实就里线性遍历这两个term对应的posting list。因此这个过程的时间复杂度是O(MN) 。这里的M是第一个term对应的posting list的长度N是第二个term对应的posting list的长度。那如果我要找多个term的posting list中的公共元素呢 比如说寻找 term : Brutus 、Calpurnia、Caesar这三个term都在哪些文档中出现了 这是一个与操作。如果知道 posting list的长度先将长度比较短的term的posting list进行与操作这样能提高查询的效率。比如说从上面图中可看出Calpurnia 的posting list的长度为4先执行 Calpurnia Brutus 得出的结果的长度也不会超过4然后再去Caesar对应的posting list中查询。效率要好。 即执行顺序为Calpurnia Brutus Caesar 比 Caesar Brutus Calpurnia 要好。 四参考资料 《An Introduction to Information Retrieval》第一章和第二章 原文http://www.cnblogs.com/hapjin/p/8214254.html转载于:https://www.cnblogs.com/hapjin/p/8214254.html
