Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > help with my recursive trie search

Reply
Thread Tools

help with my recursive trie search

 
 
chuck
Guest
Posts: n/a
 
      10-01-2007
Hello,
I wrote a simple Trie class that creates a Trie structure correctly
from character array. It will correctly recurisivley print the trie
correctly too, albeit not sorted.

The trie structue is a linked lists structure. Each node has two
pointers, next(sibling) and link(children).

I adapted the same structure that my print trie method uses to search
the trie for a particular integer index and want to return the trie
node if the index is found. The search seems to stop the recursion
when it finds the node, but returns null. The only node it correctly
find is the root.

public TrieNode findNodeIndex(TrieNode currentNode, int i){
// if(currentNode.index == i) return currentNode;
if(currentNode.link != null) findNodeIndex(currentNode.link, i);
//System.out.println( currentNode);
if(currentNode.index == i) return currentNode;
if(currentNode.next != null) findNodeIndex(currentNode.next, i);
//if(currentNode.index == i) return currentNode;
return null;
}

I have tried putting the test in various places without success, any
ideas why this fails?

If it helps i put Trie.java here
http://pastebin.ca/721376

and the test file, trietest.java here
http://pastebin.ca/721378

any help is appreciated
Chuck


 
Reply With Quote
 
 
 
 
Behrang
Guest
Posts: n/a
 
      10-01-2007
On Oct 1, 4:15 pm, chuck <(E-Mail Removed)> wrote:
> Hello,
> I wrote a simple Trie class that creates a Trie structure correctly
> from character array. It will correctly recurisivley print the trie
> correctly too, albeit not sorted.
>
> The trie structue is a linked lists structure. Each node has two
> pointers, next(sibling) and link(children).
>
> I adapted the same structure that my print trie method uses to search
> the trie for a particular integer index and want to return the trie
> node if the index is found. The search seems to stop the recursion
> when it finds the node, but returns null. The only node it correctly
> find is the root.
>
> public TrieNode findNodeIndex(TrieNode currentNode, int i){
> // if(currentNode.index == i) return currentNode;
> if(currentNode.link != null) findNodeIndex(currentNode.link, i);
> //System.out.println( currentNode);
> if(currentNode.index == i) return currentNode;
> if(currentNode.next != null) findNodeIndex(currentNode.next, i);
> //if(currentNode.index == i) return currentNode;
> return null;
>
> }
>
> I have tried putting the test in various places without success, any
> ideas why this fails?
>
> If it helps i put Trie.java herehttp://pastebin.ca/721376
>
> and the test file, trietest.java herehttp://pastebin.ca/721378
>
> any help is appreciated
> Chuck


Hi Chuck,

You are returning from findNodeIndex too early. I have posted the
corrected findNodeIndex here:

http://pastebin.ca/721497

Also, in English, it is spelled "Tree", not "Trie"

-Behrang

 
Reply With Quote
 
 
 
 
Matt Humphrey
Guest
Posts: n/a
 
      10-01-2007

"Behrang" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
| On Oct 1, 4:15 pm, chuck <(E-Mail Removed)> wrote:
| > Hello,
| > I wrote a simple Trie class that creates a Trie structure correctly
| > from character array. It will correctly recurisivley print the trie
| > correctly too, albeit not sorted.
| >
| > The trie structue is a linked lists structure. Each node has two
| > pointers, next(sibling) and link(children).
| >
| > I adapted the same structure that my print trie method uses to search
| > the trie for a particular integer index and want to return the trie
| > node if the index is found. The search seems to stop the recursion
| > when it finds the node, but returns null. The only node it correctly
| > find is the root.
| >
| > public TrieNode findNodeIndex(TrieNode currentNode, int i){
| > // if(currentNode.index == i) return currentNode;
| > if(currentNode.link != null) findNodeIndex(currentNode.link, i);
| > //System.out.println( currentNode);
| > if(currentNode.index == i) return currentNode;
| > if(currentNode.next != null) findNodeIndex(currentNode.next, i);
| > //if(currentNode.index == i) return currentNode;
| > return null;
| >
| > }
| >
| > I have tried putting the test in various places without success, any
| > ideas why this fails?
| >
| > If it helps i put Trie.java herehttp://pastebin.ca/721376
| >
| > and the test file, trietest.java herehttp://pastebin.ca/721378
| >
| > any help is appreciated
| > Chuck
|
| Hi Chuck,
|
| You are returning from findNodeIndex too early. I have posted the
| corrected findNodeIndex here:
|
| http://pastebin.ca/721497
|
| Also, in English, it is spelled "Tree", not "Trie"

There is a data structure called a "trie"
http://en.wikipedia.org/wiki/Trie.

Matt Humphrey http://www.iviz.com/


 
Reply With Quote
 
Behrang
Guest
Posts: n/a
 
      10-01-2007
Jeez! I have studied CS for more than 6 years and this is the first
time I have seen this term )

