构建 Trie 数据结构的 Ruby 代码说明 [英] Explanation of Ruby code for building Trie data structures

问题描述

所以我有这个从维基百科中抓取的 ruby​​ 代码，我做了一些修改:

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

我首先在控制台 irb 上运行它，每次我输出 node 时，它每次 {} 都会给我一个空哈希，但是当我实际调用时该函数使用参数 'dogs' 字符串构建，它确实有效，并输出 {"d"=>{"o"=>{"g"=>{"s"=>{}}}}}，这是完全正确的.

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.

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

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.

推荐答案

您可能会迷失在那些采用似乎更适合 C++ 而非 Ruby 的方法的代码中.下面是使用特殊情况 Hash 进行存储的更简洁格式的相同内容:

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 的 Enumerable 模块充满了非常有用的方法，例如 inject，这正是您在这种情况下想要的.

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

这篇关于构建 Trie 数据结构的 Ruby 代码说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！