469,927 Members | 1,790 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,927 developers. It's quick & easy.

Spell Checker

Ganon11
3,652 Expert 2GB
Hey all,

So this was an assignment in my Data Structures and Algorithms class - we were supposed to make a C++ implementation of the spell checker described here. A Java version was also provided, which I pretty much stole line for line (translating as necessary, of course). I got the program working...most of the time. I'll post the code below.

Basically, my program reads in the big.txt file, and puts all the valid words into a map (key is string, value is int). If the word is already in the map, it increments the int (so that the int reflects how often the word appeared).

After the file has been read, my driver program asks the user for a misspelled word. Once it has this word, the driver program calls the correct method. This method checks, in this order: (1) If the word is found in the map (in which case it is valid, and we don't need to do anything else), (2) If a word within edit distance 1 (that is, adding 1 letter, deleting one letter, switching two letters, or altering one letter) is in the map (in which case it is a valid substitution, and is returned), and (3) If a word within edit distance 2 is found in the map (in which case it is a valid substitution, and is returned).

Here's the code:

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <fstream>
  5. #include <cctype>
  6. using namespace std;
  7.  
  8. class SpellCheck {
  9.     public:
  10.         SpellCheck(string filename) {
  11.             ifstream in(filename.c_str());
  12.             string temp;
  13.             while (in) {
  14.                 getline(in, temp);
  15.                 string word;
  16.                 while (temp.length() > 0) {
  17.                     if (nextWord(temp, word)) {
  18.                         map<string, int>::iterator itr = nWords.find(word);
  19.                         if (itr == nWords.end()) {
  20.                             nWords.insert(pair<string, int>(word, 1));
  21.                         } else {
  22.                             (*itr).second++;
  23.                         }
  24.                     }
  25.                 }
  26.             }
  27.             in.close();
  28.         }
  29.  
  30.         string correct(string word) {
  31.             if (nWords.find(word) != nWords.end()) return word;
  32.             vector<string> edit1 = edits(word);
  33.             map<int, string> candidates;
  34.             for (int i = 0; i < edit1.size(); i++) {
  35.                 map<string, int>::iterator itr = nWords.find(edit1[i]);
  36.                 if (itr != nWords.end()) {
  37.                     pair<string, int> myPair = *itr;
  38.                     candidates.insert(pair<int, string>(myPair.second, myPair.first));
  39.                 }
  40.             }
  41.             if (candidates.size() > 0) {
  42.                 map<int, string>::iterator itr = candidates.begin();
  43.                 pair<int, string> max = *itr;
  44.                 itr++;
  45.                 while (itr != candidates.end())
  46.                     if ((*itr).first > max.first) max = *itr;
  47.                 return max.second;
  48.             }
  49.             candidates.clear();
  50.             for (int i = 0; i < edit1.size(); i++) {
  51.                 vector<string> edit2 = edits(edit1[i]);
  52.                 for (int i = 0; i < edit2.size(); i++) {
  53.                     map<string, int>::iterator itr = nWords.find(edit2[i]);
  54.                     if (itr != nWords.end()) {
  55.                         pair<string, int> myPair = *itr;
  56.                         candidates.insert(pair<int, string>(myPair.second, myPair.first));
  57.                     }
  58.                 }
  59.             }
  60.             if (candidates.size() > 0) {
  61.                 map<int, string>::iterator itr = candidates.begin();
  62.                 pair<int, string> max = *itr;
  63.                 itr++;
  64.                 while (itr != candidates.end())
  65.                     if ((*itr).first > max.first) max = *itr;
  66.                 return max.second;
  67.             }
  68.             return word;
  69.         }
  70.  
  71.     private:
  72.         vector<string> edits(string word) {
  73.             vector<string> result;
  74.             string temp;
  75.             for (int i = 0; i < word.length(); i++) {
  76.                 temp = word.substr(0, i) + word.substr(i+1);
  77.                 result.push_back(temp);
  78.             }
  79.             for (int i = 0; i < word.length() - 1; i++) {
  80.                 temp = word.substr(0, i) + word[i+1] + word[i] + word.substr(i+2);
  81.                 result.push_back(temp);
  82.             }
  83.             for (int i = 0; i < word.length(); i++) {
  84.                 for (char c = 'a'; c <= 'z'; c++) {
  85.                     temp = word.substr(0, i) + c + word.substr(i+1);
  86.                     result.push_back(temp);
  87.                 }
  88.             }
  89.             for (int i = 0; i < word.length() + 1; i++) {
  90.                 for (char c = 'a'; c <= 'z'; c++) {
  91.                     temp = word.substr(0, i) + c + word.substr(i);
  92.                     result.push_back(temp);
  93.                 }
  94.             }
  95.             return result;
  96.         }
  97.  
  98.         bool nextWord(string& sentence, string& word) {
  99.             while (true) {
  100.                 int pos = sentence.find(" ");
  101.  
  102.                 if (pos != string::npos) {
  103.                     word = sentence.substr(0, pos);
  104.  
  105.                     sentence = sentence.substr(pos);
  106.                     while (sentence.length() > 0 && !isalpha(sentence[0])) {
  107.                         sentence = sentence.substr(1);
  108.                     }
  109.                     bool isWord = true;
  110.                     for (int i = 0; i < word.length(); i++) {
  111.                         if (isalpha(word[i])) {
  112.                             word[i] = tolower(word[i]);
  113.                         } else if (ispunct(word[i])) {
  114.                             word = word.substr(0, i) + word.substr(i+1);
  115.                         } else isWord = false;
  116.                     }
  117.                     if (!isWord) {
  118.                         continue;
  119.                     }
  120.                     return true;
  121.                 } else {
  122.                     word = sentence;
  123.                     sentence = "";
  124.                     bool isWord = true;
  125.                     for (int i = 0; i < word.length(); i++) {
  126.                         if (isalpha(word[i])) word[i] = tolower(word[i]);
  127.                         else isWord = false;
  128.                     }
  129.                     if (!isWord) {
  130.                         return false;
  131.                     }
  132.                     return true;
  133.                 }
  134.             }
  135.         }                
  136.  
  137.         map<string, int> nWords;
  138. };
And the driver program:

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include "SpellCheck.h"
  3. using namespace std;
  4.  
  5. int main() {
  6.     string filename = "big.txt";
  7.     SpellCheck checker(filename);
  8.  
  9.     char choice = 'y';
  10.     while (tolower(choice) == 'y') {
  11.         cout << "Enter a word to check: ";
  12.         string word;
  13.         cin >> word;
  14.         cout << "Did you mean " << checker.correct(word) << "?" << endl;
  15.         cout << endl;
  16.         cout << "Do you wish to continue (Y/N)? ";
  17.         cin >> choice;
  18.     }
  19.     return 0;
  20. }
Here are a few sample runs:

Expand|Select|Wrap|Line Numbers
  1. $ SCTest
  2. Enter a word to check: speling
  3. Did you mean spelling?
  4.  
  5. Do you wish to continue (Y/N)? y
  6. Enter a word to check: spleling
  7. Did you mean spelling?
  8.  
  9. Do you wish to continue (Y/N)? y
  10. Enter a word to check: monkee
  11. Did you mean monkey?
  12.  
  13. Do you wish to continue (Y/N)? y
  14. Enter a word to check: freedmo
  15. Did you mean freedom?
  16.  
  17. Do you wish to continue (Y/N)? n
So, as you can see, it's working correctly for several words. I have also tried the word "acommodate" (incorrect spelling of accommodate), and it works correctly (this error was within edit distance 2). However, when I input "teh" and "wierd" (for "the" and "weird", respectively), my program freezes.

I've already gotten full credit for this assignment (and, as a matter of fact, so did everyone else, even though most people didn't even get it half-working like mine), so there's no grade on the line (and more importantly, no cheating involved) - but does anyone know why it's hanging on these specific words?
Oct 17 '07 #1
2 11259
Ganon11
3,652 Expert 2GB
I found and fixed 2 errors:

1) Inside the correct() method, I used a set of nested for loops...but tried to use i for both. Whoops. Made it a j.
2) The word accepted to correct() was not necessarily all lowercase, so I added a method to make it all lowercase before continuing.

It still hangs for certain words.
Nov 1 '07 #2
@Ganon11

what is your header file "spellcheck.h" work
Mar 22 '16 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

4 posts views Thread by Leo P. | last post: by
2 posts views Thread by WM Chung | last post: by
7 posts views Thread by Hank Reed | last post: by
8 posts views Thread by Joe | last post: by
6 posts views Thread by Neil | last post: by
22 posts views Thread by SmokeWilliams | last post: by
3 posts views Thread by Mike | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.