Matt Humphrey wrote:
> "Behrang" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) ups.com...
> | On Oct 1, 4:15 pm, chuck <(E-Mail Removed)> wrote:
> | > Hello,
> | > I wrote a simple Trie class that creates a Trie structure correctly
> | > from character array. It will correctly recurisivley print the trie
> | > correctly too, albeit not sorted.
> | >
> | > The trie structue is a linked lists structure. Each node has two
> | > pointers, next(sibling) and link(children).
> | >
> | > I adapted the same structure that my print trie method uses to search
> | > the trie for a particular integer index and want to return the trie
> | > node if the index is found. The search seems to stop the recursion
> | > when it finds the node, but returns null. The only node it correctly
> | > find is the root.
> | >
> | > public TrieNode findNodeIndex(TrieNode currentNode, int i){
> | > // if(currentNode.index == i) return currentNode;
> | > if(currentNode.link != null) findNodeIndex(currentNode.link, i);
> | > //System.out.println( currentNode);
> | > if(currentNode.index == i) return currentNode;
> | > if(currentNode.next != null) findNodeIndex(currentNode.next, i);
> | > //if(currentNode.index == i) return currentNode;
> | > return null;
> | >
> | > }
> | >
> | > I have tried putting the test in various places without success, any
> | > ideas why this fails?
> | >
> | > If it helps i put Trie.java herehttp://pastebin.ca/721376
> | >
> | > and the test file, trietest.java herehttp://pastebin.ca/721378
> | >
> | > any help is appreciated
> | > Chuck
> |
> | Hi Chuck,
> |
> | You are returning from findNodeIndex too early. I have posted the
> | corrected findNodeIndex here:
> |
> | http://pastebin.ca/721497
> |
> | Also, in English, it is spelled "Tree", not "Trie"
>
> There is a data structure called a "trie"
> http://en.wikipedia.org/wiki/Trie.
>
> Matt Humphrey http://www.iviz.com/


 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      10-01-2007
Behrang wrote:
> Jeez! I have studied CS for more than 6 years and this is the first
> time I have seen this term )


Tries are discussed in Knuth's The Art of Computer Programming (volume
1, I think). The only major usage I have ever heard of them was in TeX's
hyphenation algorithm. It is, to say the least, not a very popular data
structure.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Matt Humphrey
Guest
Posts: n/a
 
      10-01-2007

"Joshua Cranmer" <(E-Mail Removed)> wrote in message
newshdMi.3545$Hb2.3424@trndny07...
| Behrang wrote:
| > Jeez! I have studied CS for more than 6 years and this is the first
| > time I have seen this term )
|
| Tries are discussed in Knuth's The Art of Computer Programming (volume
| 1, I think). The only major usage I have ever heard of them was in TeX's
| hyphenation algorithm. It is, to say the least, not a very popular data
| structure.

I thought they were used just for dictionaries. When I learned how to do
them (long ago) one of their advantages was that they could be traversed
while in an dense binary format--instead of storing keys and offsets only
certain bit counts are stored. Wikipedia says they're part of the fastest
technique for sorting strings.

Matt Humphrey http://www.iviz.com/


 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      10-01-2007
Matt Humphrey wrote:
> "Joshua Cranmer" <(E-Mail Removed)> wrote in message
> newshdMi.3545$Hb2.3424@trndny07...
> | Behrang wrote:
> | > Jeez! I have studied CS for more than 6 years and this is the first
> | > time I have seen this term )
> |
> | Tries are discussed in Knuth's The Art of Computer Programming (volume
> | 1, I think). The only major usage I have ever heard of them was in TeX's
> | hyphenation algorithm. It is, to say the least, not a very popular data
> | structure.
>
> I thought they were used just for dictionaries. When I learned how to do
> them (long ago) one of their advantages was that they could be traversed
> while in an dense binary format--instead of storing keys and offsets only
> certain bit counts are stored. Wikipedia says they're part of the fastest
> technique for sorting strings.


s/very popular/well-known/

I too have known some semantics for a while, but I didn't know them
under the name `trie'.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Christian
Guest
Posts: n/a
 
      10-01-2007
Joshua Cranmer schrieb:
> Behrang wrote:
>> Jeez! I have studied CS for more than 6 years and this is the first
>> time I have seen this term )

>
> Tries are discussed in Knuth's The Art of Computer Programming (volume
> 1, I think). The only major usage I have ever heard of them was in TeX's
> hyphenation algorithm. It is, to say the least, not a very popular data
> structure.
>

your os probably uses these tries to index your disc storage for faster
searching.. (suffixtrees are also tries)

Also some state of the art p2p systems use a distributed trie instead of
a normal dht.
 
Reply With Quote
 
chuck
Guest
Posts: n/a
 
      10-01-2007
>
> | You are returning from findNodeIndex too early. I have posted the
> | corrected findNodeIndex here:
> |
> | http://pastebin.ca/721497
> |
> | Also, in English, it is spelled "Tree", not "Trie"
>
> There is a data structure called a "trie"
> http://en.wikipedia.org/wiki/Trie.
>
> Matt Humphrey http://www.iviz.com/



Thanks Behrang.

Yes, I too thought Trie was a misprint, however it is a real data
structure. In my case, I am using a trie for Lempel-Ziv
encoding/decoding.

Chuck

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Patricia trie vs binary search. markspace Java 32 05-30-2012 01:25 AM
Trie search algorithm Justin To Ruby 0 06-13-2008 05:42 PM
compressed suffix trie Joseph Java 1 09-22-2004 07:23 PM
compressed suffix trie Joseph C++ 3 09-22-2004 06:02 PM
[ANN] Trie for Python Miki Tebeka Python 0 10-01-2003 03:36 PM



Advertisments