Asp Forum - Trie data structure

Justin To

6/10/2008 10:45:00 PM

I'm trying to implement a trie data structure for my parsing program
that parses numbers....I'm lost as to what the algorithm would look
like. Also, I don't fully understand the wikipedia definition at
http://en.wikipedia.org... when it says "...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..."

Any help is appreciated!
--
Posted via http://www.ruby-....

16 Answers

nicholasmabry@gmail.com

6/10/2008 11:33:00 PM

On Jun 10, 5:44 pm, Justin To <te...@hotmail.com> wrote:
> I'm trying to implement a trie data structure for my parsing program
> that parses numbers....I'm lost as to what the algorithm would look
> like. Also, I don't fully understand the wikipedia definition athttp://en.wikipedia.org/wik... it says "...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..."
>
> Any help is appreciated!
> --
> Posted viahttp://www.ruby-....

The basic idea is that each node contains only a partial key, the
final piece of its full key. So if the node you're adding should have
the full key "hi":
- It will contain the partial key "i".
- Its parent will have the partial key "h".
- Its grandparent will have an empty partial key - the root node.

As the lookup algorithm example on the wiki page describes, looking up
a value by key is a matter of starting at the root node and following
each path that leads you to the next item in the full key. This
differs from a binary tree in that the tree structure is not only a
means to locate the key, but a reflection of the key itself.

Have fun!

Dave Bass

6/11/2008 9:35:00 AM

Justin To wrote:
> Also, I don't fully understand the wikipedia definition at
> http://en.wikipedia.org... when it says "...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..."

This web page has an example of data represented as a trie:

http://tinyurl....

The example is a set of words with each node corresponding to a
character.

There are various ways of implementing these sorts of data structures,
but hashes provide a powerful basis.
--
Posted via http://www.ruby-....

Justin To

6/11/2008 3:50:00 PM

Most of the articles I read say that instead of storing a value at a
node, it stores a reference. How would one accomplish this in Ruby?
Also, I'm trying to make a trie to store numbers from 100,000 to
999,999. Basically, what would the trie look like?

Thanks for the help!
--
Posted via http://www.ruby-....

Martin DeMello

6/11/2008 4:40:00 PM

On Wed, Jun 11, 2008 at 8:50 AM, Justin To <tekmc@hotmail.com> wrote:
> Most of the articles I read say that instead of storing a value at a
> node, it stores a reference. How would one accomplish this in Ruby?
> Also, I'm trying to make a trie to store numbers from 100,000 to
> 999,999. Basically, what would the trie look like?

Take a look at http://rubyquiz.com/qu...

martin

Justin To

6/11/2008 8:04:00 PM

I can't seem to grasp the algorithm for a trie. Can someone please help
me... I need the trie to store 6-digit numbers. I've read all the above
articles, but I still have no clue of how I should begin.

Thanks for the help!
--
Posted via http://www.ruby-....

Martin DeMello

6/11/2008 9:51:00 PM

On Wed, Jun 11, 2008 at 1:04 PM, Justin To <tekmc@hotmail.com> wrote:
> I can't seem to grasp the algorithm for a trie. Can someone please help
> me... I need the trie to store 6-digit numbers. I've read all the above
> articles, but I still have no clue of how I should begin.

here's a quick example of a trie storing the three digit numbers 123,
145, 207, 451, 455. we take advantage of the fact that all numbers are
known to be the same length, otherwise you also need to store a
"number_ends_here?" flag on each node

{ :root =>
{ 1 =>
{ 2 => { 3 => true } },
{ 4 => { 5 => true } }
},
{ 2 =>
{ 0 => { 7 => true } }
},
{ 4 =>
{ 5 =>
{ 1 => true, 5 => true } }
}
}

you traverse it thus (untested code, but it gives the basic idea):

node = trie[:root]
num_to_check = "123"
num_to_check.split(//).each {|digit|
node = node[digit]
return false unless node
}

return true

martin

Justin To

6/12/2008 5:06:00 PM

class Trie
attr_reader :value, :children
def initialize(value=nil)
@value = value # The corresponding value
@children = [] # Store hashes inside of the
hash
end

def <<(value)
sub_trie = Trie.new(value)
@children << sub_trie
return sub_trie
# End of def <<(value)
end

# Return true if value exists or nil if value D.N.E.
def child_value?(value)
if @children.empty? # If @children is empty, then there
are no children
return 'empty'
else
# If one of the children contains the value then return true
@children.each do |child|
if(child.value==value)
return true
else
return nil
end
end
end
# End of def child_value?(value)
end

# Return the child that added the value if the value D.N.E. else
return nil, the value already exists
# DO NOT ALTER OR CALL OUTSIDE OF CLASS--belongs to def
add_number(value)
def add_digit(digit)
if(!child_value?(digit))
child = self<<(digit)
puts "#{digit} added"
return child
else
puts "#{digit}: already exists in the child."
return nil
end
end

def add_number(number)
current_node = self
number.to_s.each_byte do |byte|
puts "add_number #{byte.chr.to_i}"
puts "Nodeclass: " + current_node.class.to_s
current_node = current_node.add_digit(byte.chr.to_i)
end

end

# End of class Trie
end

t = Trie.new
t << 3

t.add_number(234)

Output:

