This page describes the central function of the [:../:ExcerptGenerator]. It first gives a detailed requirement specification, together with a running example. Then it describes the implementation.

Requirements

Anchor(Terminology)

Terminology and basic task

A document D trivially consists of positions

D = (0,1,2,3,4,5,6,7,8,9,10,...).

Each position holds the code of a word or a non-word. By a lookup in a dictionary, each position can be mapped to its corresponding word or non-word, so that the document can easily be (re-)constructed from its positions. The following algorithmic description mostly deals with positions, that is, with integers, not with words (strings). It suffices to bear in mind that the positions can easily be translated into the corresponding words if needed. Conversely, each word or non-word gives rise to a list of positions: the positions at which this word occurs in the document.

Each document is (conceptually) divided into segments, that is, into intervals of positions. For example, the segments may be the sentences of the document. The two extreme cases of segmentation are:

The whole document is one single segment.
Each word is a segment of its own.

For example, D could be segmented at the segment bounds

SB = (0,5,10,15,20,25,...),

Each segment bound (which is a position) starts a new segment, that is, the document D is segmented into the segments

S = ([0,4],[5,9],[10,14],[15,19],[20,24],...).

A list L of positions is called a position list. In general, a position list describes a set of words, each being located in a (not necessarily different) segment of the document. Such a segment is said to match the position (i.e., the word) and conversely the position (the word) is said to match the segment.

For example, with the position list

L₀ = (6,7,12)

the matching segments are

([5,9],[10,14]).

The basic task of the central function is the following: Given the segmentation S of the document and some position lists L₀, L₁,..., the function computes all segments that match at least one of the positions in one of the L_i.

For example, with the additional position lists

L₁ = (8,11,21)

L₂ = (5,10,22)

the matching segments are:

([5,9],[10,14],[20,24]).

For each segment matching a position in one of the L_i, the function returns all words the segment consists of. If desired, the matching positions (i.e., the words) are highlighted. If more than one matching position is contained in a segment, this segment is not returned twice. Rather, with highlighting enabled, the matching positions in this segment coming from a different position list are given a different highlighting.

In the running example, with highlighting enabled and * being the highlighting for L₀, + for L₁, and $ for L₂, the function would return the following parts (of course, words are returned, not integers):

($5$,*6*,*7*,+8+,9), ($10$,+11+,*12*,13,14), (20,+21+,$22$,23,24).

So a part is defined to be the positions (words) of a matching segment, maybe augmented by highlighting markup.

The final output of the central function is a (string) concatenation of all parts computed, divided by a separator from one another (e.g., "..."). This output is called the excerpt.

In the example, the excerpt returned would be

$5$ *6* *7* +8+ 9 ... $10$ +11+ *12* 13 14 ... 20 +21+ $22$ 23 24

Input

Remark: Some of the following parameters should not be passed as arguments to the function, but rather be members of the object representing an [:../:ExcerptGenerator].

A document D (type Document).
A list of position lists (type vector<vector<Position>>).
The radius (type unsigned int): specifies how many segments around a matching segment should additionally go into the corresponding part. The default is 0, that is, only the matching segment. With radius 1, the segments one to the left and one to the right become also part of the part etc.
maxPartSize (type unsigned int): the maximum size of a part, measured in characters; has priority over the radius; see below.
maxNumOfParts (type unsigned int): specifies the maximum number of parts of the excerpt.
partsSeparator (type string): the separator string dividing the parts of the excerpt.
doHighlighting (type bool): specifies whether the words at the matching positions shall be highlighted.
highlighingTags (type vector<pair<string, string>>): a list of pairs of start and end tags for highlighting markup, such as the pair (<b style="color:red">,</b>); used to highlight words on matching positions; each position list is assigned a new pair from highlightingTags; if there are more position lists than the vector has elements, the highlighting markup is cyclically repeated.

Output

