Push

Description

This operation produces an equivalent transducer by pushing the weights and/or the labels towards the initial state or toward the final states.

Weight pushing

When pushing weights towards the initial state, the sum of the weight of the outgoing transitions and final weight at any non-initial state is equal to 1 in the resulting machine. When pushing weights towards the final states, the sum of the weight of the incoming transitions at any state is equal to 1.

Weight needs to be left distributive when pushing towards the initial state and right distributive when pushing towards the final states.

Label pushing

Pushing labels towards the initial state consists in minimizing at every state the length of the longest common prefix of the output labels of the outgoing paths. Pushing labels towards the final states consists in minimizing at every state the length of the longest common suffix of the output labels of the incoming paths.

Usage

const uint32 kPushWeights = 0x0001;
const uint32 kPushLabels =  0x0002;

enum ReweightType { REWEIGHT_TO_INITIAL, REWEIGHT_TO_FINAL };

template <class Arc, ReweightType rtype>
void Push(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, uint32 ptype) {
doc
fstpush [--opts] a.fst out.fst
    --to_final: type = bool, default = false
      Push/reweight to final (vs. to initial) states
    --push_labels: type = bool, default = false
      Push output labels
    --push_weights: type = bool, default = false
      Push weights
 

Examples

A:

push1.jpg

Push weights of A to initial state:

push2.jpg

Push<Arc, REWEIGHT_TO_INITIAL>(A, &B, kPushWeights);
fstpush --push_weights a.fst out.fst

Push labels of A to initial state:

push3.jpg

Push<Arc, REWEIGHT_TO_INITIAL>(A, &B, kPushLabels);
fstpush --push_labels a.fst out.fst

Push weights and labels of A to final states

push4.jpg

Push<Arc, REWEIGHT_TO_FINAL>(A, &B, kPushWeights|kPushLabels);
fstpush --push_weights --push_labels --to_final a.fst out.fst

Complexity

Push:

  • Weight pushing:
    • Time:
      • Acyclic: O(V + E)
      • Tropical semiring: O(V log V + E)
      • General: exponential
    • Space: O(V + E)
  • Label pushing:
    • Time: polynomial
    • Space: O(V2 + E)
where V = # of states and E = # of arcs.

-- CyrilAllauzen - 04 Jul 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg push1.jpg r1 manage 11.9 K 2007-07-09 - 21:29 CyrilAllauzen push input example
JPEGjpg push2.jpg r1 manage 11.7 K 2007-07-09 - 21:30 CyrilAllauzen push weight example
JPEGjpg push3.jpg r1 manage 11.9 K 2007-07-09 - 21:30 CyrilAllauzen push label example
JPEGjpg push4.jpg r1 manage 11.6 K 2007-07-09 - 21:31 CyrilAllauzen push to final example
Topic revision: r5 - 2011-12-06 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback