Slide 1: Introduce predict next word app

• This apps is trained by large sets data from English: twitter, blog and news
• Utilized a fast algorithm of n-gram model with Katz Backoff
• It can predict the next word based on 3-gram (last two words)

Slide 2: App input and output

Input:

• English sentence seperated by space

Output:

• Most possible next word

Slide 3: App data arrangement

Due to the large size of training data, we did few things to optimize:

1. Indexed dictionary: So word will be encoded into numbers (i.e. indexes)
2. Put ngramCountTable into files: I saved each n-gram count into individual files using n-gram index as file name

Slide 4: Algorithm

• The goal is to build up a hash table with 3-gram as key, value as the probability
• Then loaded it into memory. Each predict is a lookeup in the hashtable and return the key with highest probability
• Used the standard Good-Turing discounting method for 2-gram and 3-gram
• Used the standard Katz method to back off into lower gram if cannot found count
  • Started from trigram

Slide 5: final product

It can be access here.

• ~I appologize that I haven’t finish it yet ~