0

So far, all other methods except check have already been implemented properly in my code. The problem with check is that it only returns true a lot fewer times than expected, which means that most words that go through it are deemed as misspelled, even though they are not. I think that the issue somehow lies in line 120:

return (trav != NULL && trav->is_word);

This line simply checks if the traversal pointer has reached a leaf node in the trie. Yet it always returns 0 for some reason. The loop has already finished running, so trav should be at a leaf node as expected, I do not know where else in the code can an issue pop up.

Some other minor issue is that the dictionary count does not work as expected. It returns the correct amount for the small dictionary, yet is wrong on the large one.

My functionality for trie is divided into header and source:

trie.h

// Declares tries and related methods

#ifndef TRIE_H
#define TRIE_H

#include <stdbool.h>

// Total of all possible characters in a word
#define ALPHABET_SIZE 27

// Converts key current character into index
// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

// Type definition for a trie node
typedef struct node
{
    bool is_word;
    struct node *children[ALPHABET_SIZE];
}
node;

// Type definition for a trie
typedef struct trie
{
    node *root;
    unsigned int count;
}
trie;

// Function prototypes
node *getNode(void);
void initialize(trie *pTrie);
void insert(trie *pTrie, const char *key);
bool search(trie *pTrie, const char *key);
void free_all_core(node *pNode);
bool free_all(trie *pTrie);

#endif

trie.c

// Implements tries and related methods

// Adapted from Venki's code available here:
// https://www.geeksforgeeks.org/trie-delete/

#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "trie.h"

// Returns new trie node (Initialized to NULL)
node *getNode(void)
{
    // Declare pointer for a node
    node *pNode = NULL;

    // Allocate space on the heap for a node
    // and clear it of garbage values
    pNode = (node *)calloc(1, sizeof(node));

    // Check if the node exists and declare it as a stem
    if (pNode)
    {
        pNode->is_word = false;
    }

    return pNode;
}

// Initializes an entire trie
void initialize(trie *pTrie)
{
    pTrie->root = getNode();
    pTrie->count = 0;
}

// If not present, inserts key into trie
// If the key is prefix of trie node, mark as leaf node
void insert(trie *pTrie, const char *key)
{
    // Iterate the word count in the trie by 1
    pTrie->count++;

    // Traversal pointer
    node *trav = pTrie->root;

    // Iterate through every level in the trie / characters in the key
    for (int level = 0; level < strlen(key); level++)
    {
        int keyChar = key[level];

        // Convert current character to alphabetical index
        // assuming that every word in the dictionary is already in lowercase
        if (isalpha(keyChar))
        {
           keyChar = CHAR_TO_INDEX(keyChar);
        }

        // Special case for apostrophe
        else if (keyChar == '\'')
        {
            keyChar = ALPHABET_SIZE - 1;
        }

        // If the character is already allocated in the current level array
        if (trav->children[keyChar])
        {
            // Skip current node
            trav = trav->children[keyChar];
        }

        else
        {
            // Add new node
            trav->children[keyChar] = getNode();
            trav = trav->children[keyChar];
        }
    }

    // Mark last node as leaf
    trav->is_word = true;
}

// Returns true if key presents in trie, else false
bool search(trie *pTrie, const char *key)
{
    // Traversal pointer
    node *trav = pTrie->root;

    // Iterate through every level in the trie / characters in the key
    for (int level = 0; level < strlen(key); level++)
    {
        int keyChar = key[level];

        // Convert current character to alphabetical index
        if (isalpha(keyChar))
        {
           keyChar = CHAR_TO_INDEX(tolower(keyChar));
        }

        // Special case for apostrophe
        else if (keyChar == '\'')
        {
            keyChar = 26;
        }

        // Return 0 if the key sequence is not found in the trie
        if (!trav->children[keyChar])
        {
            return false;
        }

        // Traverse towards the next level in the trie following the current key character
        trav = trav->children[keyChar];
    }

    // Return other value if leaf node is found
    return (trav != NULL && trav->is_word);
}

// Recursive helper function to free all elements in a node
void free_all_core(node *pNode)
{
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        if (pNode->children[i])
        {
            free_all_core(pNode->children[i]);
            pNode->children[i] = NULL;
        }
    }

    free(pNode);
}

// Deletes an entire trie
bool free_all(trie *pTrie)
{
    // Check if the pTrie exists and has a root node
    if (pTrie)
    {
        if (pTrie->root)
        {
            // Free all nodes
            free_all_core(pTrie->root);
        }

        return true;
    }

    return false;
}

Here's my code for the dictionary just in case:

dictionary.h

// Declares a dictionary's functionality

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>
#include <stdio.h>

// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

// Prototypes
bool check(const char *word);
bool load(const char *dictionary);
unsigned int size(void);
bool unload(void);

#endif // DICTIONARY_H

dictionary.c

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdio.h>

#include "dictionary.h"
#include "trie.h"

// Initialize the trie dictionary
trie trie_d;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    if (!search(&trie_d, word))
    {
        return true;
    }

    return false;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Open the dictionary and see if it is empty
    FILE *file = fopen(dictionary, "r");

    if (file == NULL)
    {
        return false;
    }

    // Create and check if the trie root node was created
    initialize(&trie_d);
    if (trie_d.root == NULL)
    {
        return false;
    }

    // Array to hold the current word being read
    char word[LENGTH];

    // Iterate through every word in the dictionary
    // and insert it into the trie
    while(fgets(word, sizeof(word), file))
    {
        insert(&trie_d, word);
    }

    // Close the dictionary after reading
    fclose(file);

    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return trie_d.count;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    if (free_all(&trie_d))
    {
        return true;
    }

    return false;
}
  • Check a little lower, when I encountered an uppercase letter in the search function, I used tolower() first before using CHAR_TO_INDEX. So it still works as expected. For the apostrophe, I created a special condition to properly mark it in the trie. – user9474943 May 9 '18 at 8:29
  • Yeah, I'm stupid, did not realize you had tolower in the check version. And dictionary already comes in all-lowercase. – Blauelf May 9 '18 at 8:33
0

Got it! Seems that I was wrong in the insert function in trie, and the program seems to have gone a level too deep before marking it as a word. Sorry for the slight inconvenience I may have caused!

| improve this answer | |
  • I don't see how it goes too deep there. – Blauelf May 9 '18 at 8:37
  • Neither do I actually, I only really found out about it while experimenting with debug50. – user9474943 May 9 '18 at 9:28
  • The code you showed goes strlen(key) steps into the trie. Which is exactly right. "cat" would walk from root node representing empty string "" to "c", to "ca", to "cat", and set is_word for the "cat" node. – Blauelf May 9 '18 at 11:33
0
// Returns true if word is in dictionary else false
bool check(const char *word)
{
    if (!search(&trie_d, word))
    {
        return true;
    }

    return false;
}

is same as

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    return !search(&trie_d, word);
}

and I think you meant

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    return search(&trie_d, word);
}

without the negation.

| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .