Spell_Correct

Java code to suggest correct English words against incorrectly spelled word.

Overview

It implements Ternary Search Tree (TST) data structure and Levenshtein Distance(LD) algorithm to suggest a list of 10 related english words sorted by Edit Distance (asc) (default-max : 3) followed by frequency(desc) of entered word in english language.

Algorithm

• Create a Priority Queue with a comparator.


• Create a TST and insert all english words (from Norvig’s post) along with their frequencies.


• Start traversing the TST and for every word encountered in TST, calculate its Levenshtein Distance(LD) from input_word


• If LD <= 3 then put it in a Priority Queue.


• At Last extract 10 words from the Priority Queue and display.

Performance

• Initially it takes about 450 ms to create the Ternary Search Tree for 97565 words.


• It suggests correct words with an average of 40-50 ms and 80 ms at worst.


• The algorithm is proportional to the length of wrong word. But it hardly crosses 80 ms.


• Tested on Pentium processor.

How to use

Download and run jar file. If it doesn’t run with double click, use following command.

java java -jar SpellCorrectApp.jar

API Details

Download and add jar file to your classpath. You can use the following methods of SpellCorrector class to get the list of suggested words.

1

java public void setEditLimit(int)
You can set up to what edit limit you want to see the result. Min value is 0, default is 3.

2

java public void setSuggestedWordListLimit(int)
You can set how many suggested words you want in output.

3

java public LinkedHashMap<String, Integer> correct(String) throws IllegalArgumentException
The method to correct a wrong word. It throws an IllegalArgumentException for blank or null String argument. It returns a LinkedHashMap<String, Integer> object where key(String) is the suggested correct word and its value is its edit distance from the wrong word. Also, the elements in map are arranged according to edit distance(asc) and then by the frequency of that word in english language(desc).

Sample Uses

try{
    SpellCorrector spellCorrector = new SpellCorrector();
    spellCorrector.setEditLimit(3); //[optional]
    spell_correct.setSuggestedWordListLimit(10); //[optional]
    LinkedHashMap<String, Integer> wordList = wordList = spellCorrector.correct("happyness");
    System.out.println("Word\t\tDistance");
    for (String word : suggestedWordMap.keySet()) {
        System.out.println(word +"\t\t"+suggestedWordMap.get(word));
    }
}catch (IllegalArgumentException e){
    e.printStackTrace();
}

Minimum Requirment

• Java 1.8+ and JavaFX 2.0+