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

Question

Write a spell checker class 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, since 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 inbetween two adjacent characters in a word, deleting a single character from a word, and replacing a character in a word with another character. for an extra challenge, consider phonetic substitutions as well.

I am having a hard time following this,I've seen other posts that answer this, but when I try to run it I get a lot of errors. The language is C++. Id love it to be easy to understand as in teling me this part is for the header file , or this textfile needs to be added under the source file. Thankyou so much!!

Explanation / Answer

The required code for the above stated problem statement is as follows:

#include <iostream>

#include <fstream>

#include <cctype>

#include <cstring>

#include <string>

#include <iomanip>

#include <ctime>

#include <limits>

#include "HashTable.h"

using namespace std;

typedef HashTable<string>::Iterator iterHT;

const int TBL_SIZE = 19000;

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

void printTbl(HashTable<string>& ht);

int spellChck(HashTable<string>& ht, string spelling);

string TLC(string spelling);

int main()

{

// declare variables

int res = 0;

string input;

string curr;

clock_t first;

clock_t fin;

char res;

ifstream ifile;

HashTable<string> ht(TBL_SIZE);

ifile.open("dict.txt");

if(ifile.fail())

{

cout<<"nn**ERROR - The dictionary file could not be found...n";

exit(1);

}

cerr<<"nLoading dictionary....";

first = clock(); // start the timer

while(ifile >> curr)

{

if(!ht.Count(curr))

{

ht.Insert(curr);

}

}

ifile.close();

printTbl(ht);

fin = clock()-first;

cout<<"nnDictionary loaded in "<<

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

cout<<endl;

cout.fill('-');

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

do{

cout<<"n>> Please enter a sentence: ";

getline(cin,input);

cout<<endl;

char* splitInput = strtok(const_cast<char*>(input.c_str()),DEL);

while(splitInput!=NULL)

{

curr = splitInput;

curr = TLC(curr);

res += spellChck(ht,curr);

splitInput = strtok(NULL,DEL);

}

if(res > 0)

{

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

res = 0;

}

// ask for more data

cout<<"nDo you want to enter another sentence? (mm/n): ";

cin >> res;

cin.ignore(numeric_limits<streamsize>::max(),' ');

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

cout<<"nBYE!!n";

return 0;

}

void printTbl(HashTable<string>& ht)

{

int largeBuck = -9999999;

int largeIndex = 0;

int smallBuck = 9999999;

int smallIndex = 0;

double buckUsed = 0;

ofstream outfile("dict.txt");

for(int pp=0; pp < ht.TableSize(); ++pp)

{

// iterator is used to traverse each hashtable bucket

iterHT ht = ht.begin(pp);

if(!ht.IsEmpty(pp))

{

if(smallBuck > ht.BucketSize(pp))

{

smallBuck = ht.BucketSize(pp);

smallIndex = pp;

}

if(largeBuck < ht.BucketSize(pp))

{

largeBuck = ht.BucketSize(pp);

largeIndex = pp;

}

++buckUsed;

outfile<<"nBucket #"<<pp<<": ";

for(int mm = 0; mm < ht.BucketSize(pp); ++mm)

{

outfile <<" "<< ht[mm] << endl;

}

}

}

cout<<"Complete!n";

cout<<endl;

cout.fill('-');

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

cout<<"Total dictionary words = "<<ht.TotalElems()<<endl

<<"Hash table size = "<<ht.TableSize()<<endl

<<"Largest bucket size = "<<largeBuck<< " items at index #"<<largeIndex<<endl

<<"Smallest bucket size = "<<smallBuck<< " items at index #"<<smallIndex<<endl

<<"Total buckets used = "<<buckUsed<<endl

<<"Total percent of hash table used = "<<(buckUsed/ht.TableSize())*100<<"%"<<endl

<<"Average bucket size = "<<(ht.TotalElems()/buckUsed)<<" items";

}

int spellChck(HashTable<string>& ht, string spelling)

{

int res = 0;

int alternatives = 0;

string rm[256];

int numRM=0;

if(!ht.Count(spelling))

{

++res;

cout<<"** "<<spelling<<": ";

for(unsigned pp = 0; pp < spelling.length(); ++pp)

{

string alter = spelling;

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

{

alter[pp] = ch;

if(ht.Count(alter))

{

cout<<alter<<", ";

rm[numRM++] = alter;

++alternatives;

ht.Remove(alter);

}

string ins = spelling.substr(0, pp) + ch + spelling.substr(pp);

if(ht.Count(ins))

{

cout<<ins<<", ";

rm[numRM++] = ins;

++alternatives;

ht.Remove(ins);

}

}

}

for(unsigned pp = 0; pp < spelling.length()-1;++pp)

{

string trans = spelling.substr(0,pp) + spelling[pp+1] + spelling[pp] + spelling.substr(pp+2);

if(ht.Count(trans))

{

cout<<trans<<", ";

rm[numRM++] = trans;

++alternatives;

// rm the entry so ht isnt displayed multiple times

ht.Remove(trans);

}

string del = spelling.substr(0, pp)+ spelling.substr(pp + 1);

if(ht.Count(del))

{

cout<<del<<", ";

rm[numRM++] = del;

++alternatives;

// rm the entry so ht isnt displayed multiple times

ht.Remove(del);

}

}

while(numRM>=0)

{

ht.Insert(rm[numRM--]);

}

if(alternatives < 1)

{

cout<<"No spelling alternatives found...";

}

cout<<endl<<endl;

}

return res;

}

string TLC(string spelling)

{

for(unsigned pp = 0; pp < spelling.length(); ++pp)

{

spelling[pp] = tolower(spelling[pp]);

}

return spelling;

}

Please rate the answer if it helps......Thankyou

Hope it helps....

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.