Question: Use the coding skeleton provided to create a spellchecker. There are a lot of uses for a hash map, and one of them is implementing
Use the coding skeleton provided to create a spellchecker.
There are a lot of uses for a hash map, and one of them is implementing a spell checker. All you need to get started is a dictionary, which is provided in dictionary.txt. In spellChecker.c you will find some code to get you started with the spell checker. It is fairly similar to the code in main.c. You can build the program with make spellChecker. FYI: The spellchecker program flow should as following - 1. The user types in a word 2. Potential matches are outputted Like "Did you mean...?" etc 3. Continue to prompt user for word until they type quit The best way to implement a dictionary that's used for a spellchecker would probably be to design it with that purpose in mind from the beginning, i.e. associating a similarity for each word to some base word (maybe "abcdefghijklmnopqrstuvwyz") and then incorporating that into the hash function. There are better ways ( https://en.wikipedia.org/wiki/Levenshtein_distance) to establish similarity than computing the cosine of the angle between two vectors (strings) to create a list of candidates and further winnowed that list according to substring comparisons. So, I would say calculating the Levenshtein distance between the misspelled word and all strings in the dictionary, create 5/6 best candidates and print them as suggestion.
spellchecker.c
#include "hashMap.h"
#include
#include
#include
#include
#include
/**
* 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] = '\0';
return word;
}
/**
* Loads the contents of the file into the hash map.
* @param file
* @param map
*/
void loadDictionary(FILE* file, HashMap* map)
{
// FIXME: implement
}
/**
* 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");
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)
{
printf("Enter a word or \"quit\" to quit: ");
scanf("%s", inputBuffer);
// Implement the spell checker code here..
if (strcmp(inputBuffer, "quit") == 0)
{
quit = 1;
}
}
hashMapDelete(map);
return 0;
}
hashMap.h
#ifndef HASH_MAP_H
#define HASH_MAP_H
#define HASH_FUNCTION hashFunction1
#define MAX_TABLE_LOAD .75
typedef struct HashMap HashMap;
typedef struct HashLink HashLink;
struct HashLink
{
char* key;
int value;
HashLink* next;
};
struct HashMap
{
HashLink** table;
// Number of links in the table.
int size;
// Number of buckets in the table.
int capacity;
};
HashMap* hashMapNew(int capacity);
void hashMapDelete(HashMap* map);
int* hashMapGet(HashMap* map, const char* key);
void hashMapPut(HashMap* map, const char* key, int value);
void hashMapRemove(HashMap* map, const char* key);
int hashMapContainsKey(HashMap* map, const char* key);
int hashMapSize(HashMap* map);
int hashMapCapacity(HashMap* map);
int hashMapEmptyBuckets(HashMap* map);
float hashMapTableLoad(HashMap* map);
void hashMapPrint(HashMap* map);
#endif
hashMap.c - for reference
/*
* CS 261 Data Structures
* Assignment 6
* Name: Tim Kelly
* Date: 8/8/17
*/
#include "hashMap.h"
#include
#include
#include
#include
int hashFunction1(const char* key)
{
int r = 0;
for (int i = 0; key[i] != '\0'; i++)
{
r += key[i];
}
return r;
}
int hashFunction2(const char* key)
{
int r = 0;
for (int i = 0; key[i] != '\0'; i++)
{
r += (i + 1) * key[i];
}
return r;
}
/**
* Creates a new hash table link with a copy of the key string.
* @param key Key string to copy in the link.
* @param value Value to set in the link.
* @param next Pointer to set as the link's next.
* @return Hash table link allocated on the heap.
*/
HashLink* hashLinkNew(const char* key, int value, HashLink* next)
{
HashLink* link = malloc(sizeof(HashLink));
link->key = malloc(sizeof(char) * (strlen(key) + 1));
strcpy(link->key, key);
link->value = value;
link->next = next;
return link;
}
/**
* Free the allocated memory for a hash table link created with hashLinkNew.
* @param link
*/
static void hashLinkDelete(HashLink* link)
{
free(link->key);
free(link);
}
/**
* Initializes a hash table map, allocating memory for a link pointer table with
* the given number of buckets.
* @param map
* @param capacity The number of table buckets.
*/
void hashMapInit(HashMap* map, int capacity)
{
map->capacity = capacity;
map->size = 0;
map->table = malloc(sizeof(HashLink*) * capacity);
for (int i = 0; i < capacity; i++)
{
map->table[i] = NULL;
}
}
/**
* Removes all links in the map and frees all allocated memory. You can use
* hashLinkDelete to free the links.
* @param map
*/
void hashMapCleanUp(HashMap* map)
{
// FIXME: implement
struct HashLink *link;
struct HashLink *next;
for (int i = 0; i < map->capacity; i++) {
link = map->table[i];
//iterate through the buckets
if (link != 0) {
do {
next = link->next;
hashLinkDelete(link);
link = next;
} while (next != 0);
}
}
free(map->table);
map->table = 0;
}
/**
* Creates a hash table map, allocating memory for a link pointer table with
* the given number of buckets.
* @param capacity The number of buckets.
* @return The allocated map.
*/
HashMap* hashMapNew(int capacity)
{
HashMap* map = malloc(sizeof(HashMap));
hashMapInit(map, capacity);
return map;
}
/**
* Removes all links in the map and frees all allocated memory, including the
* map itself.
* @param map
*/
void hashMapDelete(HashMap* map)
{
hashMapCleanUp(map);
free(map);
}
/**
* Returns a pointer to the value of the link with the given key. Returns NULL
* if no link with that key is in the table.
*
* Use HASH_FUNCTION(key) and the map's capacity to find the index of the
* correct linked list bucket. Also make sure to search the entire list.
*
* @param map
* @param key
* @return Link value or NULL if no matching link.
*/
int* hashMapGet(HashMap* map, const char* key)
{
// FIXME: implement
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->capacity;
struct HashLink *link = map->table[hashIndex];
while (link != 0) {
if (strcmp(link->key, key) == 0)
return &(link->value);
else
link = link->next;
}
return 0;
}
/**
* Resizes the hash table to have a number of buckets equal to the given
* capacity. After allocating the new table, all of the links need to be
* rehashed into it because the capacity has changed.
*
* Remember to free the old table and any old links if you use hashMapPut to
* rehash them.
*
* @param map
* @param capacity The new number of buckets.
*/
void resizeTable(HashMap* map, int capacity)
{
// FIXME: implement
struct HashMap *newMap = hashMapNew(capacity);
struct HashLink *link;
for (int i = 0; i < map->capacity; i++) {
link = map->table[i];
//add links
while (link != 0) {
hashMapPut(newMap, link->key, link->value);
link = link->next;
}
}
//Swap the capacities of the tables
hashMapCleanUp(map);
map->table = newMap->table;
map->size = newMap->size;
map->capacity = newMap->capacity;
free(newMap); //free temporary map
}
/**
* Updates the given key-value pair in the hash table. If a link with the given
* key already exists, this will just update the value. Otherwise, it will
* create a new link with the given key and value and add it to the table
* bucket's linked list. You can use hashLinkNew to create the link.
*
* Use HASH_FUNCTION(key) and the map's capacity to find the index of the
* correct linked list bucket. Also make sure to search the entire list.
*
* @param map
* @param key
* @param value
*/
void hashMapPut(HashMap* map, const char* key, int value)
{
// FIXME: implement
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->capacity;
struct HashLink *link = map->table[hashIndex];
while (link != 0) {
if (strcmp(link->key, key) == 0) {
link->value = value; //set new value
return;
}
link = link->next; //move to next
}
//No value found to match, add to front
link = hashLinkNew(key, value, map->table[hashIndex]);
map->table[hashIndex] = link;
map->size++;
if (hashMapTableLoad(map) > MAX_TABLE_LOAD) {
resizeTable(map, 2 * hashMapCapacity(map)); //resize if load factor's higher than max
}
}
/**
* Removes and frees the link with the given key from the table. If no such link
* exists, this does nothing. Remember to search the entire linked list at the
* bucket. You can use hashLinkDelete to free the link.
* @param map
* @param key
*/
void hashMapRemove(HashMap* map, const char* key)
{
// FIXME: implement
assert(map != 0);
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->table[hashIndex]->next;
struct HashLink *link = map->table[hashIndex];
struct HashLink *next = map->table[hashIndex]->next;
if (link == 0) {
return;
}
if (strcmp(link->key, key) == 0) {
hashLinkDelete(link);
map->table[hashIndex] = next;
map->size--;
return;
}
while (next != 0) {
if (strcmp(next->key, key) == 0) {
link->next = next->next;
hashLinkDelete(next);
map->size--;
return;
}
else {
link = link->next;
next = next->next;
}
}
}
/**
* Returns 1 if a link with the given key is in the table and 0 otherwise.
*
* Use HASH_FUNCTION(key) and the map's capacity to find the index of the
* correct linked list bucket. Also make sure to search the entire list.
*
* @param map
* @param key
* @return 1 if the key is found, 0 otherwise.
*/
int hashMapContainsKey(HashMap* map, const char* key)
{
// FIXME: implement
int hashIndex = HASH_FUNCTION(key) % map->capacity;
if (hashIndex < 0)
hashIndex = hashIndex + map->capacity;
struct HashLink *link = map->table[hashIndex];
while (link != 0) {
if (strcmp(link->key, key) == 0) {
return 1;
}
else
link = link->next;
}
return 0;
}
/**
* Returns the number of links in the table.
* @param map
* @return Number of links in the table.
*/
int hashMapSize(HashMap* map)
{
// FIXME: implement
return map->size; //return num of links
}
/**
* Returns the number of buckets in the table.
* @param map
* @return Number of buckets in the table.
*/
int hashMapCapacity(HashMap* map)
{
// FIXME: implement
return map->capacity; //return num of buckets
}
/**
* Returns the number of table buckets without any links.
* @param map
* @return Number of empty buckets.
*/
int hashMapEmptyBuckets(HashMap* map)
{
// FIXME: implement
int count = 0;
for (int i = 0; i < map->capacity; i++) {
if (map->table[i] == 0) { //if bucket is empty, increment count
count++;
}
}
return count;
}
/**
* Returns the ratio of (number of links) / (number of buckets) in the table.
* Remember that the buckets are linked lists, so this ratio tells you nothing
* about the number of empty buckets. Remember also that the load is a floating
* point number, so don't do integer division.
* @param map
* @return Table load.
*/
float hashMapTableLoad(HashMap* map)
{
// FIXME: implement
return (double)map->size / (map->capacity); //calculate table load = num of links / num of buckets
}
/**
* Prints all the links in each of the buckets in the table.
* @param map
*/
void hashMapPrint(HashMap* map)
{
for (int i = 0; i < map->capacity; i++)
{
HashLink* link = map->table[i];
if (link != NULL)
{
printf(" Bucket %i ->", i);
while (link != NULL)
{
printf(" (%s, %d) ->", link->key, link->value);
link = link->next;
}
}
}
printf(" ");
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help