I tried implementing a radix tree using C language in order to get the auto complete suggestions of a dictionary. What are the improvements that I can do here? Also, is there any better way of doing this?
The text file I used has the following format
a
at
along
bat
cat
Here's my implementation.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include <ctype.h>
// define a maximum length for the string.
#define MAX_LEN (200)
// define the alphabet size for english.
#define ALPHABET_SIZE (26)
// linked String structure
typedef struct LinkedString {
// linked string node contains a char.
char character;
struct LinkedString *next;
} LinkedString;
// TrieNode structure
typedef struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
// linked string to place the str inside the trie node.
LinkedString *LinkedString;
// boolean to check for leaf_nodes
bool is_leaf;
} TrieNode;
/* function signatures */
// create a trie Node.
TrieNode *createNode();
// appends to the string[initial: end] and return a linked string.
LinkedString *appendLinkedString(char *str, int inital, int end);
// break the linked string and create a node with the breaked string and returns intial.
TrieNode *breakLinkedString(TrieNode *previousNode, TrieNode *node, LinkedString *breakPoint);
// insert a str to the trie node.
void insert(TrieNode *root, char *str);
// returns the pointer if found the str else returns NULL
TrieNode *searchNodes(TrieNode *root, char *str);
// convert a string in to charactors
int str_to_char(LinkedString *begin, char *str, int initial);
// print suggestions for the prefix.
void printSuggetions(TrieNode *suggestedNode, char str[], int Size);
// create a linked string with a given char.
LinkedString *createString(char Char);
// node count to get the memory used.
int node_count = 0;
// link string count to get the memory.
int link_string_node_count = 0;
int main(){
char input[MAX_LEN];
char str[MAX_LEN];
char lowerCase[MAX_LEN];
// read the file
TrieNode *root = createNode();
// file name of the wordlist
char *fileName = "wordlist70000.txt";
// create a file pointer to read the file
FILE *fptr = fopen(fileName, "r");
int j = 0;
// elapsed time ro insert all entries ti the trie
clock_t start_time = clock();
// read the file and insert words into the tire
while (fgets(str, MAX_LEN - 1, fptr))
{
j = 0;
// check whether the character is in alphabet
for (int i = 0; i < MAX_LEN; ++i){
if (((str[i] > 64) && (str[i] < 91)) || (str[i] > 96) && (str[i] < 123)) {
// converts the characters into lowercase
lowerCase[j] = tolower(str[i]);
j++;
}
if (str[i] == '\n'|| str[i] == '\0') {
break;
}
}
// configure the terminating character
lowerCase[j] = 0;
// insert into the trie
insert(root, lowerCase);
}
clock_t end = clock();
// end the timer
double elapsedtime = (double)(end - start_time) / CLOCKS_PER_SEC;
printf("\nElapsed time for insert: %f s\n", elapsedtime);
while (true){
// prompt the user to inputs
printf("Enter the prefix['0' for quit!] :\n");
// get the input
scanf("%s", input);
// copy the input to the str
strcpy(str, input);
//if the exit condition is met
if (strcmp(str, "0") == 0){
printf("Quit! \n");
break;
}
j = 0;
// check whether the character is in alphabet
for (int i = 0; i < MAX_LEN; ++i){
if (((str[i] > 64) && (str[i] < 91)) || (str[i] > 96) && (str[i] < 123)) {
// converts the characters into lowercase
lowerCase[j] = tolower(str[i]);
j++;
}
if (str[i] == '\n' || str[i] == '\0') {
break;
}
}
// configure the terminating character
lowerCase[j] = 0;
strcpy(str, lowerCase);
// star the time to track the elapsed time
clock_t start_time = clock();
// check for the prefix
TrieNode *suggestedNode = searchNodes(root, str);
if (!suggestedNode) {
// if prefix not found
printf("Prefix Not Found!\n\n");
continue;
}
printf("\n ***************** SUGGETIONS ****************** \n");
printSuggetions(suggestedNode, str, strlen(str));
// end the timer
clock_t end = clock();
// calculate the elapse time
double elapsedtime = (double)(end - start_time) / CLOCKS_PER_SEC;
// print the elapsed time and memory used.
printf("\nElapsed time : %f s\n", elapsedtime);
int count1 = (int)sizeof(*(root)) * node_count;
int count2 = (int)sizeof(LinkedString) * link_string_node_count;
printf("Memory used : %d Bytes\n\n", count1 + count2);
}
return 0;
}
TrieNode *createNode() {
node_count++;
// allocate space for new trie node.
TrieNode *newtrieNode = (TrieNode *)malloc(sizeof(TrieNode));
// initialize the linked string with NULL
newtrieNode->LinkedString = NULL;
// make it as not a leaf
newtrieNode->is_leaf = false;
int i;
for (i = 0; i < ALPHABET_SIZE; ++i) {
// make all the chiledrens null.
newtrieNode->children[i] = NULL;
}
return newtrieNode;
}
LinkedString *createString(char Char) {
link_string_node_count++;
// allocate space for a new string dynamically.
LinkedString *newString = (LinkedString *)malloc(sizeof(LinkedString));
// put the char into its character
newString->character = Char;
// make the next pointer null.
newString->next = NULL;
// return the new string.
return newString;
}
LinkedString *appendLinkedString(char *str, int inital, int end) {
int i;
// create a pointers to linked strings.
LinkedString *current = createString(str[inital]);
LinkedString *newString = NULL;
LinkedString *string = current;
// go from initial position to end position
for (i = inital + 1; i < end; ++i) {
// crate a new string with char index i or str
newString = createString(str[i]);
// make the next pointer point to new string.
current->next = newString;
// go through the string
current = current->next;
}
// make the last pointer at the end.
current = NULL;
return string;
}
TrieNode *breakLinkedString(TrieNode *previousNode, TrieNode *node, LinkedString *breakPoint) {
// create a new trie node pointer.
TrieNode *newNode = createNode();
// create a new string beginning next to the break point.
LinkedString *newString = breakPoint->next;
breakPoint->next = NULL;
// convert char to index
int index1 = (newString->character) — 'a';
newNode->LinkedString = node->LinkedString;
node->LinkedString = newString;
newNode->children[index1] = node;
int index2 = (newNode->LinkedString->character) - 'a';
// pointer the new node to the relevent index of the parent node.
previousNode->children[index2] = newNode;
// return the newnode.
return newNode;
}
void insert(TrieNode *root, char *str) {
// get the length of the str
int lastLetterIndex = strlen(str);
int i = 0, charIndex;
// create trie nodes and likedlist pointers to track
// previous current and next pointer nodes.
TrieNode *currentNode = root, *previousNode = NULL;
TrieNode *newNode = NULL;
LinkedString *currentLetter, *previousLetter = NULL;
currentLetter = currentNode -> LinkedString;
// go till the last leter of the string.
while (i < lastLetterIndex) {
charIndex = (str[i]) - 'a';
// if current letter is null
if (currentLetter == NULL) {
// if the trie is empty.
if (currentNode->children[charIndex] == NULL) {
// create a new node.
newNode = createNode();
// append the string[i:lastLetterIndex] point to the new nodes linked
newNode->LinkedString = appendLinkedString(str, i, lastLetterIndex);
newNode->is_leaf = true;
currentNode->children[charIndex] = newNode;
break;
} else { // if it is the first node.
// make the previous node pointing to the current node.
previousNode = currentNode;
currentNode = currentNode->children[charIndex];
previousLetter = currentNode->LinkedString;
currentLetter = currentNode->LinkedString->next;
}
} else {
if (currentLetter->character != str[i]) {
// make the current node pointing to the breakedLinkedString.
currentNode = breakLinkedString(previousNode, currentNode, previousLetter);
// create a new node.
newNode = createNode();
// append the link string to the newNodes LinkedString.
newNode->LinkedString = appendLinkedString(str, i, lastLetterIndex);
// make new node a leaf node
newNode->is_leaf = true;
// put newNode as a child of a current node.
currentNode->children[charIndex] = newNode;
break;
} else {
previousLetter = currentLetter;
currentLetter = currentLetter->next;
}
}
i++;
}
}
TrieNode *searchNodes(TrieNode *root, char *str) {
// get the lastIndex of the str
int lastIndex = strlen(str);
int i = 0, charIndex;
TrieNode *currentNode = root;
LinkedString *currentLetter = currentNode->LinkedString;
while (i < lastIndex) {
// get the index from the char Index.
charIndex = str[i] - 'a';
// if current letter is null.
if (currentLetter == NULL) {
// point the relevent index to the currentNode.
currentNode = currentNode->children[charIndex];
// if the word is not found. Then the current node
// and the currentLetter is NULL.
if (!currentNode) return NULL;
// make the currentLeter pointing to the linked strings next letter.
currentLetter = currentNode->LinkedString->next;
} else {
// go to the next letter.
currentLetter = currentLetter->next;
}
i++;
}
// go untilll the current letter is found null
while (currentLetter != NULL) {
// go till the end of the character.
str[lastIndex] = currentLetter->character;
currentLetter = currentLetter->next;
lastIndex++;
}
// make the last index pointing to the terminating character
str[lastIndex] = '\0';
return currentNode;
}
int str_to_char(LinkedString *begin, char *str, int initial) {
int newSize = initial;
LinkedString *currentLetter = begin;
// go while current lettter is not null
while (currentLetter != NULL) {
// put the char by char in str
str[newSize] = currentLetter->character;
// goto the next letter
currentLetter = currentLetter->next;
newSize++;
}
// set the terminating character.
str[newSize] = '\0';
return newSize - 1;
}
void printSuggetions(TrieNode *suggestedNode, char str[], int Size) {
// create a poiter to the suggested node
TrieNode *currentNode = suggestedNode;
int i, j, newSize;
if (currentNode->is_leaf){
// go till the word_size
for (j = 0; j < Size; ++j){
// print the uppercased char
printf("%c", toupper(str[j]));
}
// print the endline
printf("\n");
}
// go through each children node.
for (i = 0; i < ALPHABET_SIZE; ++i) {
// if each child is not null
if (currentNode->children[i] != NULL) {
// break down the string and get the characters
newSize = str_to_char(currentNode->children[i]->LinkedString, str, Size);
// print the suggestion.
printSuggetions(currentNode->children[i], str, newSize + 1);
}
}
}
