《信息检索导论》课后习题答案

《信息组织与检索》作业答案第一章布尔检索习题1-2考虑如下几篇文档：文档1breakthroughdrugforschizophrenia文档2newschizophreniadrug文档3newapproachfortreatmentofschizophrenia文档4newhopesforschizophreniapatientsa.画出文档集对应的词项—文档矩阵；b.画出该文档集的倒排索引（参考图1-3中的例子）。Term-Documentmatrix:1234approach0010breakthrough1000drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010InvertedIndex:approach-3breakthrough-1drug-1-2for-1-3-4hopes-4new-2-3-4of-3patients-4schizophrenia-1-2-3-4treatment3注意：倒排索引中的词表（dictionary）和每个词项的倒排列表（postinglist）需要排序，便于查找。这里我们暂不考虑词的正规化处理（如hopes-hope）。补充习题1写出AND查询的伪代码面向过程风格的伪代码：给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId查询结果存放在answer列表里。这里应用了“化归”思想（将新问题转化归为旧问题来解决）。这里，比较两排序列表的首元素，排除较小的docId（不可能有匹配）后，我们构造出新的剩余列表，再次进行两列表的首元素的比较。Whilep1!=nullANDp2!=nullIfp1-docId==p2-docId//对两（剩余）列表的首元素进行比较insert(answer,p1)；p1=p1-next；//构造新的剩余列表，迭代执行p2=p2-next；//Elseifp1-docIdp2-docIdp1=p1-next；//p1-docId不可能有匹配；构造新的剩余列表Elsep2=p2-next；//p2-docId不可能有匹配；构造新的剩余列表End面向对象风格的伪代码：注：为一个数据结构（对象）定义方法，通过方法操作自己的内部数据（List对象里隐含包含了一个成员变量，它是真正的链表或变长数组）。Whilelist1.currentItem()!=nullANDlist2.currentItem()!=nullIflist1.currentItem().getDocId()==list2.currentItem().getDocId()answer.insert(list1.currentItem());list1.moveToNext();list2.moveToNext();Elseiflist1.currentItem().getDocId()list2.currentItem().getDocId()list1.moveToNext();Elselist2.moveToNext();End习题1-10写出OR查询的伪代码面向过程风格的伪代码：给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId；查询结果存放在answer列表里。Whilep1!=nullANDp2!=nullIfp1-docId==p2-docIdinsert(answer,p1)；p1=p1-next；p2=p2-next；//构造新的剩余列表，迭代执行Elseifp1-docIdp2-docIdinsert(answer,p1)；p1=p1-next；//构造新的剩余列表，迭代执行Elseinsert(answer,p2)；p2=p2-next；//构造新的剩余列表，迭代执行EndWhilep1!=null//条件为真时，加入list1的剩余元素（此时list2已遍历到结尾）insert(answer,p1)；p1=p1-next；ENDWhilep2!=null//条件为真时，加入list2的剩余元素（此时list1已遍历到结尾）insert(answer,p2)；p2=p1-next；END面向对象风格的伪代码：Whilelist1.currentItem()!=nullANDlist2.currentItem()!=nullIflist1.currentItem().getDocId()==list2.currentItem().getDocId()answer.insert(list1.currentItem());list1.moveToNext();list2.moveToNext();Elseiflist1.currentItem().getDocId()list2.currentItem().getDocId()answer.insert(list1.currentItem());list1.moveToNext();Elseanswer.insert(list2.currentItem());list2.moveToNext();EndWhilelist1.currentItem()!=nullanswer.insert(list1.currentItem());list1.moveToNext();ENDWhilelist2.currentItem()!=nullanswer.insert(list2.currentItem());list2.moveToNext();END补充习题2若一个文集有1000篇文档，有40篇是关于信管专业建设的。我的信息需求是了解信管专业的专业建设情况，用某搜索引擎在这个文集上搜索，查询词为“信管”，搜出100篇包含“信管”的文档，这其中有20篇是信管专业建设方面的，其它80篇是关于信管的其它情况。请问该查询的正确率和召回率是多少正确率=20/100=0.2召回率=20/40=0.5第二章词项词典及倒排记录表习题2-1a.在布尔检索系统中，进行词干还原从不降低正确率。错；相当于扩充出同一个词干表示的多个词，会降低正确率。b.在布尔检索系统中，进行词干还原从不降低召回率。对。c.词干还原会增加词项词典的大小。错。d.词干还原应该在构建索引时调用，而不应在查询处理时调用。错；应同时做才能保证索引中和查询词的匹配。习题2-2请给出如下单词的归一化形式（归一化形式也可以是词本身）。a.’Cos-cosb.Shi’ite-shiite（'是隔音号）c.cont’d-contd（contd.可表示contained包括；continued继续）d.Hawai’i-hawaiie.O’Rourke-orourke习题2-3如下词经过Porter词干还原工具处理后会输出同样的结果，你认为哪对（几对）词不应该输出同样的结果？为什么？a.abandon/abandonmentb.absorbency/absorbentc.marketing/marketsd.university/universee.volume/volumes按Porter词干还原算法，这几组词都可以被还原为相应的词干。但是这里问的是哪些组做词干还原不合适，原因是某组的两个词虽然来源于同一个词干，但是它们的意思不同，如果做词干还原处理会降低正确率。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,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)。共比较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,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.“foolsrushin”；文档2、4、7。b.“foolsrushin”AND“angelsfeartotread”。文档4。补充习题1k词邻近AND合并算法前提：考虑位置索引。要求查找这样的文档，它同时包含词A和词B，且两词文中的距离在k个词以内。给定两个指针p1和p2，分别指向两个词A和B的两倒排列表（链表实现）的首元素；令pi-doc表示pi所指向文档对象的结构体。对于一个文档对象，该词出现的各个位置的列表为posList。用q1（q2）表示词A（词B）当前指向文档对象指向的posList指向的位置。用qi-pos表示该位置。查询结果存放在answer列表里。算法：Whilep1!=nullANDp2!=nullIfp1-docId==p2-docId//对两（剩余）列表的首元素进行比较Whileq1!=nullANDq2!=nullIfq1-pos–q2-pos=kORq2-pos–q1-pos=kinsert(answer,p1);break;//跳出这个循环，找到一个k临近即可ElseIfq1-pos–q2-posk//q2不可能被匹配上，忽略它q2=q2-next;//生成新的剩余列表ElseIfq2-pos–q1-posk//q1不可能被匹配上，忽略它q1=q1-next;//生成新的剩余列表EndIfEndWhilep1=p1-next;//构造新的剩余列表，迭代执行p2=p2-next;Elseifp1-docIdp2-docIdp1=p1-next；//p1-docId不可能有匹配；构造新的剩余列表Elsep2=p2-nex