Java Spell Checker hashing program We will create a spell ch

Java Spell Checker: hashing program

We will create a spell checker program. This program will use  a text file (.txt) which will be included in the program and contains an arbitrary list of words as a dictionary to look up properly spelled words. When the program starts, it will open the dictionary file (name it \"Words.txt\"). You will utilize a hash function you have created to hash the words into an externally-chained hash table you have created. The hash table will be of a size that you will determine. You will report the following statistics:

maximum chain length

average chain length

percentage of buckets to which one or more words hashed

Your program will then open an input file named \"inputTextFile.txt.\" When the checking proceeds, you will extract a word from the file to be checked, hash it into the table, and determine if it exists. You will continue this process until you have checked all the words in the file. Each time you find a word that you cannot match in the dictionary, you will let the user know and you will attempt to generate a list of suggested words. You will generate the list by assembling similar words via four methods:

One letter missing. You assume that one letter has been left out of the word. You can assemble new words to check by adding letters a..z in each of the positions in the word from the start to the end of the word.

One letter added. You assume the word has an extra letter. You scan through the word deleting each of the letters in turn, and looking up the word formed by the remaining letters.

Two letters reversed. You swap letters in positions 0..1, 1..2, 2..3, ... , n-2..n-1, to form new words which you look up.

One letter changed. You try each letter at each position in the word to see if one letter was simply mis-typed.

Each time you find a legal word from any of the four methods, you add it to the suggestion ArrayList, which you present to the user when you have finished this part of the process. If you cannot identify any suggestions, let the user know.

Example file:

Hello. My plan is to hav a test fiile that has UPPer and LOWER case words. All fuor cises of misspellings will be represented. The file will encompass more than one line and will have no other puncktuation than commas, and the dot at the end of a line.

------------------------------------------------------------

Be sure to report the following statistics in the output :

1. maximum chain length

2. average chain length

3. percentage of buckets to which one or more words hashed

Solution

/*The main program that loads the correct dictionary spellings and takes input to be analyzed from user.*/ public class SpellChecker { private static String stringInput; // input to check; private static String[] checkThis; // the stringInput turned array of words to check. public static HashSet dictionary; // the dictionary used /* Main method.*/ public static void main(String[] args) { setup(); } //end of main /*This method loads the dictionary and initiates the checks for errors in a scanned input.*/ public static void setup() { int tableSIZE=59000; dictionary = new HashSet(tableSIZE); try { //System.out.print(System.getProperty(\"user.dir\")); //just to find user\'s working directory; // Combined the FileReader into the BufferReader statement BufferedReader bufferedReader = new BufferedReader(new FileReader(\"./dictionary.txt\")); String line = null; // notes one line at a time while((line = bufferedReader.readLine()) != null) { dictionary.add(line); //add dictinary word in } prompt(); bufferedReader.close(); //close file } catch(FileNotFoundException ex) { ex.printStackTrace(); //print error } catch(IOException ex) { ex.printStackTrace(); //print error } } //end of setUp /* Just a prompt for auto generated tests or manual input test. */ public static void prompt() { System.out.println(\"Type a number from below: \"); System.out.println(\"1. Auto Generate Test\\t2.Manual Input\\t3.Exit\"); Scanner theLine = new Scanner(System.in); int choice = theLine.nextInt(); // for manual input if(choice==1) autoTest(); else if(choice==2) startwInput(); else if (choice==3) System.exit(0); else System.out.println(\"Invalid Input. Exiting.\"); } /* Manual input of sentence or words. */ public static void startwInput() { printDictionary(bufferedReader); // print dictionary System.out.println(\"Spell Checker \ Please enter text to check: \"); Scanner theLine = new Scanner(System.in); stringInput = theLine.nextLine(); // for manual input System.out.print(\"\ You have entered this text: \"+stringInput+\"\ Initiating Check...\"); long startTime = System.currentTimeMillis(); //speed test WordFinder grammarNazi = new WordFinder(); //instance of MisSpell splitString(removePunctuation(stringInput));//turn String line to String[] grammarNazi.initialCheck(checkThis); final long endTime = System.currentTimeMillis(); System.out.println(\"Total execution time: \" + (endTime - startTime) ); } //end of startwInput /* Generates a testing case. */ public static void autoTest() { System.out.println(\"Spell Checker \ This sentence is being tested: \ hello, how are you ... \"); WordFinder grammarNazi = new WordFinder(); //instance of MisSpell splitString(removePunctuation(\"hello, how are you ... \"));//turn String line to String[] grammarNazi.initialCheck(checkThis); } //end of autoTest /* This method prints the entire dictionary which was used in testing. */ public static void printDictionary(BufferedReader bufferedReader) { String line = null; // notes one line at a time try { while((line = bufferedReader.readLine()) != null) { System.out.println(line); } } catch(FileNotFoundException ex) { ex.printStackTrace(); //print error } catch(IOException ex) { ex.printStackTrace(); //print error } } //end of printDictionary /* This methods splits the passed String and puts them into a String[] */ public static void splitString(String sentence) { // split the sentence in between \" \" spaces checkThis = sentence.split(\" \"); } //end of splitString /* This method removes the punctuation and capitalization from a string.*/ public static String removePunctuation(String sentence) { String newSentence; // the new sentence //remove evil punctuation and convert the whole line to lowercase newSentence = sentence.toLowerCase().replaceAll(\"[^a-zA-Z\\\\s]\", \"\").replaceAll(\"\\\\s+\", \" \"); return newSentence; } //end of removePunctuation } /*This class checks for misspellings*/ public class WordFinder extends SpellChecker { private int wordsLength;//length of String[] to check private List wrongWords = new ArrayList(); //stores incorrect words /* This methods checks the String[] for spelling errors. * Hashes each index in the String[] to see if it is in the dictionary HashSet*/ public void initialCheck(String[] words) { wordsLength=words.length; System.out.println(); for(int i=0;i=0) test.print(test.possibilities); } //end of while } //end of suggest /*ENTERING TEST ZONE*/ /* This allows a tester to look thorough the dictionary for words if they are valid; and for testing only.*/ public void manualWordLookup() { System.out.print(\"Enter \'ext\' to exit.\ \ \"); Scanner line = new Scanner(System.in); String look=line.nextLine(); do{ if(dictionary.contains(look)) System.out.print(look+\" is valid\ \"); else System.out.print(look+\" is invalid\ \"); look=line.nextLine(); }while (!look.equals(\"ext\")); } //end of manualWordLookup } /*This is the main class responsible for generating misspellings. */ public class MisSpell extends SpellChecker { public List possibilities = new ArrayList();//stores possible suggestions private List tempHolder = new ArrayList(); //helps for the transposition method private int Ldistance=0; // the distance related to the two words private String wrongWord;// the original wrong word. /* Execute methods that make misspellings.*/ public void generateMispellings(String wordCheck) { wrongWord=wordCheck; try { concatFL(wordCheck); concatLL(wordCheck); replaceFL(wordCheck); replaceLL(wordCheck); deleteFL(wordCheck); deleteLL(wordCheck); pluralize(wordCheck); transposition(wordCheck); }catch(StringIndexOutOfBoundsException e) { System.out.println(); }catch(ArrayIndexOutOfBoundsException e) { System.out.println(); } } /* This method concats the word behind each of the alphabet letters and checks if it is in the dictionary. * FL for first letter */ public void concatFL(String word) { char cur; // current character String tempWord=\"\"; // stores temp made up word for(int i=97;i<123;i++) { cur=(char)i; //assign ASCII from index i value tempWord+=cur; //if the word is in the dictionary then add it to the possibilities list tempWord=tempWord.concat(word); //add passed String to end of tempWord checkDict(tempWord); //check to see if in dictionary tempWord=\"\"; //reset temp word to contain nothing } //end of for }//end of concatFL /* This concatenates the alphabet letters behind each of the word and checks if it is in the dictionary. LL for last letter.*/ public void concatLL(String word) { char cur; // current character String tempWord=\"\"; // stores temp made up word for(int i=123;i>97;i--) { cur=(char)i; //assign ASCII from index i value tempWord=tempWord.concat(word); //add passed String to end of tempWord tempWord+=cur; //if the word is in the dictionary then add it to the possibilities list checkDict(tempWord); tempWord=\"\"; //reset temp word to contain nothing } //end of for } //end of concatLL /* This method replaces the first letter (FL) of a word with alphabet letters.*/ public void replaceFL(String word) { char cur; // current character String tempWord=\"\"; // stores temp made up word for(int i=97;i<123;i++) { cur=(char)i;//assign ASCII from index i value tempWord=cur+word.substring(1,word.length()); //add the ascii of i ad the substring of the word from index 1 till the word\'s last index checkDict(tempWord); tempWord=\"\";//reset temp word to contain nothing } //end of for } //end of replaceFL /*This method replaces the last letter (LL) of a word with alphabet letters*/ public void replaceLL(String word) { char cur; // current character String tempWord=\"\"; // stores temp made up word for(int i=97;i<123;i++){ cur=(char)i;//assign ASCII from index i value tempWord=word.substring(0,word.length()-1)+cur; //add the ascii of i ad the substring of the word from index 1 till the word\'s last index checkDict(tempWord); tempWord=\"\"; //reset temp word to contain nothing } //end of for } //end of replaceLL /* This deletes first letter and sees if it is in dictionary*/ public void deleteFL(String word) { String tempWord=word.substring(1,word.length()-1); // stores temp made up word checkDict(tempWord); //print(possibilities); } //end of deleteFL /*This deletes last letter and sees if it is in dictionary*/ public void deleteLL(String word) { String tempWord=word.substring(0,word.length()-1); // stores temp made up word checkDict(tempWord); //print(possibilities); } //end of deleteLL /* This resets a list*/ public void resetHelper(List thisList) { while(!thisList.isEmpty()) thisList.remove(0); //while list is not empty, remove first value }//end of resetHelper /* This method prints out a list*/ public void print(List listPrint) { if (possibilities.isEmpty()) { System.out.print(\"Can\'t seem to find any related words for \"+wrongWord); return; } System.out.println(\"Maybe you meant these for \"+wrongWord+\": \"); System.out.printf(\"%s\", listPrint); resetHelper(possibilities); }//end of print /*This returns a String word version of a list */ public String printWord(List listPrint) { Object[] suggests = listPrint.toArray(); String theWord=\"\"; for(Object word: suggests){//form listPrint elements into a word theWord+=word; } return theWord; }//end of printWord }