# AutoComplete program using the n-gram model

For my Advanced Data Mining class (undergrad) we were to design a program that would predict the next word a user is likely to type via automatic text classification using the n-gram model.

The following is what I came up with. The reason I am posting this is because I am about to graduate and I want to be aware of any bad habits, inefficiencies, or examples of poor implementation that I might be prone to before I have to go out and interview for Data Science Graduate programs. Unfortunately, my professors are too busy to give this kind of analysis and it seems like they just grade us on whether a program works or not (this one does).

Note: This program uses the AOL search data from here in a text file called searchterms.txt.

import java.io.*;
import java.util.*;
public class AutoComplete {

public static void main(String[] args) throws FileNotFoundException {
/* Define Variables */
int n = 3;
Hashtable<String, Hashtable<String, Double>> nGram = new Hashtable<String, Hashtable<String, Double>>();
Scanner inFile = new Scanner(new File("searchterms.txt"));
Scanner input = new Scanner(System.in);

/* Output for progress tracking */

/* Populate the LinkedList sentences with data from AOL search dataset */
while(inFile.hasNext()) {
String unparsed = inFile.nextLine().intern();
String[] parsed = unparsed.split("\t");
sentences.add("<S> " + parsed[1] + " </S>");
}
inFile.close();

/* Output for progress tracking */
System.out.println("Successfully archived searches.");
System.out.println("Creating 3 grams...");

/* Split sentences into words */
for(String s : sentences) {
String[] words = s.split("[\\s]");
for(int i = 0; i <= words.length-n; i++) {
if(nGram.containsKey(words[i] + " " + words[i+1])) {
//Output for testing
//System.out.println("MATCH FOUND! ("+ words[i+2]+") Incrementing...");
if(nGram.get(words[i]+" "+words[i+1]).containsKey(words[i+2])) {
double v = nGram.get(words[i] + " " + words[i+1]).get(words[i+2]);
v++;
nGram.get(words[i] + " " + words[i+1]).put(words[i+2], v);
} else {
nGram.get(words[i] + " " + words[i+1]).put(words[i+2], 1.0);
}
} else {
//Output for testing
//System.out.println("No match found. Adding..." + words[i+2]);
nGram.put(words[i]+" "+words[i+1], createResult(words[i+2]));
}
}
}

/* Output for progress tracking */
System.out.println("Successfully created 3 grams.");

/* Loop so you can play with this forever */
String sTerm = "";
while(true) {
/* Request User Input */
sTerm = input.nextLine();
if (sTerm.equalsIgnoreCase("/q")) break;
/* Format user input */
String[] terms = sTerm.split("[\\s]");
if (terms.length < 2) {
sTerm = "<S> " + terms[0];
//Output for testing
//System.out.println(sTerm);
} else {
sTerm = terms[terms.length-2] + " " + terms[terms.length-1];
//Output for testing
//System.out.println(sTerm);
}

/* Normalize to percent values */
double sum = 0;
try {
for(String s : nGram.get(sTerm).keySet()) {
sum += nGram.get(sTerm).get(s);
}
for(String s : nGram.get(sTerm).keySet()) {
nGram.get(sTerm).put(s, nGram.get(sTerm).get(s)/sum);
}
} catch (Exception NullPointerException) {
}
/* Give prediction */
try {
System.out.println("Prediction: " + prediction(nGram.get(sTerm)) + " ("+ Math.round(predValue(nGram.get(sTerm))*100) +"%)");
} catch (Exception NullPointerException) {
System.out.println("Cannot make a prediction.");
}

/* Testing block */
//System.out.println(nGram.get(sTerm).keySet());
//System.out.println(nGram.get(sTerm).values());
}
input.close();
}

/* Needed for scope */
static final Hashtable<String, Double> createResult(String s) {
Hashtable<String, Double> result = new Hashtable<String, Double>();
result.put(s, 1.0);
return result;
}

/* Prediction methods */
static final String prediction(Hashtable<String, Double> h) {
String key = "";
double max = 0;
for(String s : h.keySet()) {
if(h.get(s) > max) {
max = h.get(s);
key = s;
}
}
return key;
}
static final double predValue(Hashtable<String, Double> h) {
double max = 0;
for(String s : h.keySet()) {
if(h.get(s) > max) {
max = h.get(s);
}
}
return max;
}
}

