Create a Word Auto-Completer in C using the Trie Data Structure

Pages: 1 2

void update_top_leafs(struct node *h, char *s)
{
 int i, j, z, min, num_leafs, empty, cont=0;
 struct topleaf sorted_topleafs[N];
 struct leaf *l = h−>fyllo;
 struct node *p = h;
 
 l−>frequency++;
 
 for(i=0; i<strlen(s); i++)
 { 
 z=0;
 cont =0;
 num_leafs = p−>num_leafs;
 
 for(j=0; j<N; j++)//if the array is full but one of the words is the one we test just increase frequency to be updated
 {
 if(strcmp(p−>topleafs[j].word, s) == 0)
 {
 p−>topleafs[j].frequency++;
 z=1;
 }
 }
 
 
 if(z != 1)
 {
 for(j=0; j<N; j++)//if array of top frequent words has space insert the word
 {
 if(p−>topleafs[j].frequency == −1)
 {
 empty = j;
 cont = 1;
 break;
 }
 }
 }
 
 if(cont==1)
 { 
 p−>topleafs[empty].frequency = l−>frequency;
 strcpy(p−>topleafs[empty].word, s);
 }
 
 if(cont == 0 && z!=1)
 {
 if(z!=1)//if one of those words in the array has lower frequency than the one we test change them
 { 
 min = 0;
 for(j=1; j<N; j++)//find the word with the lowest frequency of the array
 { 
 //printf("%d %s min −> %d %s\n", p−>topleafs[j].frequency,p−>topleafs[j].word, p−>topleafs[min].frequency, p−>topleafs[min].word);
 if(p−>topleafs[j].frequency < p−>topleafs[min].frequency)
 min = j;
 }
 
 if(l−>frequency >= p−>topleafs[min].frequency )
 {//if the word we test has greater or equal frequency change them 
 p−>topleafs[min].frequency = l−>frequency;
 strcpy(p−>topleafs[min].word, s);
 }
 else//no need to climb to parent
 break;
 }
 }
 p = p−>parent;
 }
}

The last function you need is the search one that gets two basic parameters. The word that you want to search for auto-completion and the root pointer of the trie. Similarly with the strlen(word) loop you will navigate through the trie and if in the last node/letter there is a valid leaf pointer then we have a match and then the program prints to the user the most frequent words under this inner node. If you want to see the implementation of search function I suggest you to take a look at the compiled source code below:

Basic Rules to run effectively the code:

• You type words and sentences using spaces, dots, letters (lowercase and uppercase) normally

• If you want to auto-complete you press the special character TAB (If you type ENTER the whole sentence will be deleted and the program waits from the user to start from the beginning)

• Then the program prints the N top words for auto-complete and by pressing the number of your choice + ENTER the word gets auto-completed ( Important: if you type illegal characters such as letters the program cancels the procedure and returns in the last character you typed before the TAB otherwise if you press a wrong number e.x. There are three available choices and you press 5 then the program waits from the user to enter a valid number.)

• If you want to change the number of the suggested words that are printed go to the trie.h file and change the N constant.

Click the image below to see a demonstration of the implemented auto-completer:

Click here to download the complete implementation of the auto-completer!

Enjoy and have fun!

References:

http://en.wikipedia.org/wiki/Trie

Giannis Kanellopoulos

Biography to be completed

More Posts