HashTrie3.rb:50:in `add_number': undefined method `add_digit' for
nil:NilClass (NoMethodError)
from HashTrie3.rb:47:in `each_byte'
from HashTrie3.rb:47:in `add_number'
from HashTrie3.rb:62
add_number 2
Nodeclass: Trie
2 added
add_number 3
Nodeclass: Trie
3: already exists in the child. # ?
add_number 4 # ?
Nodeclass: NilClass # ?

Somewhere I'm not saving the current node correctly so when it adds 3,
it's adding it into the same array that the first 3 (t<<3) and the 2
[t.add_number(234)] is in. But then again, I could have messed up
somewhere else. Maybe I'm passing around copies of the current node and
not the ACTUAL one.

Any help is much appreciated!!!!!!!!!!!!!!!!!!!!

Justin
--
Posted via http://www.ruby-....

Jimmy Kofler

6/12/2008 6:53:00 PM

> Justin To wrote:
> I can't seem to grasp the algorithm for a trie. Can someone please help
> me... I need the trie to store 6-digit numbers. I've read all the above
> articles, but I still have no clue of how I should begin.
>
> Thanks for the help!

Maybe also check out the SimpleTrie class at
http://snippets.dzone.com/posts...

Cheers,
j.k.

--
Posted via http://www.ruby-....

Justin To

6/12/2008 8:23:00 PM

class Trie
attr_reader :value, :children
attr_accessor :number_exists
def initialize(value=nil, number_exists=false)
@value = value
@children = []
@number_exists = number_exists # BOOL
end

def <<(value)
sub_trie = Trie.new(value)
children << sub_trie
return sub_trie
end
#--------------------------------------------------------------------------------------

def child_value?(value, node)

if(node.children.empty?)
return 'empty' # Return: 'empty', children[i],
'D.N.E.'
else
i=0; while(i<node.children.size)
if(node.children[i].value==value)
puts "#{value} exists in #{node}."
return node.children[i]
else if(i==node.children.size-1)
return 'D.N.E.'
end
end
i+=1
end
end

end

def add_digits(digitArray)

node = self
while(digitArray[0])
scan = child_value?(digitArray[0], node) # Scan the trie for
the digit

# Empty case
if(scan=='empty')
node = node<<(digitArray[0])
if(digitArray.size==1)
node.number_exists = true
end
digitArray.delete(digitArray[0])

else if(scan=='D.N.E.')
node = node<<(digitArray[0])
if(digitArray.size==1)
node.number_exists = true
end
digitArray.delete(digitArray[0])
else if(scan.is_a?(Trie))
if(digitArray.size==1)
scan.number_exists = true # ??
end
node = scan
digitArray.delete(digitArray[0])
else
puts "**Scan error**"
digitArray.delete(digitArray[0])
end
end
end

end
#end function
end

def add_number(number)
if(number.is_a?(Fixnum))
digitArray = []
number.to_s.each_byte { |byte| digitArray.push(byte.chr.to_i) }
add_digits(digitArray)
else
puts "\'#{number}\' not a valid *Fixnum*"
end
end

# End of class Trie
end

t = Trie.new

t.add_number(434)

#984343525
# looking for a (4), (3 and 5)
# 9843--52-
puts "\n"
puts t.children[0].children[0].children.size

My program can add most numbers fine... but if it comes to something
like 434 or 4343 or I suppose any similar patterns, it doesn't work.
I've tried it with only 1 number, that way all you have to do is look
through def add_digits(digitArray) at the section for the Empty Case.

Any help is much appreciated!

Thanks!
--
Posted via http://www.ruby-....

Justin To

6/12/2008 8:38:00 PM

class Trie
attr_reader :value, :children
attr_accessor :number_exists
def initialize(value=nil, number_exists=false)
@value = value
@children = []
@number_exists = number_exists # BOOL
end

def <<(value)
sub_trie = Trie.new(value)
children << sub_trie
return sub_trie
end
#--------------------------------------------------------------------------------------

def child_value?(value, node)

if(node.children.empty?)
return 'empty' # Return: 'empty', children[i],
'D.N.E.'
else
i=0; while(i<node.children.size)
if(node.children[i].value==value)
return node.children # Something wrong here ????
else if(i==node.children.size-1)
return 'D.N.E.'
end
end
i+=1
end
end

end

def add_digits(digitArray)

node = self
while(digitArray[0])
scan = child_value?(digitArray[0], node) # Scan the trie for
the digit

# Empty case
if(scan=='empty')
node = node<<(digitArray[0])
if(digitArray.size==1)
node.number_exists = true
end
digitArray.delete(digitArray[0])

end

end
#end function
end

#--------------------------------------------------------------------------------------
def add_number(number)
if(number.is_a?(Fixnum))
digitArray = []
number.to_s.each_byte { |byte| digitArray.push(byte.chr.to_i) }
add_digits(digitArray)
else
puts "\'#{number}\' not a valid *Fixnum*"
end
end

# End of class Trie
end

t = Trie.new

t.add_number(434)

#984343525
# looking for a (4), (3 and 5)
# 9843--52-
puts "\n"

# Looking for size = 1
puts t.children[0].children[0].children.size

Actually, you can just look at this portion of code
--
Posted via http://www.ruby-....

comp.lang.ruby

Trie data structure

Justin To

nicholasmabry@gmail.com

Dave Bass

Justin To

Martin DeMello

Justin To

Martin DeMello

Justin To

Jimmy Kofler

Justin To

Justin To

x Login to ForumsZone