Q$2\mathrm{.}1$: Train N$-$gram language model $(20$ pts$)$

Complete the following train$\_$ngram$\_$lm function based on the following input$/$output specifications. If you've done it right, you should pass the tests in the cell below.

Input:

data: the data object created in the cell above that holds the tokenized Wikitext data

order: the order of the model $($i$.$e$.,$ the $"$n$"$ in $"$n$-$gram" model$).$ If order$=3,$ we compute

$.$

Output:

lm: A dictionary where the key is the history and the value is a probability distribution over the next character computed using the maximum likelihood estimate from the training data. Importantly, this dictionary should include backoff probabilities as well; e$.$g$.,$ for order$=4,$ we want to store

as well as

and

$.$

Each key should be a single string where the characters that form the history have been concatenated. Given a key, its corresponding value should be a dictionary where each character in the vocabulary is associated with its probability of appearing after the key. For example, the entry for the history $\text{'}$c$1$c$2\text{'}$ should look like:

lm$[\text{'}$c$1$c$2\text{'}]=\{\text{'}$c$0\text{'}$: $0\mathrm{.}001,\text{'}$c$1\text{'}$ : $1$e$-6,\text{'}$c$2\text{'}$ : $1$e$-6,\text{'}$c$3\text{'}$: $0\mathrm{.}003,...\}$

In this example, we also want to store lm$[\text{'}$c$2\text{'}]$ and lm$[\text{'}\text{'}],$ which contain the bigram and unigram distributions respectively.

Hint: You might find the defaultdict and Counter classes in the collections module to be helpful.