The Encode operation allows the representation of a weighted transducer as a weighted automaton, an unweighted transducer or an unweighted automaton by considering the pair (input label, output), the pair (input label, weight) or the triple (input label, output label, weight) as a single label depending on the value of the encode flags: kEncodeLabels, kEncodeWeights or kEncodeLabels|kEncodeWeights. The encoding of each pair or triple of labels and/or weights as a unique key is performed by an EncodeMapper object.

The Decode operation takes as input an encoded FST and the corresponding EncodeMapper object and reverts the encoding.



static const uint32 kEncodeLabels      = 0x0001;
static const uint32 kEncodeWeights     = 0x0002;
static const uint32 kEncodeFlags       = 0x0003;
enum EncodeType { ENCODE = 1, DECODE = 2 };
template <class Arc> EncodeMapper<Arc>::
EncodeMapper(uint32 flags, EncodeType type);


template <class Arc>
void Encode(MutableFst<Arc> *fst, EncodeMapper<Arc> *encoder);
template <class Arc> EncodeFst<Arc>::
EncodeFst<Arc>(const Fst<Arc> &fst, EncodeMapper<Arc> *encoder); 


template <class Arc>
void Decode(MutableFst<Arc> *fst, const EncodeMapper<Arc> &encoder);
template <class Arc> DecodeFst<Arc>::
DecodeFst<Arc>(const Fst<Arc> &fst, EncodeMapper<Arc> *encoder); 


fstencode [--encode_labels] [--encode_weights] in.fst encoder out.fst
fstencode --decode in.fst encoder out.fst 




Encode(&A, &encoder):

encode_flags kEncodeLabels kEncodeWeights
$flags --encode_labels --encode_weights
result encode2.png encode3.png
encode_flags kEncodeLabels|kEncodeWeights
$flags --encode_labels --encode_weights
result encode4.png
EncodeMapper<Arc> encoder(encode_flags, ENCODE);
Encode(&A, &encoder);
EncodeFst<Arc>(A, &encoder);

fstencode $flags a.fst encoder b.fst

Decode(&A, encoder):


Decode(&A, encoder);
DecodeFst<Arc>(A, encoder);
fstencode --decode a.fst encoder b.fst


Encode, Decode:

  • Time: O(V + E)
  • Space: O(1)
where V = # of states, and E = # of transitions in the input FST.

EncodeFst, DecodeFst:

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

-- CyrilAllauzen - 27 Mar 2009

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng encode1.png r1 manage 12.2 K 2009-03-27 - 23:15 CyrilAllauzen Encode/Decode example: input FST/decoded FST
PNGpng encode2.png r1 manage 10.6 K 2009-03-27 - 23:17 CyrilAllauzen Encode/Decode example: encoding labels
PNGpng encode3.png r1 manage 13.9 K 2009-03-27 - 23:21 CyrilAllauzen Encode/Decode example: encoding weights
PNGpng encode4.png r1 manage 11.4 K 2009-03-27 - 23:19 CyrilAllauzen Encode/Decode example: encoding labels and weights
Topic revision: r5 - 2014-04-23 - 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