Skip to main content

Tries Data Structure

TRIES (Data Structure)

·        The trie (pronounced ``try'' and derived from the word retrieval) also called prefix tree (as they can be searched by prefixes), for a set of strings S is an ordered tree such that:
o   Each node but the root is labeled with a character
o   The children of a node are alphabetically ordered
·        Each node has R children, one for each possible character.
·         All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.
·        Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

Example:
car, card, carry, cart, cat, cel, celery, close, closely, closet, clue


Applications of Tries

·         Spell Checking
·         Prefix Match
·         Longest Prefix Match
·         T9 typing
·         Compression (Ziv-Lembel encoding)

TRIES CODE DEVELOPED USING VS 2010
// This Code Read Text File containing words to create a Trie.
// User may search for any string and this code will reply, input word is valid or invalid by searching in trie.

#include
#include
#include
#include

using namespace std;

//Struct Node Contain a-z Nodes links.
typedef struct TriesNode
{
          char ch;
          bool treminate;
          struct TriesNode *a;
          struct TriesNode *b;
          struct TriesNode *c;
          struct TriesNode *d;
          struct TriesNode *e;
          struct TriesNode *f;
          struct TriesNode *g;
          struct TriesNode *h;
          struct TriesNode *i;
          struct TriesNode *j;
          struct TriesNode *k;
          struct TriesNode *l;
          struct TriesNode *m;
          struct TriesNode *n;
          struct TriesNode *o;
          struct TriesNode *p;
          struct TriesNode *q;
          struct TriesNode *r;
          struct TriesNode *s;
          struct TriesNode *t;
          struct TriesNode *u;
          struct TriesNode *v;
          struct TriesNode *w;
          struct TriesNode *x;
          struct TriesNode *y;
          struct TriesNode *z;

}Node;

//Create a Root Node of Trie.
void CreateTries(Node **root)
{
          *root=NULL;      
}

//Create a New Node of Given Char, Initially All nodes are NULL
Node* CreateNewNode(char c)
{
                   Node *t=(Node*)malloc(sizeof(Node));
                   t->ch=c;
                   t->treminate=false;

                   t->a=NULL;
                   t->b=NULL;
                   t->c=NULL;
                   t->d=NULL;
                   t->e=NULL;
                   t->f=NULL;
                   t->g=NULL;
                   t->h=NULL;
                   t->i=NULL;
                   t->j=NULL;
                   t->k=NULL;
                   t->l=NULL;
                   t->m=NULL;
                   t->n=NULL;
                   t->o=NULL;
                   t->p=NULL;
                   t->q=NULL;
                   t->r=NULL;
                   t->s=NULL;
                   t->t=NULL;
                   t->u=NULL;
                   t->v=NULL;
                   t->w=NULL;
                   t->x=NULL;
                   t->y=NULL;
                   t->z=NULL;
                  
                   return t;
}




