Обяснение на Ruby кода за изграждане на Trie структури от данни

Така че имам този ruby ​​код, който взех от wikipedia и модифицирах малко:

@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, за да дешифрирам какво се случва там, предполагам.


ruby irb
person Benny Tjia    schedule 28.01.2012    source източник
comment
Какво имаш предвид под всеки път, когато извеждам възел? Не сте сигурни какъв отговор търсите – проследили ли сте алгоритъма на хартия за малък низ? Доста е кратък.   -  person Dave Newton    schedule 28.01.2012
comment
написах 'node' на конзолата, след като написах 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

Модулът Enumerable на Ruby е пълен с невероятно полезни методи като 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 заявки, затова си позволих да го коментирам. Добър метод, BTW! - 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