Bigram Probability Calculator

easyFREELanguage ModelingNLP 3: Advanced

Given a corpus of text, compute bigram probabilities.

A bigram probability is P(word2 | word1) = count(word1, word2) / count(word1), where count(word1, word2) is the number of times word2 immediately follows word1, and count(word1) is the number of bigrams whose first word is word1 (an occurrence of word1 as the very last word of the corpus starts no bigram, so it is not counted).

Input format:

corpus: the training corpus (a single line of lowercase text, words separated by spaces)
w1, w2: the first and second word of the bigram to query

Round the probability to 4 decimal places.

Output: The bigram probability as a float. If w1 never starts a bigram, return 0.0.

Example

Input

the cat sat on the mat
the cat

Output

0.5

Reasoning

Inputs: corpus is the text "the cat sat on the mat" (6 words), and the query is w1 = "the", w2 = "cat". We want $P(\text{cat} \mid \text{the})$ : how often "cat" comes right after "the".
Bigrams: every pair of adjacent words. A text of $n$ words has $n - 1$ of them, so here there are 5: (the, cat), (cat, sat), (sat, on), (on, the), (the, mat).
Denominator: bigrams whose first word is "the" are (the, cat) and (the, mat), so $\text{count}(\text{the}) = 2$ .
Numerator: of those two, only (the, cat) has "cat" second, so $\text{count}(\text{the}, \text{cat}) = 1$ .
Result: $P(\text{cat} \mid \text{the}) = \frac{1}{2} = 0.5$ , which rounded to 4 decimal places prints as 0.5.
Notice: the probabilities of all words following "the" add up to 1, since $P(\text{mat} \mid \text{the})$ is also $\frac{1}{2}$ . A word that only appears as the last word (like "mat") starts no bigram, so querying it as w1 gives 0.0.

Constraints

All text is lowercase
Bigram probability = count(bigram) / count(first word)
Round to 4 decimal places
If the first word never appears, output 0.0

Learn this in

Probability & StatisticsFoundations Introduction to LLMsLLM Study Plan Language ModelingNLP Study Plan

More from NLP 3: Advanced

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

Concept primer

Background Knowledge

Language Modeling is a fundamental concept in Natural Language Processing (NLP) that involves predicting the next word in a sequence of words. This is based on the probability distribution of words in a language. A key concept in language modeling is the idea of n-grams, which are sequences of $n$ items from a given sample of text. In this problem, we're dealing with bigrams, which are sequences of two items (i.e., $n=2$ ).

The probability of a bigram is calculated using the formula $P(\text{word2} | \text{word1}) = \frac{\text{count}(\text{word1}, \text{word2})}{\text{count}(\text{word1})}$ . This is an example of a conditional probability, where we're interested in the probability of $\text{word2}$ occurring given that $\text{word1}$ has occurred. The count of a word or bigram refers to the number of times it appears in the corpus.

Understanding bigram probabilities is essential in many NLP applications, such as language modeling, text generation, and language translation. By analyzing the co-occurrence of words in a corpus, we can gain insights into the structure and patterns of language. This knowledge can be used to improve the accuracy of language models and develop more sophisticated NLP systems.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Preprocessing the input corpus to extract individual words and bigrams
Counting the occurrences of each word and bigram in the corpus
Calculating the bigram probability using the formula $P(\text{word2} | \text{word1}) = \frac{\text{count}(\text{word1}, \text{word2})}{\text{count}(\text{word1})}$
Returning the calculated probability as the output

This approach can be implemented using a variety of programming languages and data structures, such as dictionaries or hash tables to store the word and bigram counts.

Step-by-Step Strategy

To implement the solution, follow these steps:

Read the input corpus and split it into individual words.
Create a dictionary to store the count of each word in the corpus.
Create another dictionary to store the count of each bigram in the corpus.
Iterate through the words in the corpus to populate the word and bigram count dictionaries.
Read the bigram to query and extract the individual words.
Calculate the bigram probability using the formula and the stored counts.
Round the probability to 4 decimal places and return it as the output.

Common Pitfalls

When implementing the solution, watch out for the following:

Make sure to handle cases where the input corpus is empty or contains only one word.
Ensure that the word and bigram counts are accurate and up-to-date.
Be careful when calculating the bigram probability to avoid division by zero errors.
Use a consistent method for splitting the input corpus into individual words and bigrams.

Time & Space Complexity

The expected time complexity of the solution is $O(n)$ , where $n$ is the number of words in the input corpus. This is because we need to iterate through the words in the corpus to populate the word and bigram count dictionaries. The space complexity is also $O(n)$ , as we need to store the word and bigram counts in memory. However, the actual time and space complexity may vary depending on the specific implementation and the size of the input corpus.

solution.py

Python 3.13

Test results