• Thanks for the edit! I was struggling with the formatting of the post if you couldn't tell haha Apr 20 '14 at 9:27

Your code looks at first glance quite complete and professional, so onto the points. I hereby assume that you are using Java 7, since you have not made any restrictions and it is the most common version, though I may be wrong.

1. Consider changing your programs design. Currently you have an AutoComplete class, with almost everything in the main class. Now what happens if you want to run two AutoComplete instances simultaneously? You cannot do that in one program.
I would advice to change the following points:

1. Make an AutoComplete class that can operate on it's own, you tell it what to do, what the inputs are, and you can call methods on it that give you output.
2. One candidate for refactoring is the input file, this should be an input argument.
3. Another point is that you request user input inside your processing, the user input should be asked beforehand and also be an input parameter.
4. The prediction which gets printed while processing, should be an output.
2. Use diamond inference where possible, this means that for example LinkedList<String> sentences = new LinkedList<String>(); can be written as LinkedList<String> sentences = new LinkedList<>();.

3. Code against interfaces instead of against classes. Take your LinkedList<String> sentences again. Nowhere I see a requirement to use a LinkedList here, you just want to use a list, so only constrain yourself to writing: List<String> sentences = new LinkedLIst<>(). This allows you to change the exact type of List at a later point.

4. I see that you only loop over the LinkedList<String> sentences, you have no special requirement to use a linked list, consider using the more or less default ArrayList, which provides constant lookup times and generally performs better. In your case the performance seems to be equal as all you do is, underlying to the enhanced for-loop, use an Iterator.

5. Consider changing from using the File API to the Path API at some point, it offers more future-ready changes and will coöperate better with Java 8.

6. Prefer a class that receives print statements over directly printing to System.out during processing. In bigger projects this usually is a logger framework, to which you then attach System.out writers and also file writers for logfiles. In your case you may use a simplified version of this.

7. A Hashtable is old, very old, use the nowadays standard called Map, with as default implementation a HashMap. Some method names/semantics may have changed, but they both serve the same purpose.

8. Do not catch all exceptions with Exception NullPointerException, you may have confused yourself here, but this catches all exceptions of type Exception (so all), and gives the caught exception the name NullPointerException. But even then, catching NullPointerExceptions is not good and you should just let them fall through such that they terminate your program (or thread), so you can actually fix the issue, rather than a Cannot make prediction. message.

As a whole, the best advice I can give you is to consider more abstraction, make your methods smaller and give them a single responsibility. A very important second advice is to use language features that are the standard in this day.

• Yep, Java 7. 1. That all makes a lot of sense. I think I was a little short-sighted when I wrote it and I didn't think much about scalability. I will definitely do this in the future. 2. I've seen that before, but it isn't something we actively learned. What's the advantage to using diamond inference? 3. Ahh, I totally understand. I guess since I am used to using LinkedLists for that type of operation I didn't think much further. I can see the added flexability I would get from using the interface List instead. Thanks! Apr 20 '14 at 10:49
• 4. Wow. I hadn't even considered ArrayList. I completely forgot about them. I think I lied above. I'm not used to using LinkedLists for that type of operation... I think I use them for everything. Oops. Glad you pointed that out. 5. Got it. 6. Oh, yeah. I see what you're saying. That makes a lot of sense for industry (which is the way I'm trying to convert my thinking). Since my original concern was more about the theory of what I was doing I just programmed this to run from a .bat on a local machine. Apr 20 '14 at 10:50
• After I finished I wanted to try to make a better standalone program and I never really thought about how larger projects would handle my output. I always envisioned this to be a part of something larger, so definitely something to consider. 7. What the actual f---. We spent a ton of time learning Hashtables and we never touched Maps. That's really frustrating. 8. Definitely confused myself. I thought I was catching an Exception of type NullPointerException. I guess I meant catch(NullPointerException NoDatasetValue)? Apr 20 '14 at 10:50
• The message was more for me playing with the project, so that when I typed in something obscure I didn't have to restart it when it failed. (Building 3 grams for 3.6 million search phrases takes a little bit) Thanks for all the advice, it will definitely help me a lot going forward. I've learned a lot in school, but I know its going to be a whole different world when I graduate and I'd like to be as prepared as possible - as little as that may be! Apr 20 '14 at 10:51

