Difference: RmEpsilonDoc (13 vs. 14)

Revision 142018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

RmEpsilon

Description

This operation removes epsilon-transitions (when both the input and output label are an epsilon) from a transducer. The result will be an equivalent FST that has no such epsilon transitions.

Usage

|
template <class Arc>
void RmEpsilon(MutableFst<Arc> *fst); 
Changed:
<
<
| %DOX{namespacefst.html#RmEpsilon[doc]}% |
>
>
| |
 
template <class Arc> RmEpsilonFst<Arc>::
RmEpsilonFst(const Fst<Arc>& fst);
%DOX{fst::RmEpsilonFst[doc]}%
fstrmepsilon [--opts] a.fst out.fst
 --connect: Trim output (def: true)
 

Examples

A:

rmepsilon1.jpg

(TropicalWeight)

RmEpsilon of A:

rmepsilon2.jpg

RmEpsilon(&A);
RmEpsilonFst<Arc>(A);
fstrmepsilon a.fst out.fst

Complexity

RmEpsilon:
  • TIme:
    • Unweighted: O(V2 + V E)
    • Acyclic: O(V2 + V E)
    • Tropical semiring: O(V2 log V + V E)
    • General: exponential
  • Space: O(V E)
where V = # of states and E = # of arcs.

RmEpsilonFst:

  • TIme:
    • Unweighted: O(v2 + v e)
    • General: exponential
  • Space: O(v e)
where v = # of states visited, e = # of arcs visited. Constant time to visit an input state or arc is assumed and exclusive of caching.

Caveats

See here for a discussion on efficient usage.

References

-- CyrilAllauzen - 25 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183407982" name="rmepsilon2.fst" path="rmepsilon2.fst" size="109" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183407950" name="rmepsilon1.jpg" path="rmepsilon1.jpg" size="15694" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183408044" name="rmepsilon2.jpg" path="rmepsilon2.jpg" size="9259" user="Main.MichaelRiley" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback