Trie

benchmark.rb

require "benchmark"

trie = Trie.new
dictionary = IO.read("/usr/share/dict/words").split("\n")

puts "/usr/share/dict/words has #{dictionary.size} words."

Benchmark.bm(15) do |benchmark|
  benchmark.report("build (iterative)") do
    trie = Trie.new
    dictionary.each do |word|
      trie.build(word)
    end
  end
  benchmark.report("build (recursive)") do
    trie = Trie.new
    dictionary.each do |word|
      trie.build2(word)
    end
  end
end

Benchmark.bm(15) do |benchmark|
  benchmark.report("include (iterative)") do
    10000.times { trie.include?("apple") }
  end
  benchmark.report("include (recursive)") do
    10000.times { trie.include2?("apple") }
  end
end

Benchmark.bm(15) do |benchmark|
  benchmark.report("to_a (iterative)") do
    trie.to_a2
  end
  benchmark.report("to_a (recursive)") do
    trie.to_a
  end
end   

# /usr/share/dict/words has 235886 words.
#
#                     user     system      total        real
# build (iterative)  4.010000   0.080000   4.090000 (  4.084111)
# build (recursive)  4.600000   0.140000   4.740000 (  4.730131)
#
#                      user     system      total        real
# include (iterative)  0.040000   0.000000   0.040000 (  0.041925)
# include (recursive)  0.060000   0.000000   0.060000 (  0.056116)   
#
#                      user     system      total        real
# to_a (iterative)  1.370000   0.050000   1.420000 (  1.500043)
# to_a (recursive)  1.190000   0.010000   1.200000 (  1.283220)   

recursive.rb

def build2(string, node = @root)
  node[:end] = true and return if string.size == 0
  char = string[0]
  node[char] ||= {}
  node = node[char]
  build2(string[1..-1], node)
end

def include2?(word, node = @root)
  return false if node.nil?
  return true if node[:end] and word.empty?
  char = word[0]
  node = node[char]
  include2?(word[1..-1], node])
end

def to_a2(node = @root)
  stack = [].push(["", node])
  array = []
  while(!stack.empty?) do
    prefix, node = stack.pop
    node.each do |key, value|
      key == :end ? array << prefix : stack.push([prefix + key, value])
    end
  end

  array
end

trie.rb

class Trie

  def initialize
    @root = {}
  end

  def build(string)
    node = @root
    string.chars.each do |char|
      node[char] ||= {}
      node = node[char]
    end
    
    node[:end] = true
  end

  def include?(word)
    node = @root
    word.chars.each do |char|
      return false if node.nil?
      node = node[char]
    end
    
    !!node and node[:end]
  end

  def to_a(node = @root, prefix = "", array = [])
    return array if node.nil?
    node.each do |key, value|
      key == :end ? array << prefix : to_a(value, prefix + key, array)
    end
    
    array
  end

  def prefixed(prefix, node = @root)
    prefix.chars.each do |char|
      return [] unless node[char]
      node = node[char]
    end
    
    to_a(node).map { |suffix| prefix + suffix }
  end

end