Module: HG

Defined in:
lib/zipf/hg.rb

Defined Under Namespace

Classes: Hyperedge, Hypergraph, Node

Class Method Summary collapse

Class Method Details

.all_paths(hypergraph, root, semiring = ViterbiSemiring.new) ⇒ Object 



154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
# File 'lib/zipf/hg.rb', line 154

def HG::all_paths hypergraph, root, semiring=ViterbiSemiring.new
  toposorted = topological_sort hypergraph.nodes
  paths = [[]]
  toposorted.each { |n|
    next if n.incoming.empty?
    new_paths = []
    while !paths.empty?
      p = paths.pop
      n.incoming.each { |e|
        new_paths << p+[e]
      }
    end
    paths = new_paths
  }
  return paths
end

.init(nodes, semiring, root) ⇒ Object 



81
82
83
84
 
# File 'lib/zipf/hg.rb', line 81

def HG::init nodes, semiring, root
  nodes.each { |n| n.score=semiring.null }
  root.score = semiring.one
end

.read_hypergraph_from_json(fn, semiring = RealSemiring.new, log_weights = false) ⇒ Object 



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
# File 'lib/zipf/hg.rb', line 121

def HG::read_hypergraph_from_json fn, semiring=RealSemiring.new, log_weights=false
  nodes = []
  edges = []
  nodes_by_label = {}
  nodes_by_index = []
  h = JSON.parse File.new(fn).read
  w = SparseVector.from_h h['weights']
  h['nodes'].each { |i|
    n = Node.new i['label'], i['cat']
    nodes << n
    nodes_by_label[n.label] = n
    nodes_by_index << n
  }
  h['edges'].each { |i|
    e = Hyperedge.new(nodes_by_label[i['head']], \
                      i['tails'].map{|j| nodes_by_label[j]}.to_a, \
                      semiring.convert.call(i['weight'].to_f), \
                      {})
    e.f = SparseVector.from_h i['f']
    if log_weights
      e.weight = Math.exp(w.dot(e.f))
    else
      e.weight = w.dot(e.f)
    end
    e.tails.each { |m|
      m.outgoing << e
    }
    e.head.incoming << e
    edges << e
  }
  return Hypergraph.new(nodes, edges), nodes_by_label, nodes_by_index
end

.topological_sort(nodes) ⇒ Object 



67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/zipf/hg.rb', line 67

def HG::topological_sort nodes
  sorted = []
  s = nodes.reject { |n| !n.incoming.empty? }
  while !s.empty?
    sorted << s.shift
    sorted.last.outgoing.each { |e|
      next if e.marked?
      e.mark += 1
      s << e.head if e.head.incoming.reject{ |f| f.mark==f.arity }.empty?
    }
  end
  return sorted
end

.viterbi(hypergraph, root, semiring = ViterbiSemiring.new) ⇒ Object 



86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/zipf/hg.rb', line 86

def HG::viterbi hypergraph, root, semiring=ViterbiSemiring.new
  toposorted = topological_sort hypergraph.nodes
  init toposorted, semiring, root
  toposorted.each { |n|
    n.incoming.each { |e|
      s = semiring.one
      e.tails.each { |m|
        s = semiring.multiply.call(s, m.score)
      }
      n.score = semiring.add.call(n.score, semiring.multiply.call(s, e.weight))
    }
  }
end

.viterbi_path(hypergraph, root, semiring = ViterbiSemiring.new) ⇒ Object 



100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/zipf/hg.rb', line 100

def HG::viterbi_path hypergraph, root, semiring=ViterbiSemiring.new
  toposorted = topological_sort hypergraph.nodes
  init toposorted, semiring, root
  best_path = []
  toposorted.each { |n|
    best_edge = nil
    n.incoming.each { |e|
      s = semiring.one
      e.tails.each { |m|
        s = semiring.multiply.call(s, m.score)
      }
      if n.score < semiring.multiply.call(s, e.weight) # ViterbiSemiring add
        best_edge = e
      end
      n.score = semiring.add.call(n.score, semiring.multiply.call(s, e.weight))
    }
    best_path << best_edge
  }
  return best_path, toposorted.last.score
end