ruby ​​iterate through hash

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's. (Я считаю, @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}}}} 
    }}} 
} 

р all_suffix (Trie, "Макс", "")

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

р all_suffix (Trie, "макси", "")

["maxim", "maximimlian"]