C Programming & Data Structures: Need help ASAP on spellchecker code for a hasht
ID: 3726830 • Letter: C
Question
C Programming & Data Structures: Need help ASAP on spellchecker code for a hashtable!
The code compiles but there is an issue the code that compares levenshtein values and places the value in the hashtable. Please help me correct it ASAP!! Code is provided below. ALSO, please check the "create & print array" section! Thank you!!
CODE:
#include "hashMap.h"
#include <assert.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
* Allocates a string for the next word in the file and returns it. This string
* is null terminated. Returns NULL after reaching the end of the file.
* @param file
* @return Allocated string or NULL.
*/
char* nextWord(FILE* file)
{
int maxLength = 16;
int length = 0;
char* word = malloc(sizeof(char) * maxLength);
while (1)
{
char c = fgetc(file);
if ((c >= '0' && c <= '9') ||
(c >= 'A' && c <= 'Z') ||
(c >= 'a' && c <= 'z') ||
c == ''')
{
if (length + 1 >= maxLength)
{
maxLength *= 2;
word = realloc(word, maxLength);
}
word[length] = c;
length++;
}
else if (length > 0 || c == EOF)
{
break;
}
}
if (length == 0)
{
free(word);
return NULL;
}
word[length] = '';
return word;
}
/**
* Loads the contents of the file into the hash map.
* @param file
* @param map
*/
void loadDictionary(FILE* file, HashMap* map)
{ // FIXME: implement
char* word = nextWord(file);
while (word) {
hashMapPut(map, word, 1);
free(word);
word = nextWord(file);
}
free(word);
}
/*************************
* Minimum function--returns the min
* ******************/
int min(int a, int b, int c)
{
int minimum;
minimum = a;
if(b < minimum) {
minimum = b;
}
if(c < minimum) {
minimum = c;
}
return minimum;
}
/*********************
* min2 function
* ********************/
int min2(int a, int b) {
int min;
if (a < b)
min = a;
else
min = b;
return min;
}
/**********************************
* HELPER FUNCTION
* code sourced from https://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance
* code has been modified to work with hashtables
* *********************************/
// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
{
int cost;
/* base case: empty strings */
if (len_s == 0) return len_t;
if (len_t == 0) return len_s;
/* test if last characters of the strings match */
if (s[len_s-1] == t[len_t-1])
cost = 0;
else
cost = 1;
/* return minimum of delete char from s, delete char from t, and delete char from both */
return min(LevenshteinDistance(s, len_s - 1, t, len_t ) + 1,
LevenshteinDistance(s, len_s , t, len_t - 1) + 1,
LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}
/**
* Prints the concordance of the given file and performance information. Uses
* the file input1.txt by default or a file name specified as a command line
* argument.
* @param argc
* @param argv
* @return
*/
int main(int argc, const char** argv)
{ // FIXME: implement
HashMap* map = hashMapNew(1000);
FILE* file = fopen("dictionary.txt", "r");
//if file not found
if(file==NULL)
{
perror("Error");
}
clock_t timer = clock();
loadDictionary(file, map);
timer = clock() - timer;
printf("Dictionary loaded in %f seconds ", (float)timer / (float)CLOCKS_PER_SEC);
fclose(file);
char inputBuffer[256];
int quit = 0;
while (!quit) //Step 4: continue to prompt user for word until they type quit
{
printf("Enter a word or "quit" to quit: ");
scanf("%s", inputBuffer);
// Implement the spell checker code here..
/***** NEED HELP WITH THIS FUNCTION!!!!
* Compare input Buffer to words in the dictionary, computing their Levenshtein distance.
* Store that distance as the value for each key in the table
* *********************/
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
if (link != NULL)
{
while (link != NULL)
{
int bLength = strlen(inputBuffer);
int mapL = map->capacity;
char* word = link->key;
int minVal = LevenshteinDistance(word, mapL, inputBuffer, bLength);
hashMapPut(map, word, minVal);
link = link->next;
}
}
}
/*****
* Traverse down hash table, checking each bucket.
* Jump out if you find an exact matching dictionary word
* print a message that "word spelled correctly"
* **********************/
if (hashMapContainsKey(map, inputBuffer))
{
printf("That word is spelled correctly! ");
}
/************
* If the input Buffer did not match any of the dictionary words exactly,
* generate an array of 5 words that are the closest matches to input Buffer based
* on the LOWEST Levenshtein distance.
* print the array INCLUDING the message "did you mean ...?"
* ********************/
else
{
char* array[6];
for(int idx = 0; idx < 6; idx++){
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
HashLink* nLink = map->table[i+1];
if (nLink != NULL) {
int val = *(hashMapGet(map, link->key));
int val2 = *(hashMapGet(map, nLink->key));
if(min2(val, val2) == val){
array[idx] = link->key;
}
else {
array[idx] = nLink->key;
}
nLink = nLink->next;
}
link = link->next;
}
}
/* Print the new map */
for (int i = 0; i < 6; i++)
{
printf("%sDid you mean ...? ", array[i]);
printf(" ");
}
}
if (strcmp(inputBuffer, "quit") == 0)
{
quit = 1;
}
}
hashMapDelete(map);
return 0;
}
Explanation / Answer
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "dictionary.h"
// Number of linked lists in hash table.
#define HASH_SIZE 2000
// Each element in linked list is a node. Node contains
// a word and a pointer to the next node.
typedef struct node
{
char word[LENGTH + 1];
struct node* next;
}
node;
// Hash table is an array of linked lists.
node* hashtable[HASH_SIZE];
int hash_function(const char* word);
// Tracks number of words in dictionary.
int number_of_words = 0;
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
int word_length = strlen(word);
char lower_word[LENGTH+1];
// Convert word to lowercase to accurately compare to hash table.
for (int i = 0; i < word_length; i++)
{
// If character is uppercase, make it lowercase.
if(isupper(word[i]))
{
lower_word[i] = tolower(word[i]) ;
}
// Otherwise it's already lowercase or it's not a letter.
else
{
lower_word[i] = word[i];
}
}
// Add null character to end of char array.
lower_word[word_length] = '';
// Use hash function to find correct "bucket" to place word.
int bucket = hash_function(lower_word);
// Set cursor to first node in bucket.
node* cursor = hashtable[bucket];
// Until the end of the linked list is reached (cursor == NULL),
// compare each word stored in each node to lower_word. If they're
// the same, then the word is in the dictionary and is not mispelled.
// Otherwise, it is spelled incorrectly.
while (cursor != NULL)
{
if (strcmp(lower_word, cursor->word) == 0)
{
// If lowercase'd word is the same as another in the bucket,
// it's a match and return true.
return true;
}
cursor = cursor->next;
}
return false;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char* dictionary)
{
// Initialize each value in hash table to NULL.
for(int i = 0; i < HASH_SIZE; i++)
{
hashtable[i] = NULL;
}
// Open the dictionary text file.
FILE* the_dictionary;
the_dictionary = fopen(dictionary, "r");
// Check if dictionary opened correctly.
if (the_dictionary == NULL)
{
printf("Failed to load dictionary");
return false;
}
char buffer[LENGTH+1];
// Loop through file until end of file is reached.
// Save each word in buffer.
while (fscanf(the_dictionary, "%s", buffer) > 0)
{
// Allocate memory for a new node.
node* new_node = malloc(sizeof(node));
// Set node's next pointer to NULL.
new_node->next = NULL;
// Set node's word to value stored in buffer.
strcpy(new_node->word, buffer);
// Run word through hash function to set bucket in hash table.
int bucket = hash_function(new_node->word);
// If it's the first node being added to the bucket, replace
// the NULL value with the new node.
if (hashtable[bucket] == NULL)
{
hashtable[bucket] = new_node;
}
// Otherwise set new node's pointer to the first node in the linked list.
// Then set new node to be the first node in the linked list.
else
{
new_node->next = hashtable[bucket];
hashtable[bucket] = new_node;
}
// Track number of words in dictionary.
number_of_words++;
}
// Done with text file. Time to close it.
fclose(the_dictionary);
// Everything seems to have gone well, return true.
return true;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
return number_of_words;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
// Iterate over all linked lists in hash table. Set
// cursor to point at each one's location in memory.
for (int i = 0; i < HASH_SIZE;i++)
{
node* cursor = hashtable[i];
while (cursor != NULL)
{
// Set temporary pointer to point at cursor's
// location in memory. Move cursor to the next node
// so we don't lose track of it before freeing
// the current node's (temp's) memory.
node* temp = cursor;
cursor = cursor->next;
free(temp);
}
}
return true;
}
// Maps a word to an integer value to place it in the hash table.
// Sum the value of each character in the word, then find the
// remainder after dividing by the size of the hash table.
int hash_function(const char* word)
{
int sum = 0;
int word_length = strlen(word);
for (int i = 0; i < word_length; i++)
{
sum += word[i];
}
int bucket = sum % HASH_SIZE;
return bucket;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.