Class: Lernen::Algorithm::LSharp::ObservationTree

Inherits:
Object
  • Object
show all
Defined in:
lib/lernen/algorithm/lsharp/observation_tree.rb

Overview

ObservationTree is an implementation of observation tree data structure.

This data structure is used for L# algorithm.

Constant Summary collapse

Node =

Node is a node of an observation tree.

‘output` can take `nil` for the root node on learning Mealy machine.

Data.define(:output, :branch) do
  def to_s
    "#{output&.inspect}(#{branch.map { |c, n| "#{c.inspect} -> #{n}" }.join(", ")})" # steep:ignore
  end
end

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(sul, automaton_type:) ⇒ ObservationTree

: (

  System::SUL[In, Out] sul,
  automaton_type: :dfa | :mealy | :moore
) -> void



44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/lernen/algorithm/lsharp/observation_tree.rb', line 44

def initialize(sul, automaton_type:)
  @sul = sul
  @automaton_type = automaton_type

  case automaton_type
  in :dfa | :moore
    raise "MooreLikeSUL is required to learn DFA or Moore" unless sul.is_a?(System::MooreLikeSUL)
    @root = Node[sul.query_empty, {}]
  in :mealy
    @root = Node[nil, {}]
  end
end

Instance Attribute Details

#root ⇒ Object (readonly)

: Node[In, Out]



57
58
59
 
# File 'lib/lernen/algorithm/lsharp/observation_tree.rb', line 57

def root
  @root
end

Instance Method Details

#[](word) ⇒ Object

Returns a node for the given word. When the word (or its subword) is not observed, it returns ‘nil` instead.

: (Array word) -> (Node[In, Out] | nil)



63
64
65
66
67
68
69
70
 
# File 'lib/lernen/algorithm/lsharp/observation_tree.rb', line 63

def [](word)
  node = @root
  word.each do |input|
    return nil unless node.branch[input]
    node = node.branch[input]
  end
  node
end

#observed_query(word) ⇒ Object

Returns an output sequence for the given word if it is observed. If it is not, it returns ‘nil` instead.

: (Array word) -> (Array | nil)



76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/lernen/algorithm/lsharp/observation_tree.rb', line 76

def observed_query(word)
  return [@root.output] if word.empty? # steep:ignore

  node = @root
  outputs = []
  word.each do |input|
    node = node.branch[input]
    return nil unless node

    outputs << node.output
  end

  outputs
end

#query(word) ⇒ Object

Returns an output sequence for the given word. When the word is observed, it runs actual query over ‘sul`.

: (Array word) -> Array



95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/lernen/algorithm/lsharp/observation_tree.rb', line 95

def query(word)
  outputs = observed_query(word)
  return outputs if outputs

  node = @root
  inprogress_word = []
  outputs = []
  word.each do |input|
    inprogress_word << input
    output = @sul.query_last(inprogress_word)
    outputs << output
    node.branch[input] ||= Node[output, {}] # steep:ignore
    node = node.branch[input]
  end

  outputs
end