解释用于构建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

您可能会迷失在混乱的代码中，这种方法似乎比Ruby更适合C++。以下是使用特殊情况哈希进行存储的更简洁的格式中的相同内容：

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这样非常有用的方法，这正是您在这种情况下想要的。

Answer 2

我认为您只是错误地使用了irb。您应该键入整个函数，然后运行它，看看是否得到了正确的结果。如果它不起作用，你可以在这里发布你的整个IRB会话。

这里还有一个简化版本的代码：

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