Make this program using c++ The problem: Spell checker, an application of hashin
ID: 3740387 • Letter: M
Question
Make this program using c++
The problem: Spell checker, an application of hashing
Many applications such as word processors, text editors, and email clients, include a spell- checking feature. A spell checker's task is centered around searching for words in a potentially large wordlist and reports all of the misspelled words (i.e. words that are not found in the wordlist). An efficient search is critical to the performance of the spell checker, since it will be searching the wordlist not only for the words in the input, but possibly suggestions that it might like to make for each misspelling.
Objective
Implement a spell checker that reads a wordlist from a file (wordlist.txt), stores the list of words in a hash table using separate chaining (i.e. linked lists) to resolve collisions, then spell- check an input file. For each misspelling found in the input file, your program will report it, along with a list of 5 suggestions (i.e. 5 closest words from the wordlist).
Suggested closest words
Definition of closest in this assignment follows the Hamming-Distance concept. Distance between two strings follows the algorithm below:
For two strings A, B.
A match occurs at position k if A(k) = B(k).
M = # of matches
Distance = Number of mismatches D = max (length(A) , length(B)) – M
D = 0 if A and B are identical
For each misspelled word, starting with the same first character find the list of five closest words from the wordlist using the above algorithm.
Hashing function
Your spell checker is case insensitive. The hashing function is h2(h1(key)) where key is the string such that:
L?1
• TheHashcodemap:h(S)= int(S)?i,where?=26.
? i=0
i
1
• The Compression Map: h2(K)?[0, N-1], where N is the table size
The hashTable ADT
The hashTable ADT can be implemented using a Simple Linked List (SLL) with the following member functions:
Constructor: Construct an empty table
Destructor: Destroy table
MakeTableEmpty: Empty whole table
TableIsEmpty : Return True if table is empty
TableIsFull : Return True if table is full
Occupancy: Return number of occupied slots
Insert: Insert key and data in a slot
Search: Search for a key
Retrieve: Retrieve the data part of the current slot
Update: Update the data part of the current slot
Traverse: Traverse whole table
Required Implementation:
Design and implement a template class hashTable using a SLL with a minimum of the above member functions.
Read and store each entry in the file wordlist.txt in the hash table using separate chaining to resolve collisions.
Spell check an input file such that for each misspelled word list 5 suggestions from the wordlist that are closest to it based on the Hamming Distance measure.
Explanation / Answer
//main.cpp
#include <iostream>
#include <fstream>
#include "hashTable.h"
#include "hashTable.cpp"
#include <string>
using namespace std;
void opening (ifstream &file, const string& filename);
void fillTable(hashTable<double, string> &, string &filename);
void lowerCase (string&);
void spellCheck (hashTable<double, string>& , string &filename);
int main() {
hashTable <double, string> a;
string filename, check;
cout<<"Please type in filename with .txt extension with the dictionary : ";
cin>>filename;
fillTable(a, filename);
cout<<"Imported words successfully, enter name of file to spell check with .txt extension: ";
cin>>check;
spellCheck(a, check);
return 0;
}
void opening (ifstream &file, const string& filename)
{ file.open(filename);
if (file.is_open())
return;
else
cout << "Could not open " << filename;
}
void fillTable(hashTable<double, string> &a, string &filename)
{
ifstream file;
opening (file, filename);
string temp;
while (file.good()) {
getline(file, temp);
lowerCase(temp);
a.insert(temp);
}
file.close();
}
void lowerCase (string& a){
string temp="";
for (int i =0; i<a.length(); i++){
temp+= char(tolower(int(a[i])));
}
a = temp;
}
void spellCheck (hashTable<double, string>&a , string &filename){
ifstream file;
bool found;
string word;
char c;
opening(file, filename);
if (file.is_open()) {
while (file.good()) {
while ((file.good()) && !isspace(file.get())) {
file.get(c);
word += c;
}
found = a.search(word);
if (!found) {
cout<<"Misspelled word found: "<<word;
a.Suggest(word);
cout<<endl;
}
word = "";
}
}
}
----------------------------------------------------------------------------------------------
//hashTable.cpp
#include "hashTable.h"
#include <iostream>
#include <cmath>
using namespace std;
template <class keyType, class dataType>
hashTable<keyType, dataType>::hashTable()
{
MaxSize = 149;
T = new slot[MaxSize];
Empty = 0;
for (int i=0; i<MaxSize; i++)
{ T[i].key = Empty;
T[i].next = nullptr; }
h = 0;
csize = 0;
}
template <class keyType, class dataType>
hashTable<keyType, dataType>::~hashTable() {
/* slot * temp1, *temp2;
for (int i =0; i<MaxSize; i++) {
temp1 = T[i].next;
T[i].next = nullptr;
temp2 = temp1;
while ((temp1 != nullptr) && (temp2 != nullptr)){
temp2 = temp1->next;
delete temp1;
temp1 = temp2->next;
delete temp2;
}
}
delete T;*/
}
template <class keyType, class dataType>
void hashTable<keyType,dataType>::makeTableEmpty(const keyType &k) {
slot *temp1, *temp2;
Empty = k;
for (int i = 0; i<MaxSize; i++) {
T[i].next = nullptr;
T[i].key = Empty;
temp1 = T[i].next;
temp2 = temp1;
while ((temp1 != nullptr) && (temp2 != nullptr)){
temp2 = temp1->next;
delete temp1;
temp1 = temp2->next;
delete temp2;
}
}
csize = 0;
}
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::tableIsEmpty() const
{
if (csize == 0)
return true;
else return false;
}
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::tableIsFull() const
{
if (csize == 60389)
return true;
else return false;
}
template <class keyType, class dataType>
void hashTable<keyType, dataType>::insert(const dataType &d)
{
keyType k;
h = hash(d, k);
csize++;
slot * temp1;;
if (tableIsFull())
return;
if (T[h].key == Empty)
{
T[h].key = k;
T[h].data = d;
T[h].next = nullptr;
return;
}
else if (T[h].key != Empty)
{
temp1 = T[h].next;
while (temp1 != nullptr)
{
temp1 = temp1->next;
}
temp1 = new slot;
//temp1 = newslot;
temp1->key = k;
temp1->data = d;
temp1->next = nullptr;
return;
}
else
cout << "failed" << endl;
}
template <class keyType, class dataType>
unsigned long hashTable<keyType, dataType>::hash(const dataType d, keyType & k) const
{
unsigned long temp = 0, n = d.length();
for (int i = 0; i < n; i++)
temp = temp + int(tolower(d[i])) * pow(26, i);
k = temp;
temp = temp % MaxSize;
return temp;
}
template <class keyType, class dataType>
void hashTable <keyType, dataType>::traverse() {
slot * temp;
for (int i = 0; i<MaxSize; i++){
if (T[i].key != Empty) {
cout<<T[i].data<<" ";
temp = T[i].next;
while (temp != nullptr){
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
}
}
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::search(const dataType& d)
{ double k;
unsigned long h = hash(d,k);
slot* temp = T[h].next;
if (T[h].key == k)
return true;
while (temp != nullptr) //Unique key
{
if (temp->key == k)
return true;
else
temp = temp->next;
}
return false;
}
template <class keyType, class dataType>
int hashTable<keyType, dataType>::Occupancy()const
{
return csize;
}
template<class keyType,class dataType>
int hashTable<keyType, dataType>::hammingDistance(const std::string &A, const std::string &B) const
{
int x ,y,M = 0,Big;
x = A.length();
y = B.length();
if (y > x)
Big = y;
else Big = x;
for (int i = 0; i <Big; i++)
{
if (A[i] == B[i])
M++;
}
return (Big-M);
}
template<class keyType, class dataType>
void hashTable<keyType, dataType>::Suggest(const string & A)
{
//Suggestions B[5];
int cpointer = 0, s, n = 5, B[5];
string temps, f, Bs [5];
char c = A[0];
slot * temp1;
temp1 = &T[cpointer];
for (int i = 0; i < n; i++)
{
if (T[cpointer].key != Empty)
{
f = temp1->data;
if (f[0] == c)
{
s = hammingDistance(A, f);
B[i] = s;
Bs[i] = f;
}
if (temp1->next != NULL)
temp1 = temp1->next;
else
{
cpointer++;
temp1 = &T[cpointer];
}
}
cpointer++;
}
order(Bs, B, n);
for (int i = cpointer; i < MaxSize; i++)
{
temp1 = &T[i];
while (temp1->next != NULL)
{
f = temp1->data;
if (f[0] == c)
{
s = hammingDistance(A, f);
if (s < B[0])
{
Bs[0]= f;
B[0]= s;
order(Bs, B, n);
}
}
temp1 = temp1->next;
}
}
for (int i = 0; i < n; i++)
{
cout << Bs[i] << " ";
}
}
template <class keyType, class dataType>
void hashTable<keyType, dataType>::order(string s[], int p[], int n)
{
int tempint;
string temps;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (p[i] < p[j + 1])
{
tempint = p[j + 1];
p[j + 1] = p[j];
p[j]= tempint;
temps = s[j + 1];
s[j + 1] = s[j];
s[j] = temps;
}
}
-------------------------------------------------------------------------------
//hashTable.h
#ifndef HASHTABLE_H
#defineHASHTABLE_H
#include <iostream>
template <class keyType, class dataType>
class hashTable {
public:
// Member Functions
hashTable();
~hashTable();
// Functions Prototype Definitions
void makeTableEmpty(const keyType &);
bool tableIsEmpty() const;
bool tableIsFull() const;
void insert(const dataType &);
bool search(const dataType &);
void Suggest(const std::string & A);
dataType retrieve(keyType k) const;
int Occupancy()const;
void Update(keyType k,dataType d);
int hammingDistance(const std::string & A, const std::string &B)const;
void traverse ();
void order(std::string s[], int p[], int n);
private:
// Slot Class
class slot
{
public:
keyType key; // key
dataType data; // Data
slot * next;
}; // end of class slot declaration
slot *T;
unsigned long h;
int MaxSize, csize;
keyType Empty;
unsigned long hash(dataType d, keyType & k) const;
};
#endif //HASHTABLE_H
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.