紅寶石通過散列迭代

Question

我有散列的散列。這個散列有一個字典。我需要找到它具有相同根的所有匹配。例如，我有：

#<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 

Answer 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')                                                   
# => [] 

Answer 2

這不是一個完整的答案。它只是照顧前綴。

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。然後，您需要展開該散列並將其與前綴結合使用。對於那部分，你可能想參考答案here。

Answer 3

這是我嘗試

# 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（線索， 「最大」， 「」）

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

p all_suffix（線索， 「最大」， 「」）

["maxim", "maximimlian"]