Class: TrieMatcher

Inherits:
Object
  • Object
show all
Defined in:
lib/trie_matcher.rb,
lib/trie_matcher/version.rb

Overview

Trie implementation that acts as a weak mapping

Values can be stored for a given prefix, and are returned for the longest prefix. Lookup searches based on a fixed prefix size. This can cause extra memory use and performance degredation on saturated tries with many lexemes.

Defined Under Namespace

Classes: PatternMatcher

Constant Summary collapse

VERSION = 
"1.3.1"

Instance Method Summary collapse

Constructor Details

#initialize ⇒ TrieMatcher

Build an empty trie



9
10
11
 
# File 'lib/trie_matcher.rb', line 9

def initialize
  @root = { nodes: {}, value: nil, key_length: nil }
end

Instance Method Details

#[](prefix) ⇒ Object

Perform a prefix search. Will return the value associated with the longest prefix

Parameters:

  • prefix (String) —

    what to check for a prefix in

Returns:

  • (Object) —

    the value associated with the longest matching prefix in this trie



34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/trie_matcher.rb', line 34

def [](prefix)
  current = @root
  current_prefix = prefix

  while !current.nil? && current_prefix != ""
    previous = current
    current, current_prefix = next_node(current, current_prefix)
  end

  return current[:value] if current
  return previous[:value]
end

#[]=(prefix, value) ⇒ Object

Store a prefix in the trie, and associate a value with it

Parameters:

  • prefix (String)
  • value (Object) —

    a value to return if prefix is the longest prefix on lookup

Returns:

  • (Object) —

    the value that was set



18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/trie_matcher.rb', line 18

def []=(prefix, value)
  current = @root
  current_prefix = prefix

  while current_prefix != ""
    current, current_prefix = find_canididate_insertion_node(current, current_prefix)
  end

  current[:value] = value
  return value
end

#match(prefix) ⇒ <Object>

Perform a prefix search, and return all values in the trie that have this prefix

Parameters:

  • prefix (String) —

    the prefix to search the trie with

Returns:

  • (<Object>) —

    the values that start with the given prefix



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/trie_matcher.rb', line 68

def match(prefix)
  result = []
  current = @root
  current_prefix = prefix

  while current != nil && current_prefix != ""
    previous, previous_prefix = current, current_prefix
    current, current_prefix = next_node(current, current_prefix)
  end

  unless current
    if current_prefix
      return []
    else
      next_nodes = previous[:nodes].select { |prefix, node| prefix.start_with?(previous_prefix) }.values
    end
  else
    next_nodes = [current]
  end

  until next_nodes.empty?
    current = next_nodes.pop
    result << current[:value]
    current[:nodes].each { |prefix, node| next_nodes.push(node) }
  end

  return result.compact
end

#set_if_nil(word, value) ⇒ Object

Set a value in the trie if it isn’t null. Can be used to initialize collections as values

Parameters:

  • word (String) —

    The word to set the value for

  • value (Object) —

    the value to set, if the value for the word is nil

Returns:

  • (Object) —

    the value associated with the word



52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/trie_matcher.rb', line 52

def set_if_nil(word, value)
  current = @root
  current_prefix = word

  while current_prefix != ""
    current, current_prefix = find_canididate_insertion_node(current, current_prefix)
  end

  current[:value] ||= value
  return current[:value]
end