Text Generator
Generate text using a bigram language model with deterministic selection (always pick the most probable next word).
Build a bigram model from training data. Starting from <s>, at each step choose the word with the highest P(w | prev_word). If there is a tie, choose the alphabetically first word. Stop when </s> is generated or max_length words are reached.
Input format:
- Line 1: Number of training sentences N
- Lines 2 to N+1: Training sentences
- Line N+2: max_length (maximum number of generated words, not counting <s>/</s>)
Output: The generated sentence (words only, no <s> or </s>).
Note: Use raw counts (no smoothing) for generation — pick the highest count bigram.
Example:
3 i love nlp i love ml i hate bugs 5
i love ml
Bigram counts from training: (<s>, i): 3 — only option after <s> (i, love): 2, (i, hate): 1 — pick "love" (love, nlp): 1, (love, ml): 1 — tie, pick "ml" (alphabetically first) (ml, </s>): 1 — pick </s>, stop
Generated: "i love ml"
Constraints:
- Start from <s>, pick highest-count next word
- Ties broken alphabetically (smallest word first)
- Stop at </s> or when max_length words generated
- Do NOT include <s> or </s> in output
- Use raw counts (no smoothing) for generation
Background Knowledge
Language Modeling is a fundamental task in Natural Language Processing (NLP) that involves predicting the next word in a sequence of words, given the context of the previous words. A bigram language model is a simple type of language model that predicts the next word based on the previous word. It uses the concept of conditional probability, where the probability of a word w given the previous word prev_word is denoted as P(w∣prev_word). This probability is calculated using the bigram frequency counts, which are the counts of each word pair in the training data.
In this problem, we are using a deterministic selection approach, where we always choose the word with the highest P(w∣prev_word). If there is a tie, we choose the alphabetically first word. This approach is simple and efficient but may not always produce the most coherent or natural-sounding text. Bigram models are often used as a baseline for more complex language models, such as n-gram models or neural language models. Understanding how to build and use bigram models is essential for developing more advanced language models.
The key concepts in this problem include text generation, language modeling, bigram models, and conditional probability. To solve this problem, you need to understand how to calculate bigram frequency counts, how to use these counts to predict the next word, and how to generate text using a deterministic selection approach. You also need to consider how to handle ties and how to stop generating text when a certain condition is met.
Algorithm/Approach
The general approach to solving this problem involves the following steps:
- Build a bigram model from the training data by calculating the frequency counts of each word pair.
- Use the bigram model to predict the next word in the sequence, given the previous word.
- Generate text by iteratively predicting the next word and adding it to the sequence.
- Stop generating text when a certain condition is met, such as reaching the maximum length or generating the </s> token.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.