0

私はハッシュのハッシュを持っています。このハッシュには辞書があります。同じルートを持つすべての一致を見つける必要があります。たとえば、私は持っています：

#<Trie:0x00000001bf9a40 @root={
  "m"=>{"a"=>{"x"=>{
    :end=>true,
    "i"=>{"m"=>{
      :end=>true,
      "i"=>{"m"=>{"l"=>{"i"=>{"a"=>{"n"=>{:end=>true}}}}}}
    }},
    "w"=>{"e"=>{"l"=>{"l"=>{:end=>true}}}}
  }}}
}>

と言葉"max"、、、。"maxim"_ このハッシュのすべての単語をルートで取得するにはどうすればよいですか? 例えば"maximilian""maxwell"

t = Trie.new
t.add( .....# now we added words
t.find('max')
#result all words which begins from 'max'
t.find('maxim')
#result all words which begins from 'maxim' => maxim, maximilian
4

3 に答える 3

1

私のfind方法は@sawaの方法と非常に似ているようです。(@sawa さんは、このような場合に使用する方法を最初に教えてくれた人だと思うので、それは適切です。inject)&:[]

与えられた:

class Trie
  def initialize(root)
    @root = root # Just a shortcut to use your data and focus on your question
  end

  # Recurses through Hash `h` to find all words starting with `s`
  def words(h, s, a=[])
    h.each do |k, v|
      if k == :end
        a << s
      else
        words(v, s+k, a)
      end
    end

    a
  end

  private :words

  def find(start)
    words(start.chars.inject(@root, &:[]), start) rescue []
  end
end

t = Trie.new({"m"=>{"a"=>{"x"=>{:end=>true,
                              "i"=>{"m"=>{:end=>true,
                                         "i"=>{"m"=>{"l"=>{"i"=>{"a"=>{"n"=>{:end=>true}}}}}}}},
                              "w"=>{"e"=>{"l"=>{"l"=>{:end=>true}}}}}}}})

できるよ：

t.find('max')
# => ["max", "maxim", "maximimlian", "maxwell"]
t.find('maxi')
# => ["maxim", "maximimlian"]
t.find('maximi')
# => ["maximimlian"]
t.find('maxw')
# => ["maxwell"]
t.find('x')                                                                                                                                                                                                        
# => []
于 2013-07-14T10:00:10.037 に答える
0

これが私の試みです

# Returns all the possible matching suffixes for the `given` string.
# trie is a map of map of .. strings delimitted by :end
# cur_word is a scratch pad for storing characters from prev level. 
# Pass empty string for cur_word or create a wrapper around this function.
def all_suffix(trie, given, cur_word)
   #Suffixes found in the current iteration
   suffixes = []


   #The current node (character at which we want the Hash)
   at = given[0] 

   cur_word << (at || '')

   cur_trie = trie[at] || trie[cur_word[-1]] || {}

   #When we are at the end of the string, given.length <= 1 and we must print out all suffixes
   cur_trie.each do |next_str, next_trie|

     if next_str == :end
       #Only if we reached the end of the `given` string
       suffixes << cur_word if given.length <= 1
     else
       #Delete the first character and continue iteration
       other_suffixes = all_suffix({ next_str => next_trie },
                              given[1..-1] || '',
                              cur_word + (given.length > 1 ? '' : next_str))

       suffixes << other_suffixes.flatten if other_suffixes.size > 0 
     end
   end
   suffixes.flatten
end 

trie = {
  "m"=>{"a"=>{"x"=>{
    :end=>true,
    "i"=>{"m"=>{
      :end=>true,
      "i"=>{"m"=>{"l"=>{"i"=>{"a"=>{"n"=>{:end=>true}}}}}}
    }},
    "w"=>{"e"=>{"l"=>{"l"=>{:end=>true}}}}
  }}}
}

p all_suffix(trie, "max", "")

["max", "maxim", "maximimlian", "maxwell"]

p all_suffix(trie, "maxi", "")

["maxim", "maximimlian"]
于 2013-07-14T12:00:00.630 に答える
0

これは完全な答えではありません。プレフィックスを処理するだけです。

class Trie
  def find prefix
    expand(prefix, prefix.each_char.inject(@root, &:[])) rescue []
  end
  def expand prefix, affix
    #TODO
  end
end

が与えられt.find("maxi")た場合、実装された部分は次をprefix.each_char.inject(@root, &:[])返します。

{"m" => {
  :end => true,
  "i"  => {"m" => {"l" => {"i" => {"a" => {"n" => {:end => true}}}}}}
}}

それとプレフィックス"maxi"を に渡しTrie#expandます。次に、そのハッシュを展開してプレフィックスと組み合わせる必要があります。その部分については、こちらの回答を参照してください。

于 2013-07-14T09:10:36.040 に答える