For the output, the excerpt is computed as explained in the section [#Terminology Terminology and basic task], with the following additional requirements:

The excerpt contains up to maxNumOfParts parts. The parts should contain positions from the position lists in shares as equal as possible. In particular, if maxNumOfParts is larger than the number of position lists, for each list at least one part with a position in this list should go into the excerpt. Parts located near the start of the document have priority over parts located near the end.
Parts must be augmented to the left and to the right according to the value of the radius.
Adjacent parts should not be separated with the partsSeparator. Thus, in the example, the output should be $5$,*6*,*7*,+8+,9,$10$,+11+,*12*,13,14...20,+21+,$22$,23,24
If maxPartSize is less than the part computed according to the radius (this may occur even with radius=0, i.e., the matching segment itself is too long), a shorter string shall be output instead of the part, computed as follows: Compute the substring of the part that begins with the leftmost matching position (word) and ends with the rightmost matching position. If this substring is still longer than maxPartSize allows, output it anyway. If it is shorter, expand it to the left and to the right by as many characters as maxPartSize allows in addition.
If the same word is to be highlighted because it matches in different position lists, the highlighting for position list i has priority over position list j if i < j.

The overall output then is the title of the document followed by the excerpt.

Implementation

TODO: This section is preliminary stuff. It depends heavily on the interface of class Document.

The class Document has a method getSegmentBounds(), which returns a list of positions. A position is an unsigned int, see Globals.h. For testing purposes, it suffices a preliminary, trivial implementation that segments every document into segments of length 5, that is, into the segments ([0,4],[5,9],[10,14],[15,19],[20,24],...).

Implementation study and discussion

There is an example implementation at /KM/usr/ziegler/ExGen/CentralFunction/main.cpp, which may serve us as a starting point for dicussions about the final requirements and the final implementation. It computes the above example output.

The main architectural decision is: By what is the main loop driven? There are 3 approaches:

By matching positions (as in the example implementation): The matching positions are drawn out of a PQ one by one, the matching segments are computed based on the current matching position.
By segment bounds: Step through the document segment for segment, test whether the current segment contains a matching postion. If so, output the segment.
By positions: Step through the doument by enumerating all positions 1,2,3,4... For each position, test whether it is a matching position. If so, proceed as in step 1.

Which of these approaches is the most efficient is not fully clear.

Moreover, it is not fully clear whether to insist on and how to implement the following requirements, and what the best approach from 1,2,3 above is to implement them:

Considering the radius

Let SB = (0,5,10,15,20,25,...) and L₀=(11,13,16). Additionally, let the radius be 1. Then the parts computed should read

(5,6,7,8,9)(10,*11*,12,*13*,14)(15,*16*,17,18,19)

How do we get this? Assume the implementation is matching-position-driven (as in the example implementation). Then

Pop 11 from the PQ
Go to the left until you reach the segment bound 9)(10
Go further to the left until you reach the next segment bound (radius=1)
Output everything from this bound to 11
Output *11* (highlighted)
Go to the right and output everything until you reach the next but one segment bound (radius=1). While going to the right, pop 13 and 16 from the PQ; output them highlighted.
"Going to the left and right" means stepping by whole segments, not by single positions, consuming all matching positions from the PQ that are located in segments that you step through.

Now let L₀=(11,13,16,21). When 21 is drawn from the PQ, with radius=1, the above processing would output the part

(15,*16*,17,18,19)

again.

Is this to be avoided? If so, how? What shall be output in this case?

Considering maxPartSize

The above definition of how to output parts with at most maxPartSize characters seems hard to be implemented efficiently. Moreover, it would imply that, by cutting at character bounds, only sussbtrings of words could be output at each end of the part. Is this desirable?

Another approach is to define maxPartSize as the maximum size of a part, measured in words. With this definition, let L₀=(11,13,16), maxPartSize=9. Then the first parts output is

7,8,9)(10,*11*,12,*13*,14)(15

How do we get this? Assume the implementation is matching-position-driven (as in the example implementation). Then

Pop 11 from the PQ
Go to the left 4 words (4 = int(9/2) )
Output everything from this bound to 11
Output *11* (highlighted)
Go to the right 4 words and output everything. While going to the right, pop 13 from the PQ; output it highlighted.
"Going to the left and right" means stepping by single positions, consuming all matching positions from the PQ that are located in segments that you step through.

In this approach, the concept of segment bounds (and radius) is completely irrelevant unless the rule is to always output whole segment. If so, we could, after the 4 steps, go further to the left and to the right until we reach the next segment bound. This still would make the concept of the radius irrelevant.