Тонкая настройка T9 Trie в Ruby для добавления новых слов

Question

Эта реализация T9 Trie Generator имеет большой недостаток. Он переписывает предыдущие слова, добавленные в дерево, а не добавляет их. Я не удивлен этим, просто в тупик...

class Trie
  def initialize
    @root = Hash.new
  end

# do a for loop here
  def build(word) 
    node = @root
    t9num = word.tr('a-z', '22233344455566677778889999')
    t9num.each_char do |ch|
      node[ch] ||= Hash.new
      node = node[ch]
    end
    node[:end] = "#{word}"
  end

  def find(str) 
    node = @root
    str.each_char do |ch|
      return nil unless node = node[ch]
    end
    node[:end] && true
  end
end

Эти команды:

t = Trie.new
t.build('buy')
t.build('build')
t.build('builder')
t.build('act')
t.build('acu')
puts t.inspect

Выведите это:

#<Trie:0x0000010103ea60 @root={"2"=>{"8"=>{"9"=>{:end=>"buy"}, "4"=>{"5"=>{"3"=>{:end=>"build", "3"=>{"7"=>{:end=>"builder"}}}}}}, "2"=>{"8"=>{:end=>"acu"}}}}>

Answer 1

Мне кажется, что проблема в этой строке:

node[:end] = "#{word}"

Здесь твой node[:end] может быть только одним словом, и оно перезаписывается, если два слова имеют одинаковую последовательность клавиш t9. Попробуйте это вместо этого:

(node[:end] ||= []) << word

Таким образом, у вас будет массив слов в конце ветви. Не забудьте проверить, если слово уже в три.