N-Gram Generator

easyFREEText ProcessingNLP 1: Foundations

Generate word-level n-grams from a given text.

An n-gram is a contiguous sequence of n items from a given text. For word-level n-grams, the items are words.

Function: generate_ngrams(text, n)

text: the input string
n: the size of each n-gram (integer)

Output: A list of tuples, where each tuple contains n consecutive words.

Example:

Text: "I love natural language processing"
n = 2 (bigrams)
Output: [('I', 'love'), ('love', 'natural'), ('natural', 'language'), ('language', 'processing')]

Note: Do NOT lowercase the words — preserve original casing.

Example

Input

I love natural language processing
2

Output

[('I', 'love'), ('love', 'natural'), ('natural', 'language'), ('language', 'processing')]

Reasoning

Input: text is a sentence whose words are separated by whitespace, and n is how many consecutive words each n-gram holds. Here the text has $5$ words: $w_1 =$ I, $w_2 =$ love, $w_3 =$ natural, $w_4 =$ language, $w_5 =$ processing, and $n = 2$ .
Math: the n-gram starting at word $k$ is the ordered group $(w_k, w_{k+1}, \dots, w_{k+n-1})$ . It only exists if its last word $w_{k+n-1}$ is still inside the text, so $k$ runs from $1$ to $L - n + 1$ , where $L$ is the word count.
With $L = 5$ and $n = 2$ there are $5 - 2 + 1 = 4$ bigrams: $(w_1, w_2), (w_2, w_3), (w_3, w_4), (w_4, w_5)$ .
Output: those tuples in order of starting position, casing preserved: [('I', 'love'), ('love', 'natural'), ('natural', 'language'), ('language', 'processing')].
Notice that neighbouring n-grams overlap in $n - 1$ words, so every middle word appears twice. For $n = 3$ the count drops to $3$ , and for $n = 1$ each word becomes its own one-element tuple.

Constraints

Input text contains at least n words
1 <= n <= 5
Words are split on whitespace
Preserve original casing
Output is a list of tuples

Learn this in

Introduction to NLPNLP Study Plan Text RepresentationNLP Study Plan

More from NLP 1: Foundations

Embedding Lookupeasy Cosine Similarity Calculatoreasy Binary Vectorizereasy Document Term Matrixeasy Character Frequency Countereasy

Concept primer

Background Knowledge

The concept of n-grams is fundamental in Natural Language Processing (NLP). An n-gram is a sequence of n items from a given text. In the context of word-level n-grams, these items are words. N-grams are used in various NLP applications, such as language modeling, text classification, and information retrieval. Understanding n-grams requires familiarity with basic text processing techniques, including tokenization, which is the process of splitting text into individual words or tokens.

The value of n determines the size of the sequence. For example, when n = 2, we are dealing with bigrams, which are sequences of two consecutive words. Similarly, when n = 3, we have trigrams, which are sequences of three consecutive words. The choice of n depends on the specific application and the level of detail required. In general, larger values of n capture more context but may also increase the complexity of the model.

In the context of this problem, we need to generate word-level n-grams from a given text while preserving the original casing of the words. This means that we should not convert all words to lowercase, as this could alter the meaning or context of the text. Instead, we should maintain the original casing of each word as it appears in the input text.

Algorithm/Approach

The general approach to solving this problem involves using a sliding window technique. This technique is commonly used in array or string processing problems where we need to consider a fixed-size window of elements. In this case, the window size is determined by the value of n. We will iterate through the list of words in the text, maintaining a window of n consecutive words at each step.

Step-by-Step Strategy

To implement the solution, follow these steps:

Split the input text into a list of words using tokenization.
Initialize an empty list to store the generated n-grams.
Iterate through the list of words, considering a window of n consecutive words at each step.
At each step, extract the current window of n words and add it to the list of n-grams.
Continue iterating until the window can no longer be moved forward without exceeding the bounds of the list.

Common Pitfalls

When implementing the solution, watch out for the following:

Ensure that the window size is correctly set to the value of n.
Handle the case where the input text is empty or contains fewer than n words.
Be careful when iterating through the list of words to avoid index out-of-bounds errors.

Time & Space Complexity

The expected time complexity is $O(m)$ , where $m$ is the number of words in the input text. This is because we are iterating through the list of words once, performing a constant amount of work at each step. The space complexity is also $O(m)$ , as we need to store the generated n-grams in a list. However, the actual space complexity may be less than $O(m)$ if the value of n is small compared to the number of words in the text.

solution.py

Python 3.13

Test results