Text Generator

hardPROLanguage ModelingNLP 3: Advanced

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:

train_sents: a list of N training sentences (strings of space-separated words)
max_len: the maximum number of generated words, not counting <s>/</s>

Output: The generated sentence as a string (words separated by single spaces, no <s> or </s>).

Note: Use raw counts (no smoothing) for generation — pick the highest count bigram.

Example

Input

3
i love nlp
i love ml
i hate bugs
5

Output

i love ml

Reasoning

Inputs: train_sents holds three sentences, each padded as $\langle s\rangle\ w_1 \dots w_n\ \langle /s\rangle$ , so every sentence contributes one bigram per adjacent pair. max_len $= 5$ caps the number of words produced.
After the start token: all three sentences begin with "i", so $c(\langle s\rangle, \text{i}) = 3$ is the only option. First word: "i".
After "i": $c(\text{i}, \text{love}) = 2$ beats $c(\text{i}, \text{hate}) = 1$ , so $P(\text{love} \mid \text{i}) = 2/3$ wins. Second word: "love".
After "love": $c(\text{love}, \text{nlp}) = c(\text{love}, \text{ml}) = 1$ , a tie at $P = 1/2$ . Alphabetically "ml" comes before "nlp", so it is chosen.
After "ml": the only continuation is the end token with $c = 1$ , so generation stops after 3 words, well under the cap of 5. Output: i love ml.
Notice the output is a sentence that never appears in training: greedy choices made locally can stitch together pieces of different sentences. With max_len $= 2$ the same walk would be cut off at "i love".

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

More from NLP 3: Advanced

Temperature Samplereasy ROUGE-1 Score Calculatoreasy Context Window Findereasy Keyword Answer Extractoreasy Levenshtein Distanceeasy

Concept primerPREVIEW

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.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results