Implement trie based on search history

Question

I'm making a webpage for doctors and I need to retrieve medicine for doctors from a database. The doctor can type the complete/partial name of a medicine and I need to predict what he can type. Simple?

Now, I also need the search space to modify itself based on past actions. For eg if many doctors type flaxi instead of ofloxacin(bad eg), my data structure should be modified to reflect ofloxacin when flaxi is typed. I'm thinking of using a trie, where each node contains a list of the medicine to be displayed. Can someone help me going about how to implement this?

Thanks!!!

Answer 1

Here's a small and a very simple C code for trie... Hope this helps you to understand the concepts...

Here's how you define a node...

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* Prefix Trie */

typedef struct TrieNode {
    char wordEnd;   // 1 if a word ends at this node, 0 o.w.
    struct TrieNode *index[128];
} TrieNode;

Here's how you create a new node in memory.

TrieNode* makeTrieNode() {
    TrieNode* node = (TrieNode*) malloc (sizeof(TrieNode));
    node->wordEnd = 0;
    return node;
}

Here's how you recursively insert a new node in an existing trie.

TrieNode* insert(TrieNode* root, char* word) {
    TrieNode* child;

    if (*word == 0) {
        root->wordEnd = 1;
        return root;
    }

    child = root->index[*word];
    if (child == NULL) {
        child = makeTrieNode();
        root->index[*word] = child;
    }

    return insert(child, word+1);
}

Here's how you recursively search a key word.

// returns 1 if word found 0 o.w.
int search(TrieNode* root, char* word) {
    if (*word == 0) {
        return root->wordEnd;
    }
    if (root->index[*word] == NULL) {
        // unsuccessful search
        return 0;
    }
    search(root->index[*word], word+1);
}

Here's small unit test.

int main() {
    TrieNode *root = makeTrieNode();
    insert(root, "abacus");
    insert(root, "cat");
    insert(root, "can");
    insert(root, "continue");
    insert(root, "continuation");

    printf("%d %d %d %d %d\n", search(root, "abacus"), search(root, "cat"),
    search(root, "cot"), search(root, "continue"),
    search(root, "continuation"));
    return 0;
}