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 identiy 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: for all 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 commatative 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: for all a,b: Times(a, b) = Times(b, a)
    • Idempotent: for all a: Plus(a, a) = a.
    • Path: for all a, b: Plus(a, b) = a or Plus(a, b) = b.

-- MichaelRiley - 25 May 2007

Edit | Attach | Watch | Print version | History: r15 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r2 - 2007-05-26 - 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