C++ Programming Write a spell checker class that stores a set of words, W, in a

Question

C++ Programming

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.

Please also create an example of the wordlist. Also please indicate what code goes under which .cpp or .h or main.cpp file.

Explanation / Answer

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <limits>

template<typename Sequence>
inline bool read_into_sequence(const std::string& file_name, Sequence& buffer)
{
std::ifstream file(file_name.c_str());
if (!file) return false;
std::string line;
while (std::getline(file,line))
{
buffer.push_back(line);
}
file.close();
}

unsigned int ap_hash(const std:string& str)
{
unsigned int hash = 0xAAAAAAAA;

for(std::size_t i = 0; i &lt; str.length(); i++)
{
hash ^= ((i & 1) == 0) ? ( (hash &lt;&lt; 7) ^ str[i] * (hash &gt;&gt; 3)) :
(~((hash &lt;&lt; 11) + str[i] ^ (hash &gt;&gt; 5)));
}
return hash;
}

template<typename StrSequence, typename HashFunction, typename IntSequence>
void collision_test(const StrSequence& str_list,
const HashFunction& function,
const IntSequence& quantizer_list)
{
typedef std::map<unsigned int, unsigned int> hash_value_list_type;
std::vector<hash_value_list_type> hvl(quantizer_list.size());
for(StrSequence::const_iterator it = str_list.begin(); it != str_list.end(); ++it)
{
unsigned int hvlit = 0;
for(IntSequence::const_iterator qit = quantizer_list.begin(); qit != quantizer_list.end(); ++qit, ++hvlit)
{
unsigned int hash_value = function(*it) % (*qit);
hash_value_list_type::iterator hash_it = hvl[hvlit].find(hash_value);
if (hash_it != hvl[hvlit].end())
hash_it->second++;
else
hvl[hvlit].insert(std::make_pair<unsigned int, unsigned int>(hash_value,1));
}
}

for(std::vector<hash_value_list_type>::iterator hvlit = hvl.begin(); hvlit != hvl.end(); ++hvlit)
{
unsigned int total_collisions = 0;
for(hash_value_list_type::iterator it = (*hvlit).begin(); it != (*hvlit).end(); ++it)
{
if (it->second &gt; 1)
{
total_collisions += (it->second - 1);
}
}
std::cout &lt;&lt; total_collisions &lt;&lt; " ";
}
std::cout &lt;&lt; std::endl;
}

int main()
{
std::vector<std::string> str_list;

if (read_into_sequence("words.txt", str_list))
{
std::cout &lt;&lt; "ERROR - Could not read list!" &lt;&lt; std::endl;
return 1;
}

std::vector<unsigned int> quantizer_list;
quantizer_list.push_back(std::numeric_limits<unsigned int>::max());

quantizer_list.push_back(256); quantizer_list.push_back(512);
quantizer_list.push_back(1024); quantizer_list.push_back(2048);
quantizer_list.push_back(4096); quantizer_list.push_back(7477);
quantizer_list.push_back(8011); quantizer_list.push_back(8192);
quantizer_list.push_back(8329); quantizer_list.push_back(9059);
quantizer_list.push_back(16384); quantizer_list.push_back(32768);
quantizer_list.push_back(65536); quantizer_list.push_back(131072);
quantizer_list.push_back(262144); quantizer_list.push_back(469207);
quantizer_list.push_back(524288); quantizer_list.push_back(544771);
quantizer_list.push_back(711209); quantizer_list.push_back(902677);
quantizer_list.push_back(1048576); quantizer_list.push_back(1299289);
quantizer_list.push_back(2097152); quantizer_list.push_back(4194304);
quantizer_list.push_back(8388608); quantizer_list.push_back(16777216);

collision_test(str_list,ap_hash,quantizer_list);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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