Class Containers::Trie

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

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 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
17:   def initialize
18:     @root = nil
19:   end

Public instance methods

[] (key)

Alias for get

[]= (key, value)

Alias for push

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
57:   def get(key)
58:     key = key.to_s
59:     return nil if key.empty?
60:     node = get_recursive(@root, key, 0)
61:     node ? node.last : nil
62:   end
get_recursive (node, string, index)

Returns [char, value] if found

[show source]
     # File lib/containers/trie.rb, line 169
169:   def get_recursive(node, string, index)
170:     return nil if node.nil?
171:     char = string[index]
172:     if (char < node.char)
173:       return get_recursive(node.left, string, index)
174:     elsif (char > node.char)
175:       return get_recursive(node.right, string, index)
176:     elsif (index < string.length-1) # We're not at the end of the input string; add next char
177:       return get_recursive(node.mid, string, index+1)
178:     else
179:       return node.last? ? [node.char, node.value] : nil
180:     end
181:   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
44:   def has_key?(key)
45:     key = key.to_s
46:     return false if key.empty?
47:     !(get_recursive(@root, key, 0).nil?)
48:   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
77:   def longest_prefix(string)
78:     string = string.to_s
79:     return nil if string.empty?
80:     len = prefix_recursive(@root, string, 0)
81:     string[0...len]
82:   end
prefix_recursive (node, string, index)
[show source]
     # File lib/containers/trie.rb, line 136
136:   def prefix_recursive(node, string, index)
137:     return 0 if node.nil? || index == string.length
138:     len = 0
139:     rec_len = 0
140:     char = string[index]
141:     if (char < node.char)
142:       rec_len = prefix_recursive(node.left, string, index)
143:     elsif (char > node.char)
144:       rec_len = prefix_recursive(node.right, string, index)
145:     else
146:       len = index+1 if node.last?
147:       rec_len = prefix_recursive(node.mid, string, index+1)
148:     end
149:     len > rec_len ? len : rec_len
150:   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
32:   def push(key, value)
33:     key = key.to_s
34:     return nil if key.empty?
35:     @root = push_recursive(@root, key, 0, value)
36:     value
37:   end
push_recursive (node, string, index, value)
[show source]
     # File lib/containers/trie.rb, line 152
152:   def push_recursive(node, string, index, value)
153:     char = string[index]
154:     node = Node.new(char, value) if node.nil?
155:     if (char < node.char)
156:       node.left = push_recursive(node.left, string, index, value)
157:     elsif (char > node.char)
158:       node.right = push_recursive(node.right, string, index, value)
159:     elsif (index < string.length-1) # We're not at the end of the input string; add next char
160:       node.mid = push_recursive(node.mid, string, index+1, value)
161:     else
162:       node.end = true
163:       node.value = value
164:     end
165:     node
166:   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
 96:   def wildcard(string)
 97:     string = string.to_s
 98:     return nil if string.empty?
 99:     ary = [] 
100:     ary << wildcard_recursive(@root, string, 0, "")
101:     ary.flatten.compact.sort
102:   end
wildcard_recursive (node, string, index, prefix)
[show source]
     # File lib/containers/trie.rb, line 119
119:   def wildcard_recursive(node, string, index, prefix)
120:     return nil if node.nil? || index == string.length
121:     arr = []
122:     char = string[index]
123:     if (char.chr == "*" || char.chr == "." || char < node.char)
124:       arr << wildcard_recursive(node.left, string, index, prefix)
125:     end
126:     if (char.chr == "*" || char.chr == "." || char > node.char)
127:       arr << wildcard_recursive(node.right, string, index, prefix)
128:     end
129:     if (char.chr == "*" || char.chr == "." || char == node.char)
130:       arr << "#{prefix}#{node.char.chr}" if node.last?
131:       arr << wildcard_recursive(node.mid, string, index+1, prefix + node.char.chr)
132:     end
133:     arr
134:   end