ITPEC FE Subject B April 2024 Question 15

Topic: String Processing

From the answer group below, select the correct combination of answers to be inserted into A and B in the program. Here, the array index starts at 1.

N-grams are continuous sequences of words, symbols, or tokens in a document. N-grams of texts are extensively used in text mining and natural language processing tasks. An n-gram model is built by counting how often word sequences occur in corpus text and then estimating the probabilities. The figure shows an example of the unigrams, bigrams, and trigrams of the example sentence “ITPEC includes members from 6 countries.”

unigramITPECincludesmembersfrom6countriesbigramITPEC includesincludes membersmembers fromfrom 66 countriestrigramITPEC includes membersincludes members frommembers from 6from 6 countries

Figure Example of unigrams, bigrams, and trigrams

The procedure NGRAMS generates n-grams from text and outputs them. If the argument for n is 1, the procedure outputs the unigram result. If n is 2, the procedure outputs the bigram result and so on. The input text is a string of words separated by a space, so it is needed to split the string to generate n-grams. The table shows the description of the functions used in the program. In this question, the operator “+” is used for both arithmetic calculation of integer data type and concatenation of one or more strings into one string. In the program, areas outside of the array must not be referenced.

Table Functions

FunctionReturn valueDescription
split(string: str)string []Returns the words that are separated with a space in the text str
[Program]
○ NGRAMS(integer: n, string: text)
string []: words ← split(text)
string: s
integer: i, j, length
length ← the number of elements in words
for (increase i from 1 to (A) by 1)
s ← ""
for (increase j from i to (B) by 1)
s ← s + words[j] + " "
endfor
output s
endfor

Answer group

OptionAB

Explanation

A: length - n + 1, B: i + n - 1 — an n-gram can start at any word that leaves room for n words, and it runs for exactly n words from its start.

The outer loop picks the first word i of each n-gram and the inner loop joins the words from i on. An n-gram of n words starting at i ends at i + n - 1, so blank B is i + n - 1. The last n-gram must end at words[length], so it starts at length - n + 1, blank A; any later start would read past the end of the array, which the question forbids.

Trace for the example sentence (length = 6) and trigrams (n = 3), where i runs from 1 to 4:

  • •i = 1: words 1 to 3, "ITPEC includes members"
  • •i = 2: words 2 to 4, "includes members from"
  • •i = 3: words 3 to 5, "members from 6"
  • •i = 4: words 4 to 6, "from 6 countries"

These are the four trigrams of the figure.

Answer (i)

Why not others:

  • •(a), (b) and (c) — A as length also starts n-grams at the last words; in (c) the inner loop then reads words[7] and beyond, outside the array
  • •(d), (e) and (f) — A as length - n stops one start too early and loses the last n-gram, "from 6 countries"
  • •(a), (d) and (g) — B as n ends every n-gram at word n whatever its start, so for trigrams (g) prints "ITPEC includes members", "includes members", "members" and then an empty string
  • •(b), (e) and (h) — B as i + n joins n + 1 words, one too many, and in (b) and (h) the last n-gram reads one position past the end of the array

Key rule: For windows of size n over L items, start positions run from 1 to L - n + 1 and the window starting at i ends at i + n - 1; check both bounds on the last window.

String Processing · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.