专栏首页J博士的博客01布尔模型&倒排索引

01布尔模型&倒排索引

原文链接: http://www.cnblogs.com/jacklu/p/8379726.html

博士一年级选了这门课 SEEM 5680 Text Mining Models and Applications,记下来以便以后查阅。

1. 信息检索的布尔模型

用0和1表示某个词是否出现在文档中。如下图例子,要回答“Brutus AND Caesar but NOT Calpurnia”,我们需要对词的向量做布尔运算,即110100 AND 110111 AND 101111=100100 对应的文档是Antony and Cleopatra和Hamlet

然而这种方法随着数据的增大是非常耗费空间的。比如我们有100万个文档,每个文档平均有1000字,总共有50万个不同的词语,那么矩阵将是500 000 x 1 000 000。这个矩阵是稀疏的,1的个数一般不会超过1亿个。

2. 倒排索引

倒排索引是为了解决上述布尔模型的问题。具体来说,每个词用链表顺序存储文档编号。如下图所示:

建立索引的核心是将词按字母顺序排列,合并重复词,但是要记录词频。

3. 倒排索引模型中对查询语句(AND)的处理

1、求Brutus AND Calpurnia,即求两个链表的交集。

算法思路是如果文档号不同就移动较小的指针,伪代码 INTERSECTION(p1, p2):

answer<-()
while p1 != NIL and p2 != NIL
do if docID(p1) = docID(p2)
     then ADD(answer, docID(p1))
         p1 <-next(p1)
         p2 <-next(p2)
     else if docID(p1) < docID(p2)
         p1 <-next(p1)
     else p2<-next(p2)
return answer

思考题,有两个词项A,B,其文档编号链表长度分别为3和5,那么对A,B求交集,最少的访问次数和最多的访问次数分别是多少?各举一个例子

最少访问次数是4,比如A:1-2-3,B:3-4-5-6-7;最多访问次数是8,比如A:1-7-8, B:3-4-5-7-9

2、思考题:求Brutus OR Calpurnia,即求两个链表的并集。伪代码 UNION(p1,p2):

answer<-()
while p1 != NIL and p2 != NIL
do if docID(p1) = docID(p2)
    then ADD(answer, docID(p1))
        p1 <-next(p1)
        p2 <-next(p2)
    else if docID(p1) < docID(p2)
    then ADD(answer, docID(p1))
        p1<-next(p1)
    else ADD(answer, docID(p2))
        p2<-next(p2)
return answer

3、思考题:求Brutus AND NOT Calpurnia。伪代码 INTERSECTION(p1,p2, AND NOT):

answer<-()
while p1 != NIL and p2 != NIL
do if docID(p1) = docID(p2)
        p1 <-next(p1)
        p2 <-next(p2)
    else if docID(p1) < docID(p2)
    then ADD(answer, docID(p1))
        p1<-next(p1)
    else p2<-next(p2)
    
    if p1 != NIL and P2 = NIL
    then ADD(answer, docID(p1))
        p1<-next(p1)
return answer

参考资料:http://www1.se.cuhk.edu.hk/~seem5680/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CTL_CODE说明

    DeviceIoControl函数的第二个参数IoControlCode就是由CTL_CODE宏定义的,下边我们可以了解一下CTL_CODE的内容。

    用户7043923
  • 经典功率谱估计及Matlab仿真

    原文出自:http://www.cnblogs.com/jacklu/p/5140913.html

    用户7043923
  • 隐马尔可夫模型(HMM)

    原文地址:http://www.cnblogs.com/jacklu/p/7753471.html

    用户7043923
  • Python Raw Socket使用示

    py3study
  • 剑指Offer面试题:18.二叉树的镜像

    Step1.先序遍历原二叉树的每个节点,如果遍历到的结点有子结点,就交换它的两个子结点。

    Edison Zhou
  • iOS开发——Carthage安装和使用教程

    Carthage 使用于 Swift 语言编写,只支持动态框架,只支持 iOS8+的Cocoa依赖管理工具。

    Originalee
  • 基于 Swoole 的微信扫码登录

    随着微信的普及,扫码登录方式越来越被现在的应用所使用。它因为不用去记住密码,只要有微信号即可方便快捷登录。微信的开放平台原生就有支持扫码登录的功能,不过大部分人...

    企鹅号小编
  • BIO在聊天室项目中的演化

    喜欢天文的pony站长
  • 【陆勤阅读】12 位史上最“屌”程序员,他们缔造了整个互联网时代

    人们每天使用的App,以及玩儿的电子游戏不是凭空就有的,而是程序员笔耕不辍,靠着他们一行行的代码开发出来的。 当然,那些App应用、网页、甚至是整个互联网本身...

    陆勤_数据人网
  • Vue[0x03] - Vue基础实践

    抓重点讲吧,最开始可追溯的版本号是0.6.0这个,但是正式对外发布的版本是在2014年1月24日发布的0.8.0。后面就是两个打头的里程碑,一个是1.x.x,一...

    丰臣正一

扫码关注云+社区

领取腾讯云代金券