//Insert That node in Trie
void Insert_IN_Tries(string str,Node **root)
{
          if(*root==NULL)
          {
                   //If Root node is Blank or Null,use Dummy Char for                                        //Root
                   Node *t1=CreateNewNode('+');
                   t1->treminate=false;
                   *root=t1;
                   return;
          }

//Otherwise approprate place for new char in trie and insert at that position 
          Node *temp=*root;
          int len=str.length();
          for(int i=0;i
          {
                             if(str[i]=='a'|| str[i]=='A')
                             {
                                      if(temp->a==NULL)
                                      {
                                                Node *t=CreateNewNode('a');
                                                temp->a=t;
                                                temp=temp->a;
                                      }
                                      else
                                      {
                                                temp=temp->a;
                                      }
                             }
                             else if(str[i]=='b' || str[i]=='B')
                             {
                                      if(temp->b==NULL)
                                      {
                                      Node *t=CreateNewNode('b');
                                      temp->b=t;
                                      temp=temp->b;
                                      }
                                      else
                                      {
                                                temp=temp->b;
                                      }
                             }
                             else if(str[i]=='c' || str[i]=='C')
                             {
                                      if(temp->c==NULL)
                                      {
                                                Node *t=CreateNewNode('c');
                                                temp->c=t;
                                                temp=temp->c;
                                      }
                                      else
                                      {
                                                temp=temp->c;
                                      }
                             }
                             else if(str[i]=='d' || str[i]=='D')
                             {
                                      if(temp->d==NULL)
                                      {
                                      Node *t=CreateNewNode('d');
                                      temp->d=t;
                                      temp=temp->d;
                                      }
                                      else
                                      {
                                                temp=temp->d;
                                      }
                             }
                             else if(str[i]=='e' || str[i]=='E')
                             {
                                      if(temp->e==NULL)
                                      {
                                      Node *t=CreateNewNode('e');
                                      temp->e=t;
                                      temp=temp->e;
                                      }
                                      else
                                      {
                                                temp=temp->e;
                                      }
                             }
                             else if(str[i]=='f' || str[i]=='F')
                             {
                                      if(temp->f==NULL)
                                      {
                                      Node *t=CreateNewNode('f');
                                      temp->f=t;
                                      temp=temp->f;
                                      }
                                      else
                                      {
                                                temp=temp->f;
                                      }
                             }
                             else if(str[i]=='g' || str[i]=='G')
                             {
                                      if(temp->g==NULL)
                                      {
                                      Node *t=CreateNewNode('g');
                                      temp->g=t;
                                      temp=temp->g;
                                      }
                                      else
                                      {
                                                temp=temp->g;
                                      }
                             }
                             else if(str[i]=='h' || str[i]=='H')
                             {
                                      if(temp->h==NULL)
                                      {
                                      Node *t=CreateNewNode('h');
                                      temp->h=t;
                                      temp=temp->h;
                                      }
                                      else
                                      {
                                                temp=temp->h;
                                      }
                             }
                             else if(str[i]=='i' || str[i]=='I')
                             {
                                      if(temp->i==NULL)
                                      {
                                      Node *t=CreateNewNode('i');
                                      temp->i=t;
                                      temp=temp->i;
                                      }
                                      else
                                      {
                                                temp=temp->i;
                                      }
                             }
                             else if(str[i]=='j' || str[i]=='J')
                             {
                                      if(temp->j==NULL)
                                      {
                                      Node *t=CreateNewNode('j');
                                      temp->j=t;
                                      temp=temp->j;
                                      }
                                      else
                                      {
                                                temp=temp->j;
                                      }
                             }
                             else if(str[i]=='k' || str[i]=='K')
                             {
                                      if(temp->k==NULL)
                                      {
                                      Node *t=CreateNewNode('k');
                                      temp->k=t;
                                      temp=temp->k;
                                      }
                                      else
                                      {
                                                temp=temp->k;
                                      }
                             }
                             else if(str[i]=='l' || str[i]=='L')
                             {
                                      if(temp->l==NULL)
                                      {
                                      Node *t=CreateNewNode('l');
                                      temp->l=t;
                                      temp=temp->l;
                                      }
                                      else
                                      {
                                                temp=temp->l;
                                      }
                             }
                             else if(str[i]=='m' || str[i]=='M')
                             {
                                      if(temp->m==NULL)
                                      {
                                      Node *t=CreateNewNode('m');
                                      temp->m=t;
                                      temp=temp->m;
                                      }
                                      else
                                      {
                                                temp=temp->m;
                                      }
                             }
                             else if(str[i]=='n' || str[i]=='N')
                             {
                                      if(temp->n==NULL)
                                      {
                                      Node *t=CreateNewNode('n');
                                      temp->n=t;
                                      temp=temp->n;
                                      }
                                      else
                                      {
                                                temp=temp->n;
                                      }
                             }
                             else if(str[i]=='o' || str[i]=='O')
                             {
                                      if(temp->o==NULL)
                                      {
                                      Node *t=CreateNewNode('o');
                                      temp->o=t;
                                      temp=temp->o;
                                      }
                                      else
                                      {
                                                temp=temp->o;
                                      }
                             }else if(str[i]=='p' || str[i]=='P')
                             {
                                      if(temp->p==NULL)
                                      {
                                      Node *t=CreateNewNode('p');
                                      temp->p=t;
                                      temp=temp->p;
                                      }
                                      else
                                      {
                                                temp=temp->p;
                                      }
                             }
                             else if(str[i]=='q' || str[i]=='Q')
                             {
                                      if(temp->q==NULL)
                                      {
                                      Node *t=CreateNewNode('q');
                                      temp->q=t;
                                      temp=temp->q;
                                      }
                                      else
                                      {
                                                temp=temp->q;
                                      }
                             }
                             else if(str[i]=='r' || str[i]=='R')
                             {
                                      if(temp->r==NULL)
                                      {
                                      Node *t=CreateNewNode('r');
                                      temp->r=t;
                                      temp=temp->r;
                                      }
                                      else
                                      {
                                                temp=temp->r;
                                      }
                             }
                             else if(str[i]=='s' || str[i]=='S')
                             {
                                      if(temp->s==NULL)
                                      {
                                      Node *t=CreateNewNode('s');
                                      temp->s=t;
                                      temp=temp->s;
                                      }
                                      else
                                      {
                                                temp=temp->s;
                                      }
                             }
                             else if(str[i]=='t' || str[i]=='T')
                             {
                                      if(temp->t==NULL)
                                      {
                                      Node *t=CreateNewNode('t');
                                      temp->t=t;
                                      temp=temp->t;
                                      }
                                      else
                                      {
                                                temp=temp->t;
                                      }
                             }
                             else if(str[i]=='u' || str[i]=='U')
                             {
                                      if(temp->u==NULL)
                                      {
                                      Node *t=CreateNewNode('u');
                                      temp->u=t;
                                      temp=temp->u;
                                      }
                                      else
                                      {
                                                temp=temp->u;
                                      }
                             }
                             else if(str[i]=='v' || str[i]=='V')
                             {
                                      if(temp->v==NULL)
                                      {
                                      Node *t=CreateNewNode('v');
                                      temp->v=t;
                                      temp=temp->v;
                                      }
                                      else
                                      {
                                                temp=temp->v;
                                      }
                             }
                             else if(str[i]=='w' || str[i]=='W')
                             {
                                      if(temp->w==NULL)
                                      {
                                      Node *t=CreateNewNode('w');
                                      temp->w=t;
                                      temp=temp->w;
                                      }
                                      else
                                      {
                                                temp=temp->w;
                                      }
                             }
                             else if(str[i]=='x' || str[i]=='X')
                             {
                                      if(temp->x==NULL)
                                      {
                                      Node *t=CreateNewNode('x');
                                      temp->x=t;
                                      temp=temp->x;
                                      }
                                      else
                                      {
                                                temp=temp->x;
                                      }
                             }
                             else if(str[i]=='y' || str[i]=='Y')
                             {
                                      if(temp->y==NULL)
                                      {
                                      Node *t=CreateNewNode('y');
                                      temp->y=t;
                                      temp=temp->y;
                                      }
                                      else
                                      {
                                                temp=temp->y;
                                      }
                             }
                             else if(str[i]=='z' || str[i]=='Z')
                             {
                                      if(temp->z==NULL)
                                      {
                                      Node *t=CreateNewNode('z');
                                      temp->z=t;
                                      temp=temp->z;
                                      }
                                      else
                                      {
                                                temp=temp->z;
                                      }
                             }
                   }//for

          temp->treminate=true;

          }

// Search for Given string Present in Trie.
void Search(string str,Node *root)
{
          Node *temp=root;
          bool notfound=true;

          int len=str.length();
          for(int i=0;i
          {
                   if(str[i]=='a' || str[i]=='A')
                   {
                             if(temp->a!=NULL)
                             {
                                      temp=temp->a;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='b' || str[i]=='B')
                   {
                             if(temp->b!=NULL)
                             {
                             temp=temp->b;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='c' || str[i]=='C')
                   {
                             if(temp->c!=NULL)
                             {
                             temp=temp->c;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='d' || str[i]=='D')
                   {
                             if(temp->d!=NULL)
                             {
                             temp=temp->d;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='e' || str[i]=='E')
                   {
                             if(temp->e!=NULL)
                             {
                             temp=temp->e;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='f' || str[i]=='F')
                   {
                             if(temp->f!=NULL)
                             {
                             temp=temp->f;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='g' || str[i]=='G')
                   {
                             if(temp->g!=NULL)
                             {
                             temp=temp->g;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='h' || str[i]=='H')
                   {
                             if(temp->h!=NULL)
                             {
                             temp=temp->h;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='i' || str[i]=='I')
                   {
                             if(temp->i!=NULL)
                             {
                             temp=temp->i;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='j' || str[i]=='J')
                   {
                             if(temp->j!=NULL)
                             {
                             temp=temp->j;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='k' || str[i]=='K')
                   {
                             if(temp->k!=NULL)
                             {
                             temp=temp->k;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='l' || str[i]=='L')
                   {
                             if(temp->l!=NULL)
                             {
                             temp=temp->l;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='m' || str[i]=='M')
                   {
                             if(temp->m!=NULL)
                             {
                             temp=temp->m;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='n' || str[i]=='N')
                   {
                             if(temp->n!=NULL)
                             {
                             temp=temp->n;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='o' || str[i]=='O')
                   {
                             if(temp->o!=NULL)
                             {
                             temp=temp->o;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='p' || str[i]=='P')
                   {
                             if(temp->p!=NULL)
                             {
                             temp=temp->p;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='q' || str[i]=='Q')
                   {
                             if(temp->q!=NULL)
                             {
                             temp=temp->q;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='r' || str[i]=='R')
                   {
                             if(temp->r!=NULL)
                             {
                             temp=temp->r;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='s' || str[i]=='S')
                   {
                             if(temp->s!=NULL)
                             {
                             temp=temp->s;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='t' || str[i]=='T')
                   {
                             if(temp->t!=NULL)
                             {
                             temp=temp->t;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                                     
                             }
                   }
                   else if(str[i]=='u' || str[i]=='U')
                   {
                             if(temp->u!=NULL)
                             {
                             temp=temp->u;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                                     
                             }
                   }
                   else if(str[i]=='v' || str[i]=='V')
                   {
                             if(temp->v!=NULL)
                             {
                             temp=temp->v;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                                     
                             }
                   }
                   else if(str[i]=='w' || str[i]=='W')
                   {
                             if(temp->w!=NULL)
                             {
                             temp=temp->w;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }       
                   else if(str[i]=='x' || str[i]=='X')
                   {
                             if(temp->x!=NULL)
                             {
                             temp=temp->x;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                                     
                             }
                   }
                   else if(str[i]=='y' || str[i]=='Y')
                   {
                             if(temp->y!=NULL)
                             {
                             temp=temp->y;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                             }
                   }
                   else if(str[i]=='z' || str[i]=='Z')
                   {
                             if(temp->z!=NULL)
                             {
                             temp=temp->z;
                             }
                             else
                             {
                                      notfound=false;
                                      break;
                                     
                             }
                   }
          }//for

          if(temp->treminate==true && notfound==true)
                   cout<<"Valid Word\n";
          else
                   cout<<"Word not Found :( \n";

}




void main()
{

          Node *Tries;
          CreateTries(&Tries);

          ///////////Read file/////////////////
          //Dictionary to Create Trie.
          ifstream ifile;
          ifile.open("f:\\WordsDic.txt", ios::in);

          string input="";
          int noOfWord=0;
          if(ifile)
          {
                   while(!ifile.eof())
                   {
                             ifile>>input;
                             Insert_IN_Tries(input,&Tries);
                             noOfWord++;
                   }
          }
          else
          {
                   cout<<"File Not Open";
                   exit(0);
          }
/////////////////////////////////////////////


          cout<<"Word Count:"<

          char ch='y';
          do
          {
                   string str="";
                  
                   cout<<"Enter Input Word To Search:";
                   cin>>str;
                   Search(str,Tries);
                  
                   cout<<"Contine Search?:";cin>>ch;
                   system("cls");
          }while(ch=='y' || ch=='Y');

}

I developed this code during my Degree; this code is based on iterative method, which is lengthy but easy to understand for beginners. You may optimized this code and developed recursive one. I know this code is not perfect but not that bad, it works fine for me.
Labels:

Comments

Post a Comment

Popular posts from this blog

Font identifier and Unicode converter for Hindi

Font identifier and Unicode converter for Hindi Fonts are used to represent text in document. Fonts are mainly two kind non-Unicode and Unicode fonts. Complex scripts like Hindi and other Asian languages well represented in Unicode fonts. There are some other ways to write these languages for e.g we can use ASCII/ISCII codes to represent different characters of Hindi, but there are large numbers of characters in Hindi script as compared to English. Therefore, we always need multiple ASCII/ISCII encoded characters combination to represent a single character of Hindi Script. One major problem in these ASCII encoding based fonts is that we cannot easily transfer text from one system to another. The system must have these text fonts. There is hundreds of ASCII/ISCII encoding based fonts which are used to write Hindi text. New software systems are based on Unicode fonts.                   ...
Post a Comment
Read more

Binary Search Tree in ASP .Net

Binary Search Tree in ASP .Net To create Binary Search Tree(BST) in Asp.net application   first you need to create a Node class. Something like following : class Node {     public String data;     public int freq = 0;     public Node left, right;     public Node()     { }     public Node( String data)     {         this .data = data;         left = null ;         right = null ;     } } Next You need to create a class including different functions.Like class BinaryTreeImp {     Node root;     String outputfreq = "" ;     static int count = 0;     public BinaryTreeImp()     {      ...
Post a Comment
Read more

Hindi to Punjabi Machine Translation System

The Hindi To Punjabi Machine Translation System has been developed using Direct/Rule based Approach by Dr.Vishal Goyal and Dr. G.S Lehal. Various large size Lexicon resources  have been used to map Source and Target language words.  In general, if the two languages are structurally similar, in particular as regards lexical correspondences, morphology and word order, the case for abstract syntactic analysis seems less convincing. Since the present research work deals with a pair of closely related language, so the direct translation system is the obvious choice. The overall system architecture shown below, is adopted for Hindi to Punjabi Machine Translation System. The system is divided into three stages: Preprocessing, Translation Engine, and Post Processing stage. Following is the description of various steps of this architecture.  PreProcessing   The pre-processing stage is a collection of operations that are applied on input  data to make it pr...
1 comment
Read more