Class: Containers::Trie
- Inherits:
-
Object
- Object
- Containers::Trie
- 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
-
#get(key) ⇒ Object
(also: #[])
Returns the value of the desired key, or nil if the key doesn’t exist.
-
#get_recursive(node, string, index) ⇒ Object
Returns [char, value] if found.
-
#has_key?(key) ⇒ Boolean
Returns true if the key is contained in the Trie.
-
#initialize ⇒ Trie
constructor
Create a new, empty Trie.
-
#longest_prefix(string) ⇒ Object
Returns the longest key that has a prefix in common with the parameter string.
- #prefix_recursive(node, string, index) ⇒ Object
-
#push(key, value) ⇒ Object
(also: #[]=)
Adds a key, value pair to the Trie, and returns the value if successful.
- #push_recursive(node, string, index, value) ⇒ Object
-
#wildcard(string) ⇒ Object
Returns a sorted array containing strings that match the parameter string.
- #wildcard_recursive(node, string, index, prefix) ⇒ Object
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
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 |