《信息检索导论》习题解答手册

4星 · 超过85%的资源需积分: 35 171 浏览量更新于2024-07-27 23 收藏 1.4MB PDF 举报

"Introduction to Information Retrieval Solution-Manual" 这篇文档是《信息检索导论》一书的习题答案，由Christopher D. Manning、Prabhakar Raghavan和Hinrich Schütze合著，被卡内基梅隆大学（cmu）和斯坦福大学用作信息检索课程的入门教材。此版本为英文初步草案，警告读者未经许可不得传播。《信息检索导论》是信息科学领域的经典著作，涵盖了信息检索的基本理论、技术和应用。这本书深入浅出地介绍了信息检索系统的工作原理，包括文本表示、查询处理、检索模型以及评估方法。习题答案部分由学生提供，虽然大部分已经被作者检查过，但可能还存在一些未经核实的答案，鼓励读者发现错误或提出改进建议，可以通过电子邮件informationretrieval@yahoogroups.com进行反馈。在信息检索领域，关键知识点包括： 1. **文本表示**：这是将非结构化文本转换为计算机可理解形式的过程，常见的方法有词袋模型（Bag-of-Words）、TF-IDF（词频-逆文档频率）和词向量模型（如Word2Vec、GloVe）。 2. **查询处理**：包括查询分析（query analysis），如拼写纠错、同义词扩展和查询改写，以及查询排序（query ranking），常使用布尔模型、TF-IDF、概率模型（如BM25）和语义模型（如LSI、LDA）。 3. **检索模型**：包括布尔检索、排名检索（如TF-IDF和BM25）、概率检索模型（如语言模型）和基于深度学习的检索模型，如Transformer-based检索系统。 4. **评估方法**：如查准率（Precision）、查全率（Recall）、F1分数以及平均准确率均值（MAP）等，用于衡量检索系统的性能。此外，还有TREC（Text REtrieval Conference）组织的评估标准和任务。 5. **信息检索系统**：包括搜索引擎的工作流程，如爬虫（Web Crawler）、索引构建（Indexing）、查询处理（Query Processing）和结果返回（Result Ranking）等。 6. **用户交互**：理解用户的查询意图，提供相关性和满意度高的搜索结果，包括用户查询日志分析和个性化检索。这本书的习题答案对于学习者来说是宝贵的资源，可以帮助他们检验理解，深化对信息检索理论和技术的理解，并且通过解答习题来提升实际操作技能。由于内容未经彻底审核，读者在使用时应谨慎对待，并积极参与讨论和反馈，以获取更准确的知识。

xviii The term vocabulary and postings lists

SOLUTION. It’s an O(Pk L

max

) algorithm.

Keep a moving window of postings w

for one of the lists. Add next postings

to end of window if there is no match. After adding a posting, check for

all postings in the other window if they meet the proximity constraint. If

yes, add them to the result set. Delete the ﬁrst posting of the window, if its

proximity to the last posting in the other window is below k.Therecanbe

at most k entries in the window. Each new posting is compared to at most k

entries. Thus, this algorithm is O

(k(S

+ S

)).Soproximityqueriescanbe

handled in linear time.

c. If cf

< k then one can simply test the cf

×cf

possible posting pairs to

see if they are within k.

Exercise 0.26 []

Supposewewishtouseapostingsintersectionproceduretodeterminesimplythe

list of documents that satisfy a /k clause, rather than returning the list of positions,

as in Figure 2.12 (page 42). For simplicity, assume k

≥ 2. Let L denote the total

number of occurrences of the two terms in the document collection (i.e., the sum of

their collection frequencies). Which of the following is true? Justify your answer.

a. The merge can be accomplished in a number of steps linear in L and independent

of k, and we can ensure that each pointer moves only to the right.

b. The merge can be accomplished in a number of steps linear in L and independent

of k, but a pointer may be forced to move non-monotonically (i.e., to sometimes

back up)

c. The merge can require kL steps in some cases.

SOLUTION. The merge can determine /k in L monotonic moves. (If the

pointers’ positions do not satisfy the /k clause, advance the pointer currently

pointing to the smaller position in the document, and repeat.)

Exercise 0.27 []

How could an IR system combine use of a positional index and use of stop words?

What is the potential problem, and how could it be handled?

SOLUTION.

Is the problem referred to in this question is the problem faced in construct-

ing the positional index after removal of stop words as this preprocessing

changes the positions of terms in the original text? As far as the ﬁrst part

of the question is concerned, can you give a hint of what kind of use is the

question looking for? I am assuming the answer of the question is not the

following: Phrasal queries can handled using both of them. For any query,

remove the stop-words and merge the positional indexes of the remaining

terms looking for exact phrasal match by determining relative positions.

xxi

SOLUTION. Jaccard (query, t) 1. A = set of k-grams of t 2. B = set

of k-grams of query 3. count=0 4. for i = 1 to length(B) 5. list = post-

ingslist of B[i] 6. if (list contains t) 7. count++ 8. Jaccard co-efﬁcient =

count/(length(A)+length(B)-count)

Exercise 0.37

Compute the Jaccard coefﬁcients between the query

bord and each of the terms in

Figure 3.7 that contain the bigram

or.

SOLUTION.

3.6 Jaccard co-efﬁcients between the following terms:

a. bord and border : 3/5 b. bord and lord : 2/4 c. bord and morbid : 1/7 d.

bord and sordid : 2/6

Exercise 0.38

Consider the four-term query

catched in the rye and suppose that each of the query

terms has ﬁve alternative terms suggested by isolated-term correction. How many

possible corrected phrases must we consider if we do not trim the space of corrected

phrases, but instead try all six variants for each of the terms?

SOLUTION. 6*6*6*6 = 1296

Exercise 0.39

For each of the preﬁxes of the query —

catched, catched in and catched in the —wehave

a number of substitute preﬁxes arising from each term and its alternatives. Suppose

that we were to retain only the top 10 of these substitute preﬁxes, as measured by

its number of occurrences in the collection. We eliminate the rest from consideration

for extension to longer preﬁxes: thus, if

batched in is not one of the 10 most common

2-term queries in the collection, we do not consider any extension of

batched in as pos-

sibly leading to a correction of

catched in the rye. How many of the possible substitute

preﬁxes are we eliminating at each phase?

SOLUTION. At catched in, we choose 10 out of 36 possible thus eliminat-

ing 26. At catched in the, out of 60 surviving alternatives, we eliminate 50 of

these, and at catched in the rye, we eliminate 50 of the surviving alternatives.

Exercise 0.40

Are we guaranteed that retaining and extending only the 10 commonest substitute

preﬁxes of

catched in will lead to one of the 10 commonest substitute preﬁxes of catched

in the

SOLUTION. No. None of the 10 commonest substitute preﬁxes of catched

may lead to a phrase with catchedinthe.

Exercise 0.41

Find two differently spelled proper nouns whose soundex codes are the same.

剩余118页未读，继续阅读

xujieqwe

粉丝: 2
资源: 1

《信息检索导论》习题解答手册

An Introduction to Information Retrieval 信息检索lucene

An Introduction to Information Retrieval

Introduction to Information Retrieval-2009

Information-Retrieval---CS6200:信息检索

introduction to information retrieval

Introduction to Information retrieval

Introduction to Information Retrieval

Introduction To Information Retrieval

Information Retrieval Toolkit-开源

an introduction to information retrieval

最新资源