Thread: trie algorithm question..

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    trie algorithm question..

    i read this article
    Trie - Wikipedia, the free encyclopedia

    i know that the use of trie takes less time then BST
    i cant understand how the coding goes into a tree??
    the example shows some letters with arrows
    and i dont know what they are trying to encode
    and how they retrieve the data
    ??

  2. #2
    uh oh
    Join Date
    Jan 2005
    Location
    Ontario, CA
    Posts
    66
    From the sounds of a quick read, though I could be wrong since I've never used this type of tree myself, sounds like items along the tree are being organized based on string characters starting from the beginning of the character array, and spread out based on the first few characters (thus if you look at the diagram it almost looks like they were trying to organize elements found commonly in a dictionary).

    What they are trying to describe is that the tree itself does not store all of the strings, rather a "look-up" tree where I'm sure pointers reference to the actual elements for accessing them once you use the tree to locate what you need.

    You would have to read the document in detail to I'm sure get the full scope of the algorithm. Hopefully this was of more help.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Obviously, what you use a trie for and what is stored in it are connected.

    The principle of a trie is that you index with a character (or a character minus an offset, more commonly).

    I didn't know what it was called, but I implemented something like this to decode variable length telephone numbers - based on the starting digits, at some point it will know the length of the number [although I think Germany has a different system - where a number can end with a 0 or a longer extension number with PBX solutions]. So my trie would store a pointer to the next elements until such a point that the number could be identified to number of digits - a flag in the structure told me whether it was "know" or "need to follow the tree".

    When using T9 texting system on mobile phones, a trie is used to identify what letters are available to follow what has been typed so far. The index here is the digit on the keypad. I've not thought through the entire structure needed for this, but it's basically a trie that tells the SMS application which letters go together to form words - the words are sorted by frequency [in some large text], so the most commonly used word made up from the possible letters is presented as the first one if there are multiple words available.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i cant understand this line in the article
    "Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree shows what key it is associated with."
    Last edited by transgalactic2; 04-04-2009 at 10:21 AM.

  5. #5
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    To find the "key" for each node, you start at the node and trace back to the root assembling each value along the way. The picture in the wiki page is misleading since each node shows the assembled key.

    Here's an example trie for the words "cat", "car", and "chi". Notice how the "key" is constructed using the path from the root to the node.
    Code:
         c
       /  \
      a    h
     / \    \
    t   r    i
    The BST version would look like this.
    Code:
       cat
       /  \
    car   chi

  6. #6
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i see the words in your trie tree
    but how the number values are involved
    for string aac i got 001
    why
    ??

  7. #7
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    That sounds like something specific to the encoding in your implementation. The number could indicate which child to go to. So in my example, "car" would be 01, and "cat" would be 00. That's just a guess at your encoding though.

    If you post some code we may be able to help more.

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    ahh thanks

  9. #9
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    this my the code
    Code:
    #define N 3
    typedef struct tree {
    	int value;
    	struct tree **sons;  // array of pointers 
    } tree;
    
    tree * what1(){
    	int i;
    	tree *temp = (tree *)malloc(sizeof(tree));
    if(!temp) exit(1);
    	temp->value=0;
    	temp->sons = (tree **)malloc(N * sizeof(tree *)); 
    	if(!temp->sons) exit(1);
    	for(i=0; i<N; i++)
      temp->sons[i]=NULL;
    	return temp;
    }
    
    void what2(tree *root, char *text){
    	if(!(*text)){
    		root->value++;
    		return;
    	}
    	if(!root->sons[*text-'a'])	
    root->sons[*text-'a']= what1();
    	what2(root->sons[*text-'a'],text+1);
    }
    
    void what3(tree *root){
    	int i;
    	if(!root) return;
    	printf("%d ",root->value);
    	for(i=0; i<N; i++)
    		what3(root->sons[i]);
    }
    
    void main(){
    	tree *root= what1();
    	int i;
    	char *text[]={"aac","aa","bbb","aac","aa","aabc","a"},
     stack[80]={0};
    	for(i=0; i<7; i++)
    		what2(root,text[i]);
    	what3(root);
    	putchar('\n');
    }

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Why don't you just compile that and run it? Seeing as it is the fourth time you have posted this code, and it seems like you want US to figure out what it does...

    Or is there a SPECIFIC question you have about the code and it's functionality?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    Quote Originally Posted by transgalactic2 View Post
    this my the code
    Code:
    #define N 3
    typedef struct tree {
    	int value;
    	struct tree **sons;  // array of pointers 
    } tree;
    
    tree * what1(){
    	int i;
    	tree *temp = (tree *)malloc(sizeof(tree));
    if(!temp) exit(1);
    	temp->value=0;
    	temp->sons = (tree **)malloc(N * sizeof(tree *)); 
    	if(!temp->sons) exit(1);
    	for(i=0; i<N; i++)
      temp->sons[i]=NULL;
    	return temp;
    }
    
    void what2(tree *root, char *text){
    	if(!(*text)){
    		root->value++;
    		return;
    	}
    	if(!root->sons[*text-'a'])	
    root->sons[*text-'a']= what1();
    	what2(root->sons[*text-'a'],text+1);
    }
    
    void what3(tree *root){
    	int i;
    	if(!root) return;
    	printf("%d ",root->value);
    	for(i=0; i<N; i++)
    		what3(root->sons[i]);
    }
    
    void main(){
    	tree *root= what1();
    	int i;
    	char *text[]={"aac","aa","bbb","aac","aa","aabc","a"},
     stack[80]={0};
    	for(i=0; i<7; i++)
    		what2(root,text[i]);
    	what3(root);
    	putchar('\n');
    }
    void main()??
    After posting 1000+ posts on this forum, you should know better.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Serializing/deserializing problem
    By vsla in forum C Programming
    Replies: 3
    Last Post: 04-21-2008, 03:55 PM
  2. Quick Algorithm Question
    By cjwenigma in forum C++ Programming
    Replies: 3
    Last Post: 11-01-2007, 10:39 AM
  3. Design layer question
    By mdoland in forum C# Programming
    Replies: 0
    Last Post: 10-19-2007, 04:22 AM
  4. STL algorithm question
    By Reggie in forum C++ Programming
    Replies: 1
    Last Post: 04-22-2003, 09:04 AM
  5. More a math question than an algorithm
    By Gustaff in forum C Programming
    Replies: 1
    Last Post: 01-28-2003, 01:10 PM