Ruby code explanation for building Trie data structures

Question

So, I have this ruby ​​code, which I grabbed from Wikipedia, and changed a bit:

@trie = Hash.new() def build(str) node = @trie str.each_char { |ch| cur = ch prev_node = node node = node[cur] if node == nil prev_node[cur] = Hash.new() node = prev_node[cur] end } end build('dogs') puts @trie.inspect 

I first ran this on the irb console, and every time I output node , it just left me an empty hash every time {} , but when I really call this assembly of functions using the 'dogs' parameter line, it actually works. and outputs {"d"=>{"o"=>{"g"=>{"s"=>{}}}}} , which is absolutely correct.

This is probably a Ruby question rather than a real question about how the algorithm works. I do not have enough Ruby knowledge to decrypt what is going on there, I think.

Answer 1

You are probably getting lost inside this mess of code that uses an approach that is better suited for C ++ than Ruby. Here is the same in a more compressed format that uses a special Hash register for storage:

 class Trie < Hash def initialize # Ensure that this is not a special Hash by disallowing # initialization options. super end def build(string) string.chars.inject(self) do |h, char| h[char] ||= { } end end end 

It works exactly the same, but it doesn't have nearly the same mess with pointers, etc.

 trie = Trie.new trie.build('dogs') puts trie.inspect 

The Ruby Enumerable module is full of surprisingly useful methods such as inject , which is exactly what you want for this situation.

Answer 2

I think you are just using irb incorrectly. You must enter the entire function, then run it and see if you get the correct results. If that doesn't work, how about you post your entire IRB session here.

A simplified version of your code is also provided:

 def build(str) node = @trie str.each_char do |ch| node = (node[ch] ||= {}) end # not sure what the return value should be end