1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
# Semirings for directed acyclic graphs (dags) (also directed hypergraphs),
# as described in:
# 'Dynamic Programming Algorithms in
# Semiring and Hypergraph Frameworks' (Liang Huang)
class Semiring
attr_accessor :add, :multiply, :one, :null, :convert
end
class BooleanSemiring < Semiring
def initialize
@add = Proc.new { |a,b| a||b }
@multiply = Proc.new { |a,b| a&&b }
@one = true
@null = false
@convert = Proc.new { |v| true && v!=0 }
end
end
class ViterbiSemiring < Semiring
def initialize
@add = Proc.new { |a,b| [a,b].max }
@multiply = Proc.new { |a,b| a*b }
@one = 1.0
@null = 0.0
@convert = Proc.new { |v| v }
end
end
class InsideSemiring < Semiring
def initialize
@add = Proc.new { |a,b| a+b }
@multiply = Proc.new { |a,b| a*b }
@one = 1.0
@null = 0.0
@convert = Proc.new { |v| v }
end
end
class RealSemiring < Semiring
def initialize
@add = Proc.new { |a,b| [a,b].min }
@multiply = Proc.new { |a,b| a+b }
@one = 0.0
@null = 1.0/0.0
@convert = Proc.new { |v| v }
end
end
# for longest/worst paths
class RealxSemiring < Semiring
def initialize
@add = Proc.new { |a,b| [a,b].max }
@multiply = Proc.new { |a,b| a+b }
@one = -1.0/0.0
@null = 0.0
@convert = Proc.new { |v| v }
end
end
class CountingSemiring < Semiring
def initialize
@add = Proc.new { |a,b| a+b }
@multiply = Proc.new { |a,b| a*b }
@one = 1.0
@null = 0.0
@convert = Proc.new { |v| if v!=0 then 1 else 0 end }
end
end
|
