Write a spell checker that stores a set of words, W, in a hash table and...

Question

Question

Write a spell checker that stores a set of words, W, in a hash table and...

Write a spell checker that stores a set of words, W, in a hash table and implements a function, spellCheck(s), which performs a spell check on the string s with respect to the set of words, W.

If s is in W, then the call to spellCheck(s) returns an iterable collection that contains only s, because it is assumed to be spelled correctly in this case. Otherwise, if s is not in W, then the call to spellCheck(s) returns a list of every word in W that could be a correct spelling of s.

Your program should be able to handle all the common ways that s might be a misspelling of a word in W, including

swapping adjacent characters in a word;
inserting a single character in between two adjacent characters in a word;
deleting a single character from a word; and
replacing a character in a word with another character.

The input to your program will consist of the name of a text file, and strings of characters manually entered by the user. The text file will contain the set of words, W, one word per line, and should be read in the program when the program starts. The strings of characters input by the user will be used to test the hash table and the spellCheck function. The program will keep running the tests until the user enters the string "quit".

Create classes SpellChecker and HashTable to implement the spell checker and the hash table, respectively. Create a UML class diagram that describes your class design.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

CODE:

#include <iostream>

#include <fstream>//to handle file opening and closing

#include <cctype>

#include <cstring>

#include <string> // to handle strings

#include <iomanip>

#include <ctime>

#include <limits>

//including the self created hashtable header file

#include "HashTable.h"

using namespace std;

// declaring iterator for hash_table

typedef HashTable<string>::Iterator iterDec;

// delimiters

const char* DELIMITERS = " ,.-\':;?()+*/\\%$#!\"@\^&";

// declaring hashtable size

const int TABLE_SIZE = 29990;

// function to check the spelling of given word

int Spell_Check(HashTable<string>& hashTable, string word);

// declaring function prototypes

void Print_Table_Stats(HashTable<string>& hashTable);

//function for lowercase conversion of words

string To_Lower_Case(string word);

int main()

