N-Gram

An N-gram is a sequence of N words: a 2-gram (or bigram) is a two-word sequence of words like “lütfen ödevinizi”, “ödevinizi çabuk”, or ”çabuk veriniz”, and a 3-gram (or trigram) is a three-word sequence of words like “lütfen ödevinizi çabuk”, or “ödevinizi çabuk veriniz”.

Smoothing

To keep a language model from assigning zero probability to unseen events, we’ll have to shave off a bit of probability mass from some more frequent events and give it to the events we’ve never seen. This modification is called smoothing or discounting.

Laplace Smoothing

The simplest way to do smoothing is to add one to all the bigram counts, before we normalize them into probabilities. All the counts that used to be zero will now have a count of 1, the counts of 1 will be 2, and so on. This algorithm is called Laplace smoothing.

Add-k Smoothing

One alternative to add-one smoothing is to move a bit less of the probability mass from the seen to the unseen events. Instead of adding 1 to each count, we add a fractional count k. This algorithm is therefore called add-k smoothing.

Video Lectures

Class Diagram

For Developers

You can also see Python, Cython, C, C++, Swift, Js, or C# repository.

Requirements

• Java Development Kit 8 or higher, Open JDK or Oracle JDK
• Maven
• Git

Java

To check if you have a compatible version of Java installed, use the following command:

java -version

If you don't have a compatible version, you can download either Oracle JDK or OpenJDK

Maven

To check if you have Maven installed, use the following command:

mvn --version

To install Maven, you can follow the instructions here.

Git

Install the latest version of Git.

Download Code

In order to work on code, create a fork from GitHub page. Use Git for cloning the code to your local or below line for Ubuntu:

git clone <your-fork-git-link>

A directory called SpellChecker will be created. Or you can use below link for exploring the code:

git clone https://github.com/olcaytaner/NGram.git

Open project with IntelliJ IDEA

Steps for opening the cloned project:

• Start IDE
• Select File | Open from main menu
• Choose NGram/pom.xml file
• Select open as project option
• Couple of seconds, dependencies with Maven will be downloaded.

Compile

From IDE

After being done with the downloading and Maven indexing, select Build Project option from Build menu. After compilation process, user can run NGram.

From Console

Use below line to generate jar file:

 mvn install

Maven Usage

    <dependency>
        <groupId>io.github.starlangsoftware</groupId>
        <artifactId>NGram</artifactId>
        <version>1.0.20</version>
    </dependency>

Detailed Description

• Training NGram
• Using NGram
• Saving NGram
• Loading NGram

Training NGram

To create an empty NGram model:

NGram(int N)

For example,

a = NGram(2);

this creates an empty NGram model.

To add an sentence to NGram

void addNGramSentence(Symbol[] symbols)

For example,

String[] text1 = {"jack", "read", "books", "john", "mary", "went"};
String[] text2 = {"jack", "read", "books", "mary", "went"};
nGram = new NGram<String>(2);
nGram.addNGramSentence(text1);
nGram.addNGramSentence(text2);

with the lines above, an empty NGram model is created and the sentences text1 and text2 are added to the bigram model.

Another possibility is to create an Ngram from a corpus consisting of two dimensional String array such as

ArrayList<ArrayList<String>> corpus;
nGram = new NGram<>(simpleCorpus, 1);

Training With Smoothings

NoSmoothing class is the simplest technique for smoothing. It doesn't require training. Only probabilities are calculated using counters. For example, to calculate the probabilities of a given NGram model using NoSmoothing:

a.calculateNGramProbabilities(new NoSmoothing());

LaplaceSmoothing class is a simple smoothing technique for smoothing. It doesn't require training. Probabilities are calculated adding 1 to each counter. For example, to calculate the probabilities of a given NGram model using LaplaceSmoothing:

a.calculateNGramProbabilities(new LaplaceSmoothing());

GoodTuringSmoothing class is a complex smoothing technique that doesn't require training. To calculate the probabilities of a given NGram model using GoodTuringSmoothing:

a.calculateNGramProbabilities(new GoodTuringSmoothing());

AdditiveSmoothing class is a smoothing technique that requires training.

a.calculateNGramProbabilities(new AdditiveSmoothing());

Using NGram

To find the probability of an NGram:

double getProbability(Symbol ... symbols)

For example, to find the bigram probability:

a.getProbability("jack", "reads")

To find the trigram probability:

a.getProbability("jack", "reads", "books")

Saving NGram

To save the NGram model:

void saveAsText(String fileName)

For example, to save model "a" to the file "model.txt":

a.saveAsText("model.txt");              

Loading NGram

To load an existing NGram model:

NGram(String fileName)

For example,

a = NGram("model.txt");

this loads an NGram model in the file "model.txt".