FST Weights
A semiring is specified by two binary operations
Plus(x, y)
and
Times(x, y)
and
two designated elements
Zero
and
One
with the following properties:
-
Plus
: associative, commutative, and has Zero
as its identity.
-
Times
: associative and has identity One
, distributes w.r.t. Plus
, and has Zero
as an annihilator: Times(Zero(), a) = Times(a, Zero()) = Zero().
A left semiring distributes on the left; a right semiring is similarly defined.
A
Weight
class is required to be (at least) a left or right semiring.
In addition, the following should be defined for a
Weight
:
-
Member
: predicate on set membership.
-
>>
: reads weight.
-
<<
: prints weight.
-
Weight(const string &)
: reads from byte array.
-
Data(string *)
: writes to byte array.
-
Hash
: maps weight to ssize_t.
-
ApproxEqual
: approximate equality (for inexact weights)
-
Quantize
: quantizes wrt delta (for inexact weights)
-
Divide
: ∀ a,b,c
s.t. Times(a, b) = c
⇒ b = Divide(c, a, DIVIDE_LEFT)
if a left semiring and b.Member()
⇒ a = Divide(c, b, DIVIDE_RIGHT)
if a right semiring and a.Member()
⇒ b = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT)
if a commutative semiring and b.Member()
-
ReverseWeight
: the type of the corresponding reverse weight. Typically the same type as Weight
for a (both left and right) semiring. For the left string semiring, it is the right string semiring.
-
Reverse
: a mapping from Weight
to ReverseWeight s.t.
⇒ Reverse(Reverse(a)) = a
⇒ Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
⇒ Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
Typically the identity mapping in a (both left and right) semiring. In the left string semiring, it maps to the reverse string in the right string semiring.
-
Properties
: specifies properties that hold:
-
LeftSemiring
: indicates weights form a left semiring
-
RightSemiring
: indicates weights form a right semiring
-
Commutative
: ∀ a,b
: Times(a, b) = Times(b, a)
-
Idempotent
: ∀ a
: Plus(a, a) = a
.
-
Path
: ∀ a, b
: Plus(a, b) = a
or Plus(a, b) = b.
--
MichaelRiley - 25 May 2007