Objective

Develop an efficient algorithm for spell checking using a HashTable

Experiment with different hash functions and table sizes, and measure the performance of each configuration.

Tasks

Complete the provided HashTable class that can insert, search, and delete elements using the hashFunction method.

Complete the provided SpellChecker class that takes a string as input, check each word against the HashTable and returns a list of misspelled words.

Complete the provided HashTableTester class that tests the performance of the spell checker by measuring the time taken to check a document, the number of collisions, and the average search time for a randomly selected word.

Experiment with different hash functions and table sizes, and measure the performance of each configuration using the method implemented in the HashTableTester class.

Comment on the results of the experiments at the top of your source code.

Instructions

The documents are provided in a plain text format. You should use a way to parse it into a list of words. (For example: splitting the text by spaces)

You must use the provided HashTable, SpellChecker, and HashTableTester classes in your solution.

You should be able to analyse the performance of your implementation in terms of time and space complexity.

You should experiment with different hash functions and different table sizes.

You should report the results of your experiments and complexity analysis in the comments of your source code.

Hand in the java file containing the HashTable, spellChecker and the HashTableTester class.

Skeletons (src code)

HashTable.java

import java.util.LinkedList;

import java.util.List;

class HashTable {

private final int SIZE = 256;

private LinkedList[] table;

public HashTable() {

table = new LinkedList[SIZE];

for (int i = 0; i < SIZE; i++) {

table[i] = new LinkedList<>();

}

}

public void insert(String word) {

// TODO: Implement this method - it should insert the word into the HashTable at the appropriate index

}

public String get(String word){

// TODO: Implement this method - it should return the word if it exists in the HashTable

// If the word doesn't exist in the HashTable, don't return it.

}

public int hashFunction(String word) {

// TODO: Hash function goes here

// Input: String to be hashed

// Output: Hashcode of the input String

}

public boolean search(String word) {

int index = hashFunction(word);

return table[index].contains(word);

}

public void delete(String word) {

int index = hashFunction(word);

table[index].remove(word);

}

public List[] getTable() {

return table;

}

}

SpellChecker.java

import java.io.File;

import java.io.IOException;

import java.util.*;

public class SpellChecker {

/*

-- To test this class (in the command prompt):

-- Use the cd command to navigate to the directory where your java files are stored, then compile:

javac SpellChecker.java

-- Then run the following command:

java SpellChecker

-- Example:

java SpellChecker This is spelled correctly

*/

public static boolean checkWord(String word, HashTable dictionary) {

// TODO: check if the (hashed) word exists in the dictionary

// output: if the word is in the dictionary, return true

}

public static List checkSeveralWords(List words, HashTable dictionary) {

// This method takes in several words to check, checks them, and then removes them from the list of words to check.

for (int i = words.size()-1; i>=0; i--){

if (checkWord(words.get(i), dictionary)){

words.remove(i);

}

}

return words;

}

public static void main(String[] args) throws IOException{

// read the dictionary file and create a HashTable

File dictionaryFile = new File("dictionary.txt");

HashTable dictionary = new HashTable();

try (Scanner sc = new Scanner(dictionaryFile)) {

while (sc.hasNext()) {

dictionary.insert(sc.next());

}

}

// Test the spell checker

List wordsToCheck = new ArrayList(Arrays.asList(args));

System.out.println("The following words are not spelled correctly, according to our dictionary: " + checkSeveralWords(wordsToCheck, dictionary));

}

}

HashTableTester.java

import java.io.File;

import java.io.IOException;

import java.util.ArrayList;

import java.util.List;

import java.util.Random;

import java.util.Scanner;

class HashTableTester {

private static Random rand = new Random();

public static void main(String[] args) throws IOException {

// read the dictionary file and create a HashTable

File dictionaryFile = new File("dictionary.txt");

HashTable dictionary = new HashTable();

// If you want, you can include different Hashtable implementations here.

// Store the words in memory

List words = new ArrayList<>();

try (Scanner sc = new Scanner(dictionaryFile)) {

while (sc.hasNext()) {

words.add(sc.next());

}

}

testHashTable(words, dictionary);

}

public static void testHashTable(List words, HashTable table) {

long startTime = System.currentTimeMillis();

for (String word : words) {

table.insert(word);

}

long endTime = System.currentTimeMillis();

System.out.println("Time taken to insert all words: " + (endTime - startTime) + " ms");

int collisions = 0;

for (List list : table.getTable()) {

collisions += list.size() - 1;

}

System.out.println("Number of collisions: " + collisions);

startTime = System.currentTimeMillis();

for (int i = 0; i < 10000; i++) {

// Search for a random word

String testWord = words.get(rand.nextInt(words.size()));

table.search(testWord);

}

endTime = System.currentTimeMillis();

System.out.println("Time taken to search for 10,000 words: " + (endTime - startTime) + " ms");

}

}

dictionary.txt

a aa aaa aah aahed aahing aahs aal aalii aaliis aals aam aani aardvark aardvarks aardwolf aardwolves aargh aaron aaronic aaronical aaronite aaronitic aarrgh aarrghh aaru aas aasvogel aasvogels ab aba ababdeh ababua abac abaca abacay abacas abacate abacaxi abaci abacinate abacination abacisci abaciscus abacist aback abacli abacot abacterial abactinal abactinally abaction abactor abaculi abaculus abacus abacuses abada abaddon abadejo abadengo abadia abadite abaff abaft abay abayah abaisance abaised abaiser abaisse abaissed abaka abakas abalation abalienate abalienated abalienating abalienation abalone abalones abama abamp abampere abamperes abamps aband abandon abandonable abandoned abandonedly abandonee abandoner abandoners abandoning abandonment abandonments abandons abandum abanet abanga abanic abannition abantes abapical abaptiston abaptistum abarambo abaris abarthrosis abarticular abarticulation abas abase abased abasedly abasedness abasement abasements abaser abasers abases abasgi abash abashed abashedly abashedness abashes abashing abashless abashlessly abashment abashments abasia abasias abasic abasing abasio abask abassi abassin abastard abastardize abastral abatable abatage abate abated abatement abatements abater abaters abates abatic abating abatis abatised abatises abatjour abatjours abaton abator abators abattage abattis abattised abattises abattoir abattoirs abattu abattue abatua abature abaue abave abaxial abaxile abaze abb abba abbacy abbacies abbacomes abbadide abbaye abbandono abbas abbasi abbasid abbassi abbasside abbate abbatial abbatical abbatie abbe abbey abbeys abbeystead abbeystede