TWiki
>
FST Web
>
FstQuickTour
>
PushDoc
(revision 2) (raw view)
Edit
Attach
---+ 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 <span style="text-decoration:overline">1</span> 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 <span style="text-decoration:overline">1</span>. 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 |<verbatim> 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) { </verbatim>| %DOX{namespacefst.html#Push[%H%]}% | |<verbatim> 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 </verbatim> | | ---++ 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(V<sup>2</sup> + E)_ where _V_ = # of states and _E_ = # of arcs. -- Main.CyrilAllauzen - 04 Jul 2007
Edit
|
Attach
|
Watch
|
P
rint version
|
H
istory
:
r6
|
r4
<
r3
<
r2
<
r1
|
B
acklinks
|
V
iew topic
|
Raw edit
|
More topic actions...
Topic revision: r2 - 2007-07-04
-
CyrilAllauzen
FST
Log In
or
Register
FST Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
Webs
Contrib
FST
Forum
GRM
Kernel
Main
Sandbox
TWiki
Main
Copyright © 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