-1

この T9 トライ ジェネレーターの実装には大きな欠陥があります。ツリーに追加された以前の単語を追加するのではなく、上書きしています。驚かないでただ呆然としてる…

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"}}}}>
4

1 に答える 1

0

問題は次の行にあるようです。

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

ここでnode[:end]は、1 つの単語しか指定できず、2 つの単語が同じ t9 キーのシーケンスを持つ場合は上書きされます。代わりにこれを試してください：

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

このようにして、分岐の最後に単語の配列ができます。単語がすでにトライに含まれているかどうかを確認することを忘れないでください。

于 2013-09-04T22:42:13.923 に答える