Although all points made by @skiwi are valid (+1), he missed a few important points:

## "Use exceptions only for exceptional conditions" (Effective Java Item 57)

try {
/* ... */ nGram.get(sTerm).xyz /* ... */
} catch (NullPointerException e) {
}


Do not use try/catch to control normal program flow.

Map<String, Double> nGramForSearchTerm = nGram.get(sTerm);

if (nGramForSearchTerm == null) {
System.out.println("Cannot make a prediction.");
System.exit(0);
}


EDIT

As noted in the comments by @200_success; "NullPointerExceptions can lurk anywhere in the code, and arise due to programmer error rather than unexpected runtime conditions." Therefore catching NullPointerException is practically always a bad idea. Whenever you find yourself writing catch (NullPointerException you should stop and think. If you are catching NullPointerException because some method may return null, convert it to a null checking conditional instead. If you are writing it because it was thrown somewhere else, then first track the cause (to a piece of code you are responsible, most probably the scope where you are writing the try/catch) and handle it at the point it was caused; with a null check as above or checking with Map.containsKey(), Collection.isEmpty(), Iterator.hasNext() etc.

## DRY: Do not repeat yourself. Factor out repeated sections and give them meaningful names.

One is nGram.get(sTerm). I called it nGramForSearchTerm but you can give it a more meaningful name.

The more important example is predValue/prediction. Repetition is evil. And repetition of algorithm (business logic) is a great evil. The cause of the repetition is that Java does not allow more than one value to be returned. But this is not really a problem unless you suffer from primitive obsession also. Just define a new value object Prediction and put the values that would be returned as fields in it.

static class Prediction {
private final String nGram;
private final double confidence;
// constructor getters only.
}

static Prediction getBestPrediction(Map<String, Double> /* TODO rename this */ map) {
if (map.isEmpty()) throw new IllegalArgumentException();

String bestPrediction = null;
double bestConfidence = 0;
for(Entry<String, Double> entry : map.entrySet()) {
String currentPrediction = entry.getKey();
double currentConfidence = entry.getValue();

if (currentConfidence > bestConfidence) {
bestConfidence = currentConfidence;
bestPrediction = currentPrediction;
}
}
return new Prediction(bestPrediction, bestConfidence);
}


Some points to note (and apply to other parts of the original code). If you are iterating over all keys of a Map and looking up that map for all (or many) of those keys, use Map.entrySet() instead.

## Do normalization once in the beginning

Also in the DRY vein. You should do normalization once in the beginning for all values.

• Since the latter part of the algorithm depends on normalized values, you should give it a normalized data structure, and relieve the reader of the code from the mental burden of trying to figure out which values of the said data structure are normalized and when.

• Floating point arithmetic double arithmetic is inexact. So doing normalization on already normalized values is not idempotent. (You may not notice a difference, or giving the confidence level false in the nth decimal place may not be important but this is a design issue. It may be serious issue later. Looking up values should be idempotent, should not modify used data structures.)

Some examples of 20 1s normalized repeatedly:

 0.04999999999999999
0.049999999999999975
0.05000000000000002
0.04999999999999998
0.050000000000000024
0.04999999999999999
0.049999999999999975
0.05000000000000002
0.04999999999999998
0.050000000000000024

• Normalizing upfront, it may cause a slight performance depending on the size of the DB, but it will improve the performance of each individual lookup, which is what you want. (As a side note: Where there are many possible misses in a lookup, a bloom filter may be indicated.)

• Catching NullPointerException is particularly bad, since NullPointerExceptions can lurk anywhere in the code, and arise due to programmer error rather than unexpected runtime conditions. It's akin to reviving a C program after a segmentation fault. Apr 24 '14 at 10:14
• @200_success I totally agree. I edited in a few words to that effect. Apr 24 '14 at 10:49