Relabel

Description

This operation relabels the input and/or output labels of an FST. The input and/or output relabeling are specified by providing the corresponding sets of pairs (old_label, new_label) of label IDs .

When the FST has input and/or output symbol tables, the relabeling can be specified by giving new input and/or output symbol tables. The operation then modifies the label IDs of each arc in such a way that the symbols are preserved.

Usage

template <class Arc>
void Relabel(
    MutableFst<Arc> *fst,
    const vector<pair<typename Arc::Label, typename A::Label> >& ipairs,
    const vector<pair<typename Arc::Label, typename A::Label> >& opairs);
doc
template<class Arc>
void Relabel(
     MutableFst<Arc> *fst,
     const SymbolTable* new_isymbols,
     const SymbolTable* new_osymbols);
template <class Arc> RelabelFst<Arc>::
RelabelFst(const Fst<A>& fst,
             const vector<pair<Label, Label> >& ipairs,
             const vector<pair<Label, Label> >& opairs);
doc
template <class Arc> RelabelFst<Arc>::
RelabelFst(const Fst<A>& fst,
             const SymbolTable* new_isymbols,
             const SymbolTable* new_osymbols)
fstrelabel [--relabel_ipairs=$ipairs] [--relabel_opairs=$opairs] in.fst out.fst 
fstrelabel [--relabel_isymbols=$isyms] [--relabel_osymbols=$osyms] in.fst out.fst 

Examples

A:

S1
eps 0
a 1
b 2
c 3
d 4
f 5
g 6

A
relabel.png relabel_s1.png

Relabel(&A):

S2
eps 0
a 6
b 5
c 4
d 3
f 2
g 1

B
relabel.png relabel_s2.png

Relabel(&A, S2, S2);
RelabelFst<Arc> B(A, S2, S2);

fstrelabel  --relabel_isymbols=s2 --relabel_osymbols=s2 a.fst b.fst

P
0 0
1 6
2 5
3 4
4 3
5 2
6 1

Relabel(&A, P, P);
RelabelFst<Arc> B(A, P, P);

fstrelabel --relabel_ipairs=p --relabel_opairs=p a.fst b.fst

Complexity

Relabel

  • Time: O(V + E + Si + So)
  • Space: O(Si + So)
where V = # of states, E = # of arcs of the input FST, Si = # of input symbols and So = # of output symbols.

RelabelFst

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

-- CyrilAllauzen - 03 Mar 2009

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng relabel.png r1 manage 10.9 K 2009-03-25 - 22:38 CyrilAllauzen Relabel example: fst A
PNGpng relabel_s1.png r3 r2 r1 manage 10.6 K 2009-03-25 - 23:27 CyrilAllauzen Relabel example: fst A with integer labels
PNGpng relabel_s2.png r2 r1 manage 10.7 K 2009-03-25 - 23:27 CyrilAllauzen Relabel example: fst B with integer labels
Topic revision: r4 - 2009-03-26 - CyrilAllauzen
 
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