PruneDoc < FST

FST Web>FstQuickTour>PruneDoc (2018-04-27, MichaelRiley) (raw view)

---+ Prune

---++ Description

This operation deletes states and arcs in the input FST that do not belong to a successful path whose weight is no more (w.r.t the natural the natural semiring order) than the threshold _t_ &otimes;-times the weight of the shortest path in the input FST.  

Weights need to be commutative and have the path property.
Both destructive and constructive implementations are available.

---++ Usage

|<verbatim>
template <class Arc>
void Prune(MutableFst<Arc> *fst, typename Arc::Weight threshold);
</verbatim>| 
|<verbatim>
template <class Arc>
void Prune(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, typename Arc::Weight threshold);
</verbatim>| 
|<verbatim>
fstprune [--opts] in.fst out.fst
    --weight: type = string, default = ""
      Weight parameter
</verbatim> |

---+++ =A:=

%ATTACHURL%/prune1.jpg

---+++ =Prune of A with threshold 3:=

%ATTACHURL%/prune2.jpg

<verbatim>
Prune(&A, 3);
Prune(A, &B, 3);
fstprune --weight=3 a.fst out.fst
</verbatim>
---++ Complexity

=Prune:=
   * Time: _O(V log V + E)_
   * Space: _O(V + E)_
where _V_ = # of states and _E_ = # of arcs.



-- Main.CyrilAllauzen - 05 Jul 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	prune1.jpg	r1	manage	9.4 K	2007-07-09 - 21:05	CyrilAllauzen	prune input example
jpg	prune2.jpg	r1	manage	8.8 K	2007-07-09 - 21:06	CyrilAllauzen

Topic revision: r5 - 2018-04-27 - MichaelRiley