Search within ordered words and sentences

“First verb in the third sentence” is an order-sensitive question. Unlike counting or finding a maximum value, it cannot be answered correctly after randomly shuffling the word cards.

A position and a count are different #

The supplied Word table has SerialNumber IDs 0–64. Card 12 is the thirteenth word occurrence. Each full stop is attached to its word, for example morning. and eyes. The first two sentences have 4 and 7 words, so the third begins at card 11.

Keep track of the current sentence #

Set Sentence=1 before reading. For each word, first use the current sentence number to decide whether it is a candidate. After processing that word, if it ends with a full stop, increment Sentence. A word carrying the full stop still belongs to the sentence that just ended.

Sentence = 1
Found = False
Result = NONE
while (cards remain AND NOT Found AND Sentence <= 3) {
    Read next word X in SerialNumber order
    Move X to the visited pile
    if (Sentence == 3 AND X.PartOfSpeech == "Verb") {
        Found = True
        Result = X.SerialNumber
    }
    if (X.Word ends in a full stop) {
        Sentence = Sentence + 1
    }
}

Trace the actual answer #

What if the target does not exist? #

If there are fewer than three sentences, the pile can end without a match. If sentence 3 ends without a recorded verb, the Sentence<=3 guard prevents accepting a verb from sentence 4. Report “not found”. This is more precise than assuming every sentence must have a qualifying labeled verb.

The full-stop rule is the simplified rule for this dataset. Colons and semicolons inside its final sentence do not end the sentence. A general text-processing system would need explicit rules for abbreviations and other ending punctuation.

Source: Lecture 2.1. Small teaching datasets and diagrams are prepared for these notes; lecture and tutorial totals are identified explicitly.