Объяснение кода Ruby для построения структур данных Trie

Итак, у меня есть этот рубиновый код, который я взял из Википедии и немного изменил:

@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' string, она действительно работает и выводит {"d"=>{"o"=>{"g"=>{"s"=>{}}}}}, что совершенно правильно.

Вероятно, это больше вопрос о Ruby, чем реальный вопрос о том, как работает алгоритм. Думаю, у меня нет достаточных знаний Ruby, чтобы расшифровать, что там происходит.


ruby irb
person Benny Tjia    schedule 28.01.2012    source источник
comment
Что вы имеете в виду под каждым выходным узлом? Не знаете, какой ответ вы ищете - вы проследили алгоритм на бумаге для небольшой строки? Это довольно коротко.   -  person Dave Newton    schedule 28.01.2012
comment
я набрал «узел» в консоли после ввода node = prev_node['a'], затем он возвращает что-то вроде =› {}, что означает хэш для пустого объекта, а затем после этого я набрал node = node['b '], пытаясь смоделировать цикл for, передав другой символ в качестве ключа. когда я снова набрал «узел» после этого, он, конечно, возвращает ноль. Мне просто интересно, как он может производить {d=›{o=›{g=›{s=›{}}}}}, когда каждый раз, когда я его отслеживаю, он выглядит так, будто он всегда пуст   -  person Benny Tjia    schedule 28.01.2012
comment
Я все же рекомендую проследить алгоритм на листе бумаги, следя за каждым шагом и записывая значения всех переменных. Обратите особое внимание на prev_node[cur] = Hash.new и подумайте, что такое prev_node[cur], но помните, что prev_node сам по себе является хешем с символьным ключом, который указывает на пустой хеш (для одной итерации).   -  person Dave Newton    schedule 28.01.2012
comment
Я не понимаю, в чем твой вопрос.   -  person Phrogz    schedule 28.01.2012

Ответы (2)


arrow_upward
23
arrow_downward

Вы, вероятно, заблудились в этом беспорядке кода, который использует подход, который кажется более подходящим для 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, и это именно то, что вам нужно для такой ситуации.

person tadman    schedule 28.01.2012
comment
Как бы вы добавили еще одно слово в Trie? - person Eric Duminil; 16.03.2017
comment
@EricDuminil Вы можете звонить build столько раз, сколько хотите, разными словами. - person tadman; 16.03.2017
comment
Спасибо, я не заметил, что build — это метод экземпляра. Однако add может быть более подходящим. В зависимости от данных может быть интересно добавить некоторую информацию о конечных узлах: добавление foo после foobar ничего не меняет в текущей структуре. - person Eric Duminil; 16.03.2017
comment
@EricDuminil Это просто основа для более надежной версии, поэтому, если вам нужны такие вещи, во что бы то ни стало, удлиняйтесь! build - это метод, указанный в исходном вопросе, поэтому я просто использовал его. - person tadman; 16.03.2017
comment
Спасибо. Этот вопрос довольно высок для запросов ruby ​​trie, поэтому я позволил себе прокомментировать его. Хороший метод, кстати! - person Eric Duminil; 16.03.2017

arrow_upward
0
arrow_downward

Я думаю, что вы просто неправильно используете 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
person David Grayson    schedule 28.01.2012