Encode/Decode

Description

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.

Usage

EncodeMapper

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);
doc

Encode

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

Decode

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

fstencode

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

Example

A:

encode1.png

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):

encode1.png

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

Complexity

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