《《信息检索导论》课后习题答案》由会员分享，可在线阅读，更多相关《《信息检索导论》课后习题答案（13页珍藏版）》请在金锄头文库上搜索。
1、信息组织与检索作业答案第一章 布尔检索习题 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. 画出文档集对应的词项文档矩阵；b. 画出该文档集的倒排索引（参考图 1-3 中的例子） 。Term-Documentmatrix:1 2 3 4approach 0 0 1 0breakthrough 1
2、 0 0 0drug 1 1 0 0for 1 0 1 1hopes 0 0 0 1new 0 1 1 1of 0 0 1 0patients 0 0 0 1schizophrenia 1 1 1 1treatment 0 0 1 0Inverted Index: approach - 3 breakthrough -1 drug -1-2 for -1-3-4 hopes -4 new -2-3-4 of -3 patients -4 schizophrenia -1-2-3-4treatment 3注意：倒排索引中的词表（dictionary ）和每个词项的倒排列表（ posting li
3、st）需要排序，便于查找。这里我们暂不考虑词的正规化处理（如 hopes-hope） 。补充习题 1写出 AND 查询的伪代码 面向过程风格的伪代码：给定两个指针 p1 和 p2，分别指向两倒排列表 list1 和 list2（链表实现）的首元素；令docId(p1)表示 p1 所指向的元素的 docId 查询结果存放在 answer 列表里。这里应用了“化归”思想（将新问题转化归为旧问题来解决） 。这里，比较两排序列表的首元素，排除较小的 docId（不可能有匹配）后，我们构造出新的剩余列表，再次进行两列表的首元素的比较。While p1 != null AND p2 != nullIf p
4、1-docId=p2-docId /对两（剩余）列表的首元素进行比较insert(answer, p1)；p1=p1-next；/构造新的剩余列表，迭代执行p2=p2-next；/Else if p1-docId docIdp1=p1-next； /p1-docId 不可能有匹配；构造新的剩余列表Elsep2=p2-next； /p2-docId 不可能有匹配；构造新的剩余列表End 面向对象风格的伪代码：注：为一个数据结构（对象）定义方法，通过方法操作自己的内部数据（List 对象里隐含包含了一个成员变量，它是真正的链表或变长数组） 。While list1.currentItem() !=
5、 null AND list2.currentItem() != nullIf list1.currentItem().getDocId() = list2.currentItem().getDocId()answer.insert(list1.currentItem();list1.moveToNext();list2.moveToNext();Else if list1.currentItem().getDocId() docId = p2-docIdinsert(answer, p1)；p1=p1-next；p2=p2-next； /构造新的剩余列表，迭代执行Else if p1-doc
6、Id docIdinsert(answer, p1)；p1=p1-next； /构造新的剩余列表，迭代执行Elseinsert(answer, p2)；p2=p2-next； /构造新的剩余列表，迭代执行EndWhile p1 != null/条件为真时，加入 list1 的剩余元素（此时 list2 已遍历到结尾）insert(answer, p1)；p1=p1-next；ENDWhile p2 != null/条件为真时，加入 list2 的剩余元素（此时 list1 已遍历到结尾）insert(answer, p2)；p2=p1-next；END 面向对象风格的伪代码：While lis
7、t1.currentItem() != null AND list2.currentItem() != nullIf list1.currentItem().getDocId() = list2.currentItem().getDocId()answer.insert(list1.currentItem();list1.moveToNext();list2.moveToNext();Else if list1.currentItem().getDocId() cosb. Shiite - shiite（ 是隔音号）c. contd -contd（contd. 可表示 contained 包括
8、；continued 继续）d. Hawaii -hawaiie. ORourke -orourke习题 2-3如下词经过 Porter 词干还原工具处理后会输出同样的结果，你认为哪对（几对）词不应该输出同样的结果？为什么？a. abandon/abandonment b. absorbency/absorbent c. marketing/markets d. university/universe e. volume/volumes按 Porter 词干还原算法，这几组词都可以被还原为相应的词干。但是这里问的是哪些组做词干还原不合适，原因是某组的两个词虽然来源于同一个词干，但是它们的意思不
9、同，如果做词干还原处理会降低正确率。c 组不做词干还原。marketing 表示营销，market 表示市场。d 组不做词干还原。university 表示大学，universe 表示宇宙。习题 2-6对于两个词组成的查询，其中一个词（项）的倒排记录表包含下面 16 个文档 ID：4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180 而另一个词（项）对应的倒排记录表仅仅包含一个文档 ID：47 请分别采用如下两种策略进行倒排记录表合并并计算所需要的比较次数，同时简要地说明计算的正确性。a. 使用标准的倒排记录表。比较：(4,47), (6,47),
10、 (10,47), (12,47), (14,47), (16,47), (18,47), (20,47), (22,47), (32,47), (47,47)。共比较 11 次。b. 使用倒排记录表+跳表的方式，跳表指针设在 P1/2 处（P 是列表长度） 。P=16。也就说第一个列表的跳表指针往后跳 4 个元素。下图蓝色表示安装了跳表指针的元素，其中 120 跳到 180 上。4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180 比较：(4,47), (14,47), (22,47), (120,47), (32,47), (47,47)。共比
11、较 6 次。习题 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,1
12、10,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 ）; 那么哪些文档和以下的查询匹配？
13、其中引号内的每个表达式都是一个短语查询。a. “fools rush in”；文档 2、4 、7。b. “fools rush in” AND “angels fear to tread”。文档 4。补充习题 1k 词邻近 AND 合并算法前提：考虑位置索引。要求查找这样的文档，它同时包含词 A 和词 B，且两词文中的距离在 k 个词以内。给定两个指针 p1 和 p2，分别指向两个词 A 和 B 的两倒排列表（链表实现）的首元素；令 pi-doc 表示 pi 所指向文档对象的结构体。对于一个文档对象，该词出现的各个位置的列表为 posList。用 q1（q2 ）表示词 A（词B）当前指向文档对
14、象指向的 posList 指向的位置。用 qi-pos 表示该位置。查询结果存放在 answer 列表里。算法：While p1 != null AND p2 != nullIf p1-docId = p2-docId /对两（剩余）列表的首元素进行比较While q1 != null AND q2 != nullIf q1-posq2-pospos q1-pos pos q2-pos k /q2 不可能被匹配上，忽略它q2= q2-next;/生成新的剩余列表Else If q2-pos q1-pos k /q1 不可能被匹配上，忽略它q1=q1-next;/生成新的剩余列表End IfEn
15、d Whilep1=p1-next; /构造新的剩余列表，迭代执行p2=p2-next;Else if p1-docId docIdp1=p1-next； /p1-docId 不可能有匹配；构造新的剩余列表Elsep2=p2-next； /p2-docId 不可能有匹配；构造新的剩余列表End第六章 文档评分、词项权重计算及向量空间模型习题 6-2上面的例 6-1 中，如果 g1 = 0.2, g2 = 0.31 及 g3 = 0.49，那么对于一个文档来说所有可能的不同得分有多少？得分 1: 0得分 2：g1=0.2得分 3：g2=0.31得分 4：g3=0.49得分 5：g1+g2=0.5
16、1得分 6：g1+g3=0.69得分 7：g2+g3=0.8得分 8：g1+g2+g3=1.0习题 6-10考虑图 6-9 中的 3 篇文档 Doc1、Doc2、Doc3 中几个词项的 tf 情况，采用图 6-8 中的 idf值来计算所有词项 car、auto、insurance 及 best 的 tf-idf 值（这里改为 df 值的计算就假设用 Doc1, Doc2 Doc3 的这个文集 ） 。解答：wt,d=max(1+log10(1+tf),0)Doc1 Doc2 Doc3Car 2.4314 1.6021 2.3802Auto 1.4771 2.5185 0insurance 0 2.5185 2.4624Best 2.1461 0 2.2304dft idftcar 3 0auto
