Explicación de código Ruby para la construcción de estructuras de datos Trie

Así que tiene el código de rubí me agarró de Wikipedia y que modifica un poco:Explicación de código Ruby para la construcción de estructuras de datos Trie

@trie = Hash.new() 
def build(str) 
    node = @trie 
    str.each_char { |ch| 
     cur = ch 
     prev_node = node 
     node = node[cur] 
     if node == nil 
     prev_node[cur] = Hash.new() 
     node = prev_node[cur] 
     end 
    } 
    end 

build('dogs') 

puts @trie.inspect

me encontré por primera vez esta en el IRB de la consola, y cada vez que la salida node, simplemente me sigue dando un hash vacío cada vez {}, pero cuando realmente invoco esa función compila con el parámetro 'dogs' cadena, realmente funciona, y saca {"d"=>{"o"=>{"g"=>{"s"=>{}}}}}, lo cual es totalmente correcto.

Esto es probablemente más una pregunta de Ruby que la pregunta real sobre cómo funciona el algoritmo. Realmente no tengo suficiente conocimiento de Ruby para descifrar lo que está pasando allí, supongo.

Fuente

2012-01-28 Benny Tjia

¿Qué quiere decir con "cada vez que salgo nodo"? ¿No está seguro de qué tipo de respuesta está buscando? ¿Ha rastreado el algoritmo en papel para una pequeña cadena? Es bastante corto. –

escribí 'nodo' en la consola después de escribir en node = prev_node ['a'], luego devuelve algo como => {} que significa hash para vaciar el objeto, y luego de eso escribí node = node [' b '], tratando de simular el bucle for pasando una chave diferente como clave. cuando escribí 'node' de nuevo después de eso, devuelve nil, por supuesto. Me pregunto cómo puede producir {"d" => {"o" => {"g" => {"s" => {}}}}} cuando cada vez que lo trazo, parece que siempre está vacío –

Todavía recomiendo seguir el algoritmo con un trozo de papel, seguir cada paso y anotar los valores de todas las variables. Mire particularmente en 'prev_node [cur] = Hash.new', y considere lo que' prev_node [cur] 'es - pero recuerde que' prev_node' en sí mismo es un hash con una clave de carácter, que apunta a un hash vacío (para una iteración). –

Probablemente se esté perderse dentro de ese lío de código que toma un enfoque que parece una mejor opción para C++ que para Ruby. Aquí está lo mismo en un formato más conciso que utiliza un hash de casos especiales para el almacenamiento:

class Trie < Hash 
    def initialize 
    # Ensure that this is not a special Hash by disallowing 
    # initialization options. 
    super 
    end 

    def build(string) 
    string.chars.inject(self) do |h, char| 
     h[char] ||= { } 
    end 
    end 
end

Funciona exactamente el mismo, pero no tiene casi el mismo desorden con los punteros y tal:

trie = Trie.new 
trie.build('dogs') 
puts trie.inspect

El módulo Enumerable de Ruby está lleno de métodos asombrosamente útiles como inject que es precisamente lo que desea para una situación como esta.

Fuente

2012-01-28 02:54:45 tadman

¡Solución brillante! – DaniG2k

¿Cómo agregarías otra palabra al Trie? –

@EricDuminil Puedes invocar 'build' tantas veces como quieras con diferentes palabras. – tadman

Creo que solo está utilizando IRB incorrectamente. Debería escribir toda la función, ejecutarla y ver si obtiene los resultados correctos. Si no funciona, ¿qué tal si publicas aquí toda tu sesión de IRB?

También aquí es una versión simplificada de su código:

def build(str) 
    node = @trie 
    str.each_char do |ch| 
    node = (node[ch] ||= {}) 
    end 
    # not sure what the return value should be 
end

Fuente

2012-01-28 02:49:33

Explicación de código Ruby para la construcción de estructuras de datos Trie

Respuesta

Cuestiones relacionadas