N-Gram Generator

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.