FST Weight Requirements

A semiring is specified by two binary operations ⊕ and ⊗ and two designated elements 0 and 1 with the following properties:

  • ⊕: associative, commutative, and has 0 as its identity.
  • ⊗: associative and has identity 1, distributes w.r.t. ⊕, and has 0 as an annihilator: 0 ⊗ a = a ⊗ 0 = 0.

A left semiring distributes on the left; a right semiring is similarly defined.

A Weight class must have binary functions Plus and Times and static member functions Zero() and One() and these must form (at least) a left or right semiring.

In addition, the following must be defined for a Weight:

  • Member: predicate on set membership.
  • NoWeight: static member function that returns an element that is not a set member; used to signal an error.
  • >>: reads textual representation of a weight.
  • <<: prints textual representation of a weight.
  • Read(istream &): reads binary representation of a weight.
  • Write(ostream &): writes binary representation of a weight.
  • Hash: maps weight to size_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, b'.Member() and Times(a, b') = c
    a' = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a'.Member() and Times(a', b) = c
    b' = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a commutative semiring, b'.Member() and Times(a, b') = Times(b', a) = c
  • 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: a ⊕ a = a.
    • Path: ∀ a, b: a ⊕ b = a or a ⊕ b = b.
Edit | Attach | Watch | Print version | History: r15 < r14 < r13 < r12 < r11 | Backlinks | Raw View | WYSIWYG | More topic actions
Topic revision: r15 - 2012-03-01 - MichaelRiley
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback