Hello, dear friend, you can consult us at any time if you have any questions, add  WeChat:  zz-x2580

Q1. (25 marks)

Some Boolean retrieval systems (e.g., Westlaw) support the proximity operator /S, which

restricts the occurrences matches to be within the same sentence.

Assume that we have created an additional positional list for $, which records the positions

of the end of the sentences. E.g., for the document

A B C. D E.

the position list for $ is [4, 7].

You are required to engine an algorithm to support the query A /S B. To make the task

easier, we further constrain the semantics of the query to satisfy both conditions:

? the occurrences of A and B must be within the same sentence.

? the occurrence of A must precede that of B.

For example, the above example document matches the query A /S C, but not C /S A.

You need to

? make simple modifications to the pseudocode shown in Algorithm 1, which is exactly

the algorithm in Figure 2.12 in the textbook. Note that we modify the

algorithm slightly so that array indexes start from 1 instead of 0. Specifically,

– you need to insert some code between Lines 6 and 7, and perform some modifications

to some lines afterwards.

– In your submitted algorithm pseudocode (named Q1(p1, p2, p$

)), clearly mark

the modifications using color or boxes.

? You can assume that there is a function skipTo(p, docID, pos), which move the

cursor of list p to the first position such that (1) the position belongs to a document

docID, and (2) the position is no smaller than pos.