Class: Containers::Trie

Inherits:
Object
  • Object
show all
Defined in:
lib/containers/trie.rb

Overview

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.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Trie

Create a new, empty Trie.

t = Containers::Trie.new
t["hello"] = "world"
t["hello"] #=> "world"



17
18
19
 
# File 'lib/containers/trie.rb', line 17

def initialize
  @root = nil
end

Instance Method Details

#get(key) ⇒ Object Also known as: []

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



57
58
59
60
61
62
 
# 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) ⇒ Object

Returns [char, value] if found



169
170
171
172
173
174
175
176
177
178
179
180
181
 
# 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) ⇒ Boolean

Returns true if the key is contained in the Trie.

Complexity: O(m) worst case

Returns:

  • (Boolean) 


44
45
46
47
48
 
# 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) ⇒ Object

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"



77
78
79
80
81
82
 
# 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) ⇒ Object 



136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# 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) ⇒ Object Also known as: []=

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



32
33
34
35
36
37
 
# 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) ⇒ Object 



152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
 
# 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) ⇒ Object

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



96
97
98
99
100
101
102
 
# 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) ⇒ Object 



119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
# 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