Class: Containers::Trie

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

Overview

rdoc

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.

MIT License

Copyright (c) 2009 Kanwei Li

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

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"



39
40
41
 
# File 'lib/containers/trie.rb', line 39

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



79
80
81
82
83
84
 
# File 'lib/containers/trie.rb', line 79

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



191
192
193
194
195
196
197
198
199
200
201
202
203
 
# File 'lib/containers/trie.rb', line 191

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) 


66
67
68
69
70
 
# File 'lib/containers/trie.rb', line 66

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"



99
100
101
102
103
104
 
# File 'lib/containers/trie.rb', line 99

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 



158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/containers/trie.rb', line 158

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



54
55
56
57
58
59
 
# File 'lib/containers/trie.rb', line 54

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 



174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/containers/trie.rb', line 174

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



118
119
120
121
122
123
124
 
# File 'lib/containers/trie.rb', line 118

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 



141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
 
# File 'lib/containers/trie.rb', line 141

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