用于构建Trie数据结构的Ruby代码的说明

Question

所以我有从维基百科中抓取的这个ruby代码,我修改了一下:

@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

我第一次跑这在控制台IRB,每一次我输出node,它只是让每次给我一个空的哈希值{},但是当我实际调用该函数建立与参数'dogs'字符串,它实际上做的工作,和产出{"d"=>{"o"=>{"g"=>{"s"=>{}}}}},这是完全正确的.

这可能是一个Ruby问题,而不是关于算法如何工作的实际问题.我真的没有足够的Ruby知识来破译那里发生的事情.

Answer 1

您可能会迷失在那些混乱的代码中,这种方法似乎更适合C++而不是Ruby.这是一个更简洁的格式,使用特殊情况Hash进行存储:

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

它的工作方式完全相同,但是没有几乎与指针混淆相同的东西:

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

Ruby的Enumerable模块充满了非常有用的方法inject,正是这样的情况正是你想要的.