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.
Methods
Public Class
Public Instance
Public Class methods
Create a new, empty Trie.
t = Containers::Trie.new t["hello"] = "world" t["hello"] #=> "world"
# File lib/containers/trie.rb, line 17 def initialize @root = nil end
Public Instance methods
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
# 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
Returns [char, value] if found
# 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
Returns true if the key is contained in the Trie.
Complexity: O(m) worst case
# 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
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"
# 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
# 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
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
# 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
# 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
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") #=> []
# 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
# 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