Explanation of Ruby code for building Trie data structures

Question

So I have this ruby code I grabbed from wikipedia and I modified 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 console irb, and each time I output node, it just keeps giving me an empty hash each time {}, but when I actually invoke that function build with parameter 'dogs' string, it actually does work, and outputs {"d"=>{"o"=>{"g"=>{"s"=>{}}}}}, which is totally correct.

This is probably more of a Ruby question than the actual question about how the algorithm works. I don't really have adequate Ruby knowledge to decipher what is going on there I guess.

Answer 1

You're probably getting lost inside that mess of code which takes an approach that seems a better fit for C++ than for Ruby. Here's the same thing in a more concise format that uses a special case Hash 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 doesn't have nearly the same mess with pointers and such:

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

Ruby's Enumerable module is full of amazingly useful methods like inject which is precisely what you want for a situation like this.