logo资料库

信息检索导论_王斌译_课后习题答案.pdf

发布时间：2022-06-14 发布人：admin 分类：说明书 资料大小：0.62M 资料格式：pdf 举报 版权申诉
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
资料共16页，剩余部分请下载后查看
    《信息检索导论》课后练习答案 ⺩王斌 最后更新⽇日期 2013/9/28 第⼀一章 布尔检索 习题1-1 [*]　画出下列文档集所对应的倒排索引（参考图1-3中的例子）。 文档 1 new home sales top forecasts 文档 2 home sales rise in july 文档 3 increase in home sales in july 文档 4 july new home sales rise 解答： forecasts home in increase july new rise sales top -------> -------> -------> -------> -------> -------> -------> -------> -------> 1 1  2  3 2  1  2  1  1 2  3  3 3  4 4 4 2  3  4 4 习题1-2 [*]　考虑如下几篇文档： 文档1 breakthrough drug for schizophrenia 文档2 new schizophrenia drug 文档3 new approach for treatment of schizophrenia 文档4 new hopes for schizophrenia patients a. 画出⽂文档集对应的词项—⽂文档矩阵； 解答： 文档1 文档2 文档3 文档4 approach breakthrough 0 1 0 0 1 0 0 0
    drug for hopes new of patients schizophrenia treatment 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 b. 画出该⽂文档集的倒排索引（参考图 1-3中的例⼦子）。 解答：参考a。 习题1-3 [*]　对于习题1-2中的文档集，如果给定如下查询，那么返回的结果是什么？ schizophrenia AND drug a. 解答：{文档1，文档2} for AND NOT (drug OR approach） b. 解答：{文档4} 习题1-4 [*] 对于如下查询，能否仍然在O(x+y)次内完成？其中x和y分别是Brutus和Caesar所对应的倒排 记录表长度。如果不能的话，那么我们能达到的时间复杂度是多少？ a. Brutus AND NOT Caesar b. Brutus OR NOT Caesar 解答： a. 可以在O(x+y)次内完成。通过集合的减操作即可。具体做法参考习题1-11。 b. 不能。不可以在O(x+y)次内完成。因为NOT Caesar的倒排记录表需要提取其他所有词项对应的 倒排记录表。所以需要遍历几乎全体倒排记录表，于是时间复杂度即为所有倒排记录表的长度 的和N，即O(N) 或者说O(x+N-y)。 习题1-5 [*] 将倒排记录表合并算法推广到任意布尔查询表达式，其时间复杂度是多少？比如，对于查询 c. (Brutus OR Caesar) AND NOT (Antony OR Cleopatra) 我们能在线性时间内完成合并吗？这里的线性是针对什么来说的？我们还能对此加以改进吗？ 解答：时间复杂度为O(qN)，其中q为表达式中词项的个数，N为所有倒排记录表长度之和。也就是说可以 在词项个数q及所有倒排记录表长度N的线性时间内完成合并。由于任意布尔表达式处理算法复杂度的上 界为O(N)，所以上述复杂度无法进一步改进。 习题1-6 [**]　假定我们使用分配律来改写有关AND和OR的查询表达式。 12 a. 通过分配律将习题1-5中的查询写成析取范式； b. 改写之后的查询的处理过程比原始查询处理过程的效率高还是低？ c. 上述结果对任何查询通用还是依赖于文档集的内容和词本身？ 解答： a. 析取范式为：(Brutus And Not Anthony And Not Cleopatra) OR (Caesar AND NOT Anthony AND NOT Cleopatra) b. 这⾥里的析取范式处理⽐比前⾯面的合取范式更有效。这是因为这⾥里先进⾏行AND操作(括号内)，得到的倒排记录表 都不⼤大，再进⾏行OR操作效率就不会很低。⽽而前⾯面需要先进⾏行OR操作，得到的中间倒排记录表会更⼤大⼀一些。 c. 上述结果不⼀一定对，⽐比如两个罕⻅见词A和B构成的查询 (A OR B) AND NOT(HONG OR KONG)，假设HONG KONG⼀一起出现很频繁。此时合取⽅方式可能处理起来更⾼高效。如果在析取范式中仅有词项的⾮非操作时，b中结果 不对。
    习题 1-7 [*]　请推荐如下查询的处理次序。 d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes） 其中，每个词项对应的倒排记录表的长度分别如下： 倒排记录表⻓长度 词项 eyes kaleidoscope marmalade skies tangerine trees 213 312 87 009 107 913 271 658 316 812 46 653 解答： 由于： (tangerine OR trees) ➔ 46653+316812 = 363465 (marmalade OR skies)➔ 107913+271658 = 379571 (kaleidoscope OR eyes）➔ 87009+213312 = 30321 所以推荐处理次序为： (kaleidoscope OR eyes）AND (tangerine OR trees) AND (marmalade OR skies) 习题1-8[*] 对于查询 e. friends AND romans AND (NOT countrymen) 如何利用countrymen的文档频率来估计最佳的查询处理次序？特别地，提出一种在确定查询顺序时对逻 辑非进行处理的方法。 解答：令friends、romans和countrymen的文档频率分别为x、y、z。如果z极高，则将N-z作为NOT countrymen的长度估计值，然后按照x、y、N-z从小到大合并。如果z极低，则按照x、y、z从小到大合 并。 习题 1-9 [**]　对于逻辑与构成的查询，按照倒排记录表从小到大的处理次序是不是一定是最优的？如果 是，请给出解释；如果不是，请给出反例。 解答：不一定。比如三个长度分别为x,y,z的倒排记录表进行合并，其中x>y>z，如果x和y的交集为空集， 那么有可能先合并x、y效率更高。 习题 1-10 [**]　对于查询x OR y，按照图1-6的方式，给出一个合并算法。 解答： p1<- next(p1) p2<-next(p2) 1 answer<- ( ) 2 while p1!=NIL and p2!=NIL 3 do if docID(p1)=docID(p2) 4 then ADD(answer,docID(p1)) 5 6 7 else if docID(p1)
    14 else while p2!=NIL do ADD(answer,docID(p2)) 15 return(answer) 习题 1-11 [*] 如何处理查询x AND NOT y？为什么原始的处理方法非常耗时？给出一个针对该查询的高效 合并算法。 解答：由于NOT y几乎要遍历所有倒排表，因此如果采用列举倒排表的方式非常耗时。可以采用两个 有序集合求减的方式处理 x AND NOT y。算法如下： answer () while p1!=NIL and p2!=NIL do if docID(p1) =docID(p2) then p1next(p1) p2next(p2) else if docID(p1)
    a. 在布尔检索系统中，进行词干还原从不降低正确率。 b. 在布尔检索系统中，进行词干还原从不降低召回率。 c. 词干还原会增加词项词典的大小。 d. 词干还原应该在构建索引时调用，而不应在查询处理时调用。 解答： a错 b 对 c错 d 错 习题2-7 [*]　考虑利用如下带有跳表指针的倒排记录表 和一个中间结果表（如下所示，不存在跳表指针）进行合并操作。 3　5　89　95　97　99　100　101 采用图2-10所示的倒排记录表合并算法，请问： a. 跳表指针实际跳转的次数是多少（也就是说，指针p1的下一步将跳到skip（p1））？ 一次，24—>75 b. 当两个表进行合并时，倒排记录之间的比较次数是多少？【如下答案不一定正确，有人利用程 序计算需要21次，需要回到算法，本小题不扣分，下面不考虑重新比较同意对数字】 解答： 18次： <3,3>, <5,5>, <9,89>, <15,89>,<24,89>,<75,89>,<92,89>,<81,89>,<84,89>,<89,89>,<92,95>,<115,95>,<96,95>,<96,97>,< 97,97>,<100,99>,<100,100><115,101> c. 如果不使用跳表指针，那么倒排记录之间的比较次数是多少？ 解答： 19次： <3,3>,<5,5>,<9,89>,<15,89>,<24,89>,<39,89>,<60,89>,<68,89>,<75,89>,<81,89>,<84,89>,<89,89> <92,95>, <96,95>,<96,97>,<97,97>,<100,99>,<100,100>,<115,101> 习题 2-9 [*]　下面给出的是一个位置索引的一部分，格式为：词项: 文档1: 〈位置1, 位置2, …〉; 文档 2: 〈位置1, 位置2, …〉。 angels: 2: 〈36,174,252,651〉; 4: 〈12,22,102,432〉; 7: 〈17〉; fools: 2: 〈1,17,74,222〉; 4: 〈8,78,108,458〉; 7: 〈3,13,23,193〉; fear: 2: 〈87,704,722,901〉; 4: 〈13,43,113,433〉; 7: 〈18,328,528〉; in: 2: 〈3,37,76,444,851〉; 4: 〈10,20,110,470,500〉; 7: 〈5,15,25,195〉; rush: 2: 〈2,66,194,321,702〉; 4: 〈9,69,149,429,569〉; 7: 〈4,14,404〉; to: 2: 〈47,86,234,999〉; 4: 〈14,24,774,944〉; 7: 〈199,319,599,709〉; tread: 2: 〈57,94,333〉; 4: 〈15,35,155〉; 7: 〈20,320〉; where: 2: 〈67,124,393,1001〉; 4: 〈11,41,101,421,431〉; 7: 〈16,36,736〉; 那么哪些文档和以下的查询匹配？其中引号内的每个表达式都是一个短语查询。 a. “fools rush in”。 解答： 文档2、4、7 b. “fools rush in” AND “angels fear to tread”。 解答： 文档4 第三章 词典及容错式检索 习题 3-5　 再次考虑3.2.1节中的查询fi*mo*er，如果采用2-gram索引的话，那么对应该查询应该会 产生什么样的布尔查询？你能否举一个词项的例子，使该词匹配3.2.1节的轮排索引查询，但是 并不满足刚才产生的布尔查询？ 解答： 2-gram索引下的布尔查询：$f AND fi AND mo AND er AND r$ 词项filibuster(海盗)满足 3.2.1节的轮排索引查询，但是并不满足上述布尔查询
    习题 3-7　如果 |si | 表示字符串si的长度，请证明s1和s2的编辑距离不可能超过max{|s1|, |s2|}。 证明：不失一般性，假设|s1|<= |s2|，将s1转换为s2的一种做法为：将s1中的每个字符依次替换为 s2中的前|s1|个字符，然后添加s2的后|s2|-|s1|个字符，上述操作的总次数为|s2|= max{|s1|, | s2|}，根据编辑距离的定义，其应该小于|s2|= max{|s1|, |s2|} 习题 3-8　 计算paris和 alice之间的编辑距离，给出类似于图3-5中的算法结果，其中的5 × 5 矩阵 包含每个前缀子串之间的计算结果。 解答： 57 习题 3-11　考虑四词查询catched in the rye，假定根据独立的词项拼写校正方法，每个词都有5个 可选的正确拼写形式。那么，如果不对空间进行缩减的话，需要考虑多少可能的短语拼写形式 （提示：同时要考虑原始查询本身，也就是每个词项有6种变化可能）？ 解答：6*6*6*6=1296 习题 3-14　找出两个拼写不一致但soundex编码一致的专有名词。 解答：Mary, Mira (soundex相同)，本题答案不唯一，可能有其他答案，但是soundex编码必须一 致。 第四章 索引构建 习题 4-1　 如果需要T log2 T次比较（T是词项ID—文档ID对的数目），每次比较都有两次磁盘寻道 过程。假定使用磁盘而不是内存进行存储，并且不采用优化的排序算法（也就是说不使用前面 提到的外部排序算法），那么对于Reuters-RCV1构建索引需要多长时间？计算时假定采用表4-1 中的系统参数。 解答： 对于Reuters-RCV1，T=108 因此排序时间(文档分析时间可以忽略不计)为：2*(108*log2108)*5*10-3s = 26575424s = 7382 h=308 day 习题 4-3　对于n = 15个数据⽚片，r = 10个分区⽂文件，j = 3个词项分区，假定使⽤用的集 群的机器的参数如表4-1所⽰示，那么在MapReduce构架下对Reuters-RCV1语料进⾏行分布式索 引需要多⻓长时间？ 【给助教：教材不同印刷版本表4-2不⼀一样，不同同学⽤用的不同版本，还有本题过程具 有争议。暂不扣分】
    解答【整个计算过程是近似的，要了解过程】： (一)、MAP阶段【读入语料(已经不带XML标记信息了，参考表5-6)，词条化，写入分区文件】： (1) 读入语料： 基于表4-2，Reuters RCV1共有8*105篇文档，每篇文档有200词条，每个词条(考虑标点和空格)占 6B，因此整个语料库的大小为 8*105*200*6=9.6*108B （近似1GB，注表4-2对应于表5-1第3行的数据，而 那里的数据已经经过 去数字 处理，因此实际的原始文档集大小应该略高于0.96G，这里近似计算，但是 不要认为没有处理就得到表5-1第3行的结果） 将整个语料库分成15份，则每份大小为9.6*108/15 B 每一份读入机器的时间为：9.6*108/15*2*10-8=1.28s (2) 词条化：每一份语料在机器上进行词条化处理，得到8*105*200=1.6*108个词项ID-文档ID对(参考 表4-2和图4-6，注意此时重复的 词项ID-文档ID对 还没有处理)，共占1.6*108*8=1.28*109个字节，词条化 的时间暂时忽略不计【从题目无法得到词条化这一部分时间，从表5-1看词条化主要是做了去数字和大小 写转换，当然也感觉这一部分的处理比较简单，可以忽略】。 (1.28*109/15)*2*10-8=1.71s (3) 写入分区文件：每一份语料得到的词项ID-文档ID (Key-Value)存储到分区所花的时间为： (4) MAP阶段时间： 由于分成15份，但只有10台机器进行MAP操作，所以上述MAP操作需要两步，因此，整个MAP过程所 需时间为 (1.28+1.71)*2=6.0s (二)、REDUCE阶段【读入分区文件，排序，写入倒排索引】： (1) 读入分区文件【读入过程中已经实现所有Key-Value对中的Value按Key聚合，即变成Key, list(V1,V2..)。聚合过程在内存中实现，速度很快，该时间不计。另外，网络传输时间这里也不计算】： 根据表4-2，所有倒排记录的数目为1.6*108，因此3台索引器上每台所分配的倒排记录数目为 1.6*108/3,而每条记录由4字节词项ID和4字节文档ID组成，因此每台索引器上需要读入的倒排记录表数据 为 1.28*109/3字节。 于是，每台索引器读数据的时间为 1.28*109/3*2*10-8=8.5s (2) 排序： 每台索引器排序所花的时间为 1.6*108/3*log2(1.6*108/3)*10-8=13.7s (3) 写入倒排索引文件【此时倒排文件已经实现文档ID的去重，假定只存储词项ID和文档ID列表，并 不存储其他信息(如词项的DF及在每篇文档中的TF还有指针等等)】： 需要写入磁盘的索引大小为(据表4-2，词项总数为4*105个) 4*105/3*4+108/3*4=4/3*108字节 索引写入磁盘的时间为：4/3*108*2*10-8=2.7s (4) REDUCE阶段时间为： 8.5+13.7+2.7=24.9 (三) 因此，整个分布式索引的时间约为6.0+8.5+13.7+2.7=30.9s
    第五章 索引压缩 习题 5-2　 估计Reuters-RCV1文档集词典在两种不同按块存储压缩方法下的空间大小。其中，第一 种方法中k = 8，第二种方法中k = 16。 解答： 每8个词项会节省7*3个字节，同时增加8个字节，于是每8个词项节省7*3-8=13字节，所有词项 共节省13*400000/8=650K，因此，此时索引大小为7.6MB-0.65MB=6.95MB 每16个词项会节省15*3个字节，同时增加16个字节，于是每16个词项节省15*3-16=29字节，所 有词项共节省29*400000/16=725K，因此，此时索引大小为7.6MB-0.725MB=6. 875MB 习题 5-6　考虑倒排记录表（4, 10, 11, 12, 15, 62, 63, 265, 268, 270, 400）及其对应的间 距表（4, 6, 1, 1, 3, 47, 1, 202,3, 2, 130）。假定倒排记录表的长度和倒排记录表分开独立 存储，这样系统能够知道倒排记录表什么时候结束。采用可变字节码： (i) 能够使用1字节来编码的最大间距是多少？ (ii) 能够使用2字节来编码的最大间距是多少？ (iii) 采用可变字节编码时，上述倒排记录表总共需要多少空间（只计算对这些数字序列进行编 码的空间消耗）？ 解答： (i) 27-1=127 (答128也算对，因为不存在0间距，0即可表示间距1，……) (ii) 214-1=16383 (答16384也算对) (iii) 1+1+1+1+1+1+1+2+1+1+2=13 习题 5-8 [*]　对于下列采用γ 编码的间距编码结果，请还原原始的间距序列及倒排记录表。 1110001110101011111101101111011 解答： 1110 001; 110 10; 10 1; 111110 11011; 110 11 1001; 110; 11; 111011; 111 9; 6; 3; 32+16+8+2+1=59; 7 9; 15;18;77;84 第六章 ⽂文档评分、词项权重计算及向量空间模型 习题 6-10　 考虑图6-9中的3篇文档Doc1、Doc2、Doc3中几个词项的tf情况，采用图6-8中的idf值来 计算所有词项car、auto、insurance及best的tf-idf值。 Doc1 Doc2 Doc3 car auto insurance best 27 3 0 14 4 33 33 0 24 0 29 17
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料