import sys from collections import defaultdict, Counter import math # Step 1: Preprocess the text file to extract unigrams and bigrams def preprocess(file_path): """ Read and preprocess the input text file to extract unigrams and bigrams. Converts everything to lowercase and strips punctuation. """ with open(file_path, 'r') as f: sentences = [line.strip().lower().split() for line in f] return sentences # Step 2: Build the unigram model def build_unigram_model(sentences): """ Build a unigram model (1-gram) by counting word frequencies. """ unigram_counts = Counter() total_words = 0 for sentence in sentences: for word in sentence: unigram_counts[word] += 1 total_words += 1 # Convert to probabilities (frequency/total words) unigram_model = {word: count / total_words for word, count in unigram_counts.items()} return unigram_model, total_words, unigram_counts # Step 3: Build the bigram model def build_bigram_model(sentences): """ Build a bigram model (2-gram) by counting word pairs. """ bigram_counts = defaultdict(Counter) unigram_counts = Counter() total_bigrams = 0 for sentence in sentences: sentence = ['<s>'] + sentence # Add start of sentence symbol for i in range(len(sentence) - 1): unigram_counts[sentence] += 1 bigram_counts[sentence][sentence[i+1]] += 1 total_bigrams += 1 return bigram_counts, unigram_counts # Step 4: Add-one smoothing for bigram model def build_smoothed_bigram_model(bigram_counts, unigram_counts, vocabulary_size): """ Apply add-one smoothing to the bigram model. """ smoothed_bigram_model = defaultdict(Counter) for word, following_words in bigram_counts.items(): for next_word in following_words: smoothed_bigram_model[word][next_word] = (bigram_counts[word][next_word] + 1) / (unigram_counts[word] + vocabulary_size) return smoothed_bigram_model # Step 5: Calculate log probability for a sentence def calculate_log_probability(sentence, model, total_words=None, smoothing=False, is_bigram=False, unigram_counts=None): """ Calculate the log probability of a sentence using a given model. Use logarithmic space to avoid underflow. """ log_prob = 0 sentence = ['<s>'] + sentence if not is_bigram: # Unigram model for word in sentence[1:]: if word in model: log_prob += math.log2(model[word]) else: return 'undefined' # If a word is unseen in the training data else: # Bigram model (with or without smoothing) for i in range(len(sentence) - 1): word, next_word = sentence, sentence[i + 1] if next_word in model[word]: prob = model[word][next_word] else: # If no smoothing, return 'undefined' for unseen bigrams if not smoothing: return 'undefined' else: prob = 1 / (unigram_counts[word] + total_words) # For smoothed bigrams log_prob += math.log2(prob) return round(log_prob, 4) # Step 6: Process test file and calculate log probabilities def process_test_file(test_file, unigram_model, bigram_model, smoothed_bigram_model, total_words, vocabulary_size, unigram_counts): """ Process the test file and compute log probabilities using unigram, bigram (without smoothing), and bigram (with smoothing) models. """ test_sentences = preprocess(test_file) for sentence in test_sentences: print(f"S = {' '.join(sentence)}") # Unsmoothed Unigrams unigram_log_prob = calculate_log_probability(sentence, unigram_model, smoothing=False) print(f"Unsmoothed Unigrams, logprob(S) = {unigram_log_prob}") # Unsmoothed Bigrams bigram_log_prob = calculate_log_probability(sentence, bigram_model, smoothing=False, is_bigram=True, unigram_counts=unigram_counts) print(f"Unsmoothed Bigrams, logprob(S) = {bigram_log_prob}") # Smoothed Bigrams smoothed_log_prob = calculate_log_probability(sentence, smoothed_bigram_model, total_words, smoothing=True, is_bigram=True, unigram_counts=unigram_counts) print(f"Smoothed Bigrams, logprob(S) = {smoothed_log_prob}") print() # Main function def main(train_file, test_file): # Step 1: Preprocess training file train_sentences = preprocess(train_file) # Step 2: Build unigram and bigram models unigram_model, total_words, unigram_counts = build_unigram_model(train_sentences) bigram_counts, unigram_counts = build_bigram_model(train_sentences) # Step 3: Build smoothed bigram model vocabulary_size = len(unigram_model) smoothed_bigram_model = build_smoothed_bigram_model(bigram_counts, unigram_counts, vocabulary_size) # Step 4: Process the test file and output results process_test_file(test_file, unigram_model, bigram_counts, smoothed_bigram_model, total_words, vocabulary_size, unigram_counts) # Entry point if __name__ == '__main__': if len(sys.argv) != 3: print("Usage: python3 ngrams.py [train_file] [test_file]") else: main(sys.argv[1], sys.argv[2]) Modify above code to get output as below. Also it should support other test cases Output should be same as Trace1.txt on running python3 ngrams.py train1.txt test1.txt command Trace1.txt S=a Unsmoothed Unigrams, logprob(S) = -2.3219 Unsmoothed Bigrams, logprob(S) = 0.0000 Smoothed Bigrams, logprob(S) = -1.3219 S=bc Unsmoothed Unigrams, logprob(S) = -3.6439 Unsmoothed Bigrams, logprob(S) = undefined Smoothed Bigrams, logprob(S) = -3.9069 S=abcd Unsmoothed Unigrams, logprob(S) = -8.2877 Unsmoothed Bigrams, logprob(S) = -1.0000 Smoothed Bigrams, logprob(S) = -5.5507 Output should be same as Trace2.txt on running python3 ngrams.py train2.txt test2.txt command Trace2.txt S = Wolf Unsmoothed Unigrams, logprob(S) = -11.4522 Unsmoothed Bigrams, logprob(S) = -12.4375 Smoothed Bigrams, logprob(S) = -12.8260 S = In the jungle Unsmoothed Unigrams, logprob(S) = -22.0357 Unsmoothed Bigrams, logprob(S) = -15.3101 Smoothed Bigrams, logprob(S) = -18.9389 S = Rustle in the grass . Unsmoothed Unigrams, logprob(S) = -43.1179 Unsmoothed Bigrams, logprob(S) = undefined Smoothed Bigrams, logprob(S) = -51.7462 S = What could go wrong ? Unsmoothed Unigrams, logprob(S) = -48.2676 Unsmoothed Bigrams, logprob(S) = -35.3043 Smoothed Bigrams, logprob(S) = -55.0859 S = I swear I am not making this up . Unsmoothed Unigrams, logprob(S) = -82.8339 Unsmoothed Bigrams, logprob(S) = undefined Smoothed Bigrams, logprob(S) = -97.0172 S = But old Mr. Toad will leave one day . Unsmoothed Unigrams, logprob(S) = -78.5045 Unsmoothed Bigrams, logprob(S) = undefined Smoothed Bigrams, logprob(S) = -82.1001 build N-gram language models. It creates three different types of language models: (a) A unigram language model with no smoothing. (b) A bigram language model with no smoothing. (c) A bigram language model with add-one smoothing. You can assume that the set of unigrams found in the training corpus is the entire universe of unigrams. We will not give you test sentences that contain unseen unigrams. So the vocabulary V for this assignment is the set of all unique unigrams that occur in the training corpus, including punctuation marks. However, we will give you test sentences that contain bigrams that did not appear in the training corpus. The n-grams will consist entirely of unigrams that appeared in the training corpus, but there may be new (previously unseen) combinations of the unigrams. The first two language models (a) and (b) do not use smoothing, so unseen bigrams should be assigned a probability of zero. For the last language model (c), you should use add-one smoothing to compute the probabilities for all of the bigrams. For bigrams, you will need to have a special pseudo-word “” as a beginning-of-sentence symbol. Bigrams of the form “ wi” mean that word wi occurs at the beginning of the sentence. Do NOT include as a word in your vocabulary for the unigram language model or include in the sentence probability for the unigram model. For simplicity, just use the unigram frequency count of wk−1 to compute the conditional proba- bility P (wk | wk−1). (This means you won’t have to worry about cases where wk−1 occurs at the end of the sentence and isn’t followed by anything.) For example, just compute P (wk | wk−1) = count (wk−1wk) / count (wk−1). You should NOT use an end-of-sentence symbol. The last bigram for a sentence of length n should represent the last 2 words of the sentence: “wn−1wn”. For each of the language models, you should create a function that computes the probability of a sentence P (w1 . . . wn) using that language model. Since the probabilities will get very small, you must do the probability computations in log space (as discussed in class, also see the lecture slides). Please do these calculations using log base 2. Output Specifications Your program should print the following information to standard output for each test sentence. When printing the logprob numbers, please print exactly 4 digits after the decimal point. For 8 example, print -8.9753864210 as -8.9754 . The programming language will have a mechanism for controlling the number of digits that are printed. If P(S) = 0, then the logarithm is not defined, so print “logprob(S) = undefined”. Be sure to use a function that rounds, not truncates. For example, 1.33337 should be rounded to 1.3334 . You should only do the rounding as the last step in your calculations, just before printing. Do not round numbers during intermediate calculations or your final results will not be fully accurate. Print an empty line between different sentences. Continue reading...
