class Containers::Trie

  1. lib/containers/trie.rb
Parent: Containers

A Trie is a data structure that stores key value pairs in a tree-like fashion. It allows O(m) lookup speed, where m is the length of the key searched, and has no chance of collisions, unlike hash tables. Because of its nature, search misses are quickly detected.

Tries are often used for longest prefix algorithms, wildcard matching, and can be used to implement a radix sort.

This implemention is based on a Ternary Search Tree.

Public Instance Aliases

[] -> get
[]= -> push

Public Class methods

new ()

Create a new, empty Trie.

t = Containers::Trie.new
t["hello"] = "world"
t["hello"] #=> "world"
[show source]
# File lib/containers/trie.rb, line 17
def initialize
  @root = nil
end

Public Instance methods

get (key)

Returns the value of the desired key, or nil if the key doesn’t exist.

Complexity: O(m) worst case

t = Containers::Trie.new
t.get("hello") = "world"
t.get("non-existant") #=> nil
[show source]
# File lib/containers/trie.rb, line 57
def get(key)
  key = key.to_s
  return nil if key.empty?
  node = get_recursive(@root, key, 0)
  node ? node.last : nil
end
get_recursive (node, string, index)

Returns [char, value] if found

[show source]
# File lib/containers/trie.rb, line 169
def get_recursive(node, string, index)
  return nil if node.nil?
  char = string[index]
  if (char < node.char)
    return get_recursive(node.left, string, index)
  elsif (char > node.char)
    return get_recursive(node.right, string, index)
  elsif (index < string.length-1) # We're not at the end of the input string; add next char
    return get_recursive(node.mid, string, index+1)
  else
    return node.last? ? [node.char, node.value] : nil
  end
end
has_key? (key)

Returns true if the key is contained in the Trie.

Complexity: O(m) worst case

[show source]
# File lib/containers/trie.rb, line 44
def has_key?(key)
  key = key.to_s
  return false if key.empty?
  !(get_recursive(@root, key, 0).nil?)
end
longest_prefix (string)

Returns the longest key that has a prefix in common with the parameter string. If no match is found, the blank string “” is returned.

Complexity: O(m) worst case

t = Containers::Trie.new
t.push("Hello", "World")
t.push("Hello, brother", "World")
t.push("Hello, bob", "World")
t.longest_prefix("Hello, brandon") #=> "Hello"
t.longest_prefix("Hel") #=> ""
t.longest_prefix("Hello") #=> "Hello"
[show source]
# File lib/containers/trie.rb, line 77
def longest_prefix(string)
  string = string.to_s
  return nil if string.empty?
  len = prefix_recursive(@root, string, 0)
  string[0...len]
end
prefix_recursive (node, string, index)
[show source]
# File lib/containers/trie.rb, line 136
def prefix_recursive(node, string, index)
  return 0 if node.nil? || index == string.length
  len = 0
  rec_len = 0
  char = string[index]
  if (char < node.char)
    rec_len = prefix_recursive(node.left, string, index)
  elsif (char > node.char)
    rec_len = prefix_recursive(node.right, string, index)
  else
    len = index+1 if node.last?
    rec_len = prefix_recursive(node.mid, string, index+1)
  end
  len > rec_len ? len : rec_len
end
push (key, value)

Adds a key, value pair to the Trie, and returns the value if successful. The to_s method is called on the parameter to turn it into a string.

Complexity: O(m)

t = Containers::Trie.new
t["hello"] = "world"
t.push("hello", "world") # does the same thing
t["hello"] #=> "world"
t[1] = 1
t[1] #=> 1
[show source]
# File lib/containers/trie.rb, line 32
def push(key, value)
  key = key.to_s
  return nil if key.empty?
  @root = push_recursive(@root, key, 0, value)
  value
end
push_recursive (node, string, index, value)
[show source]
# File lib/containers/trie.rb, line 152
def push_recursive(node, string, index, value)
  char = string[index]
  node = Node.new(char, value) if node.nil?
  if (char < node.char)
    node.left = push_recursive(node.left, string, index, value)
  elsif (char > node.char)
    node.right = push_recursive(node.right, string, index, value)
  elsif (index < string.length-1) # We're not at the end of the input string; add next char
    node.mid = push_recursive(node.mid, string, index+1, value)
  else
    node.end = true
    node.value = value
  end
  node
end
wildcard (string)

Returns a sorted array containing strings that match the parameter string. The wildcard characters that match any character are ‘*’ and ‘.’ If no match is found, an empty array is returned.

Complexity: O(n) worst case

t = Containers::Trie.new
t.push("Hello", "World")
t.push("Hilly", "World")
t.push("Hello, bob", "World")
t.wildcard("H*ll.") #=> ["Hello", "Hilly"]
t.wildcard("Hel") #=> []
[show source]
# File lib/containers/trie.rb, line 96
def wildcard(string)
  string = string.to_s
  return nil if string.empty?
  ary = [] 
  ary << wildcard_recursive(@root, string, 0, "")
  ary.flatten.compact.sort
end
wildcard_recursive (node, string, index, prefix)
[show source]
# File lib/containers/trie.rb, line 119
def wildcard_recursive(node, string, index, prefix)
  return nil if node.nil? || index == string.length
  arr = []
  char = string[index]
  if (char.chr == "*" || char.chr == "." || char < node.char)
    arr << wildcard_recursive(node.left, string, index, prefix)
  end
  if (char.chr == "*" || char.chr == "." || char > node.char)
    arr << wildcard_recursive(node.right, string, index, prefix)
  end
  if (char.chr == "*" || char.chr == "." || char == node.char)
    arr << "#{prefix}#{node.char.chr}" if node.last?
    arr << wildcard_recursive(node.mid, string, index+1, prefix + node.char.chr)
  end
  arr
end