{

// declare variables

string filename;

//getting user file for dictionary making

cout<<"Enter the file name";

cin>> filename;

int result = 0;

//variable for storing user inputted word

string userInput;

string currWord;

clock_t beg; // required to time the hash_table load

clock_t end; // required to time the hash_table load

char response;

// file pointer to handle file

ifstream infile;

HashTable<string> hashTable(TABLE_SIZE);

// open the file containing dictionary word

infile.open(filename);

// check for the file existence, if it does not exist then EXIT

if(infile.fail())

{

cout<<"**FATAL ERROR - Sorry the dictionary file inputed by you could not be found...\n";

exit(1);

}

//throwing the processing caption

cerr<<"PLEASE WAIT Dictionary is loading........\n";

beg = clock(); // startING the timer

// fetching the data from inputted file and putting into hash table

while(infile >> currWord)

{

// avoiding duplicate words from entering the table

if(!hashTable.Count(currWord))

{//inserting the current new word into dictionary

hashTable.Insert(currWord);

}

//closing the file for safe working

infile.close();

//this function can be used for many stats related to hash table

end = clock()-beg; // ending the timer

cout<<"Your Dictionary has been loaded in "<<

(double)end / ((double)CLOCKS_PER_SEC)<<" secs!";

//showing the time in which we have created the dictonary

// creating the line separator

cout<<endl;

cout.fill('-');

//filling the whole line with '-'

cout<<left<<setw(50)<<""<<endl;

do{ // getting user input for words/sentences

cout<<" Please enter a sentence/word: ";

getline(cin,userInput);

//storing the user input

cout<<endl;

// breaking the sentence into individual words for checking spelling of each

char* splitInput = strtok(const_cast<char*>(userInput.c_str()),DELIMITERS);

while(splitInput!=NULL)

{//spilliting the words

currWord = splitInput;

//conversion of words to lower case

currWord = To_Lower_Case(currWord);

result += Spell_Check(hashTable,currWord);

splitInput = strtok(NULL,DELIMITERS);

}

// displaying results

if(result > 0)

{//showing the number of words which are misspelled

cout<<"Number of words spelled incorrectly: "<<result<<endl;

result = 0;

}

// ask for more data

cout<<"Do you want to enter few another sentence/words? (y/quit): ";

//recording the user response

cin >> response;

cin.ignore(numeric_limits<streamsize>::max(),'\n'); // clear the cin buffer

}while(toupper(response)=='Y');

cout<<"BYE the dictionary exits!!n";

return 0;

}// end of main

int Spell_Check(HashTable<string>& hashTable, string word)

{//declaring variables

int result = 0;

int suggestions = 0;

//declaring string array of size 256 words

string remove[256];

int numRemove=0;

//if hashtable have words then

if(!hashTable.Count(word))

{

++result;

cout<<"** "<<word<<": ";

// checking for alteration & insertion in word

for(unsigned x = 0; x < word.length(); ++x)

{

string alteration = word;

for(char c = 'a'; c <= 'z'; ++c)

{

//if a alphabet is altered with another alphabet

alteration[x] = c;

if(hashTable.Count(alteration))

{

cout<<alteration<<", ";

remove[numRemove++] = alteration;

++suggestions;

// removing the entries so that every entry is present only once

hashTable.Remove(alteration);

}

// checking for insertion

string insertion = word.substr(0, x) + c + word.substr(x);

//if insertion found

if(hashTable.Count(insertion))

{

cout<<insertion<<", ";

//removing that insertion

remove[numRemove++] = insertion;

++suggestions;

// remove the entry is unique not multiple times

hashTable.Remove(insertion);

}

// checking for adjacent swapping (transposition) & deletion

for(unsigned c = 0; c < word.length()-1;++c)

{

// transposition

string transposition = word.substr(0,c) + word[c+1] + word[c] + word.substr(c+2);

if(hashTable.Count(transposition))

{

cout<<transposition<<", ";

remove[numRemove++] = transposition;

++suggestions;

// remove the entry so it isnt displayed multiple times

hashTable.Remove(transposition);

}

// checking for deletion

string deletion = word.substr(0, c)+ word.substr(c + 1);

//if deletion found then

if(hashTable.Count(deletion))

{

cout<<deletion<<", ";

//recording that deletion

remove[numRemove++] = deletion;

++suggestions;

// remove the entry to avoid multiple apperance

hashTable.Remove(deletion);

}

// placing the removed items back into the hashtable

while(numRemove>=0)

{//inserting item

hashTable.Insert(remove[numRemove--]);

}

//if no suggestions are found

if(suggestions< 1)

{

cout<<"Sorry No spelling suggestion found...";

}

cout<<endl<<endl;

}

//returniing the spell check result

return result;

}// end of Spell_Check

//function for conversion of word string to lower case

string To_Lower_Case(string word)

{//converting everyword to its lowercase

for(unsigned c = 0; c < word.length(); ++c)

{//using tolower functio for lower case conversion

word[c] = tolower(word[c]);

}

//returning the lowercase word

return word;

}// end of To_Lower_Case

//hashtable.h

#ifndef TEMPLATE_HASH_TABLE

#define TEMPLATE_HASH_TABLE

#include <iostream>

#include <string>

#include <sstream>

#include <cstdlib>

// if user doesnt define, this is the

// default hash table size

const int HASH_SIZE = 100;

template <class ItemType>

class HashTable

{

public:

HashTable(int hashSze = HASH_SIZE);

/* Function: Constructor initializes hash table

Precondition: None

Postcondition: Defines private variables */

bool IsEmpty(int key);

/* Function: Determines whether hash table is empty at the given key

Precondition: Hash table has been created

Postcondition: The function = true if the hash table is empty and the

function = false if hash table is not empty */

bool IsFull();

/* Function: Determines whether hash table is full

Precondition: Hash table has been created

Postcondition: The function = true if the hash table is full and the

function = false if hash table is not full */

int Hash(ItemType newItem);

/* Function: Computes and returns a unique hash key for a given item

The returned key is the given cell where the item resides

Precondition: Hash table has been created and is not full

Postcondition: The hash key is returned */

void Insert(ItemType newItem);

/* Function: Adds newItem to the back of the list at a given key in the hash table

A unique hash key is automatically generated for each newItem

Precondition: Hash table has been created and is not full

Postcondition: Item is in the hash table */

void Append(int key, ItemType newItem);

/* Function: Adds new item to the end of the list at a given

key in the hash table

Precondition: Hash table has been created and is not full

Postcondition: Item is in the hash table */

bool Remove(ItemType deleteItem, int key = -1);

/* Function: Removes the first instance from the table whose value is "deleteItem"

Optional second parameter indicates the key where deleteItem is located

Precondition: Hash table has been created and is not empty

Postcondition: The function = true if deleteItem is found and the

function = false if deleteItem is not found */

void Sort(int key);

/* Function: Sort the items in the table at the given key