ruby - 构建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，这正是您在这种情况下所需要的。