Java implementation of spell-checking algorithm

Question

This little program was written for an assignment in a data structures and algorithms class. I'll just note the basic requirements:

Given an inputted string, the program should check to see if it exists in a dictionary of correctly spelled words. If not, it should return a list of words that are obtainable by:

• adding any character to the beginning or end of the inputted string
• removing any single character from the inputted string
• swapping any two adjacent characters in the string

The primary data structure is embodied in the Dictionary class, which is my implementation of a separately-chaining hash list, and the important algorithms are found in the charAppended(), charMissing() and charsSwapped() methods.

Everything works as expected - I'm just looking for tips about anything that can be done more cleanly, efficiently or better aligned with best practices.

SpellCheck.java

import java.util.ArrayList;
import java.util.Scanner;

public class SpellCheck {

    private Dictionary dict;
    final static String filePath = "d:/desktop/words.txt";
    final static char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray();

    SpellCheck() {
        dict = new Dictionary();
        dict.build(filePath);

    }

    void run() {
        Scanner scan = new Scanner(System.in);
        boolean done = false;
        String input;

        while (true) {
            System.out.print("\n-------Enter a word: ");
            input = scan.nextLine();
            if (input.equals("")) {
                break;
            }
            if (dict.contains(input)) {
                System.out.println("\n" + input + " is spelled correctly");
            } else {
                System.out.print("is not spelled correctly, ");
                System.out.println(printSuggestions(input));
            }
        }
    }

    String printSuggestions(String input) {
        StringBuilder sb = new StringBuilder();
        ArrayList<String> print = makeSuggestions(input);
        if (print.size() == 0) {
            return "and I have no idea what word you could mean.\n";
        }
        sb.append("perhaps you meant:\n");
        for (String s : print) {
            sb.append("\n  -" + s);
        }
        return sb.toString();
    }

    private ArrayList<String> makeSuggestions(String input) {
        ArrayList<String> toReturn = new ArrayList<>();
        toReturn.addAll(charAppended(input));
        toReturn.addAll(charMissing(input));
        toReturn.addAll(charsSwapped(input));
        return toReturn;
    }

    private ArrayList<String> charAppended(String input) { 
        ArrayList<String> toReturn = new ArrayList<>();
        for (char c : alphabet) {
            String atFront = c + input;
            String atBack = input + c;
            if (dict.contains(atFront)) {
                toReturn.add(atFront);
            }
            if (dict.contains(atBack)) {
                toReturn.add(atBack);
            }
        }
        return toReturn;
    }

    private ArrayList<String> charMissing(String input) {   
        ArrayList<String> toReturn = new ArrayList<>();

        int len = input.length() - 1;
        //try removing char from the front
        if (dict.contains(input.substring(1))) {
            toReturn.add(input.substring(1));
        }
        for (int i = 1; i < len; i++) {
            //try removing each char between (not including) the first and last
            String working = input.substring(0, i);
            working = working.concat(input.substring((i + 1), input.length()));
            if (dict.contains(working)) {
                toReturn.add(working);
            }
        }
        if (dict.contains(input.substring(0, len))) {
            toReturn.add(input.substring(0, len));
        }
        return toReturn;
    }

    private ArrayList<String> charsSwapped(String input) {   
        ArrayList<String> toReturn = new ArrayList<>();

        for (int i = 0; i < input.length() - 1; i++) {
            String working = input.substring(0, i);// System.out.println("    0:" + working);
            working = working + input.charAt(i + 1);  //System.out.println("    1:" + working);
            working = working + input.charAt(i); //System.out.println("    2:" + working);
            working = working.concat(input.substring((i + 2)));//System.out.println("    FIN:" + working); 
            if (dict.contains(working)) {
                toReturn.add(working);
            }
        }
        return toReturn;
    }

    public static void main(String[] args) {
        SpellCheck sc = new SpellCheck();
        sc.run();
    }

}

Dictionary.java

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException; 

public class Dictionary {
    private int M = 1319; //prime number
    final private Bucket[] array;
    public Dictionary() {
        this.M = M;

        array = new Bucket[M];
        for (int i = 0; i < M; i++) {
            array[i] = new Bucket();
        }
    }

    private int hash(String key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    //call hash() to decide which bucket to put it in, do it.
    public void add(String key) {
        array[hash(key)].put(key);
    }

    //call hash() to find what bucket it's in, get it from that bucket. 
    public boolean contains(String input) {
        input = input.toLowerCase();
        return array[hash(input)].get(input);
    }

    public void build(String filePath) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(filePath));
            String line;
            while ((line = reader.readLine()) != null) {
                add(line);
            }
        } catch (IOException ioe) {
            ioe.printStackTrace();
        }

    }
    //this method is used in my unit tests
    public String[] getRandomEntries(int num){
        String[] toRet = new String[num];
        for (int i = 0; i < num; i++){
            //pick a random bucket, go out a random number 
            Node n = array[(int)Math.random()*M].first;
            int rand = (int)Math.random()*(int)Math.sqrt(num);

            for(int j = 0; j<rand && n.next!= null; j++) n = n.next;
            toRet[i]=n.word;


        }
        return toRet;
    }

    class Bucket {

        private Node first;

        public boolean get(String in) {         //return key true if key exists
            Node next = first;
            while (next != null) {
                if (next.word.equals(in)) {
                    return true;
                }
                next = next.next;
            }
            return false;
        }

        public void put(String key) {
            for (Node curr = first; curr != null; curr = curr.next) {
                if (key.equals(curr.word)) {
                    return;                     //search hit: return
                }
            }
            first = new Node(key, first); //search miss: add new node
        }

        class Node {

            String word;
            Node next;

            public Node(String key, Node next) {
                this.word = key;
                this.next = next;
            }

        }

    }
}

Answer 1

General

Many of the variable names lack meaning and are inconsistent. I cover some of them specifically below, but for example print is not a good choice for a list of suggestions--even though you intend to print them. Instead, suggestions clearly identifies what the list holds.

Learn to use JavaDoc for documenting public classes and methods. Not only is it nicer to read than one-liners, developing this habit early will demonstrate your goal to become a professional engineer (if that's the case).

/**
 * Adds the key to this dictionary if not already present.
 *
 * @param key hash determines the bucket to receive it
 */
public void add(String key) { ... }

/**
 * Determines if the key is present in this dictionary.
 *
 * @param key hash determines the bucket to search
 * @return true if key is present
 */
public boolean contains(String input) { ... }

SpellCheck

You make a good effort at breaking up the methods and separating concerns, but I would take it a step further. The methods that build alternate spellings should not be responsible for checking the dictionary. Instead, combine all misspellings into a single list and search the dictionary in one place. This also allows you to remove duplicates and avoid wasted lookups.

I would also completely separate all output, possibly to a new UI class to allow reuse. You did pretty well here, but printSuggestions should receive the list of suggestions instead of calling makeSuggestions itself.

    private void printStatusAndSuggestions(String input) {
        System.out.println();
        System.out.print(input);
        if (dict.contains(input) {
            System.out.println(" is spelled correctly.");
        } else {
            System.out.print(" is not spelled correctly,");
            printSuggestions(suggest(input));
        }
    }

    private void printSuggestions(Set<String> suggestions) {
        if (suggestions.isEmpty()) {
            System.out.println(" and I have no idea what word you could mean."
        } else {
            ... print them ...
        }
    }

    private Set<String> suggest(String input) {
        Set<String> suggestions = new HashSet<>();
        Set<String> alternates = makeAlternates(input);
        for (String alternate : alternates) {
            if (dict.contains(alternate) {
                suggestions.add(alternate);
            }
        }
        return suggestions;
    }

If Dictionary implemented the Set interface, you could use the built-in intersection method to do the lookups for you.

private Set<String> suggest(String input) {
    return makeAlternates(input).retainAll(dict);
}

• input.equals("") is better expressed as input.isEmpty(). You may want to trim the input to remove leading/trailing spaces: input = scan.nextLine().trim();

• This applies similarly to ArrayList: print.isEmpty() instead of print.size() == 0.

• pringSuggestions creates a StringBuilder needlessly when there are no suggestions.

• You use two different methods of concatenating strings when building suggestions: an implicit StringBuilder and String.concat. Both are fine in different circumstances (though I confess that I've never used the latter), but make sure you combine all the concatenations in one statement. Breaking them across statements uses a new builder for each statement. charsSwapped is especially egregious requiring three for each suggestion instead of one.

  String working = input.substring(0, i)
          + input.charAt(i + 1);
          + input.charAt(i);
          + input.substring(i + 2);
  

Dictionary

• Turn M into a constant. As it stands, you're initializing the field to 1319 and then reassigning it to itself in the constructor. Perhaps BUCKET_COUNT is a better name.

  Alternatively, add a constructor that takes the value as a parameter. While we're at it, how about buckets in place of the very generic name array? It's rarely a good idea to name a primitive variable based solely on its type.

  public static final int DEFAULT_BUCKET_COUNT = 1319;
  
  private final bucketCount;
  private final Bucket[] buckets;
  
  public Dictionary() {
      this(DEFAULT_BUCKET_COUNT);
  }
  
  public Dictionary(int bucketCount) {
      this.bucketCount = bucketCount;
      ... create empty buckets ...
  }
  

Bucket/Node

• Both of these can be static since they don't access the outer classes' members.

• You don't really need Bucket and may consider rewriting the code to remove it to see the difference. It's not a huge improvement but may simplify the code.

• As with Dictionary, add and contains make more sense than put and get.

• Be consistent with naming across methods. In Bucket, get takes in while put takes key, but in and key represent the same things and as such should use the same name: key. Also, stick with curr to avoid confusion with Node.next.

• @Czippers nailed this one: get and put should use the same looping construct since they're both walking the list in order and possibly stopping at some point.

Answer 2

1. Take a wrongly spelled word as input.
2. Store the list of English words along with their frequencies in a text file. I have used this text file from Norvig’s post.
3. Insert all the available English words(stored in the text file) along with their frequencies (measure of how frequently a word is used in English language) in a Ternary Search Tree.
4. Now traverse along the Ternary Search Tree
   • For each word encountered in the Ternary Search Tree, calculate its Levenshtein Distance from the wrongly spelled word.
   • if Levenshtein Distance <= 3, store the word in a Priority Queue.
   • If two words have same edit distance, the one with higher frequency is grater.
     5. Print the top 10 items from Priority Queue.

You can see the whole code on github.

Answer 3

Other than in the Bucket.get() method, you can replace the while loop with a for loop like in put(), it looks good! You might want to combine Dictionary.printSuggestions() and Dictionary.makeSuggestions() because that was a little weird. But if you want to be super OO, then good for you!

If this is for a class, you can look like a pro by replacing:

System.out.println("\n" + input + " is spelled correctly");

with

System.out.println(new StringBuffer(1 + input.length() + " is spelled correctly".length).append("\n").append(input).append(" is spelled correctly").toString());

Also if you have an if statement or while or for or whatever, you can use no brackets if there is only one thing inside it. For example:

for (Node curr = first; curr != null; curr = curr.next) {
    if (key.equals(curr.word)) {
        return;                     //search hit: return
    }
}

Can be replaced by:

for(Node curr = first; curr != null; curr = curr.next)
    if(key.equals(curr.word))
        return;                     //search hit: return