TWiki> FST Web>FstQuickTour>RelabelDoc (revision 3)EditAttach

Relabel

Description

Work in progress, under construction TBA

This operation relabels the input and/or output labels of an FST. The relabeling can be specified by a set of pair of integer labels.

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 interger labels of each arc in such a way that its symbolic labels 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 [bad link?]
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

Work in progress, under construction TBA

A:

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

A
relabel.png relabel_s1.png

B:

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

B
relabel.png relabel_s2.png


fstrelabel  --relabel_isymbols=s2 --relabel_osymbols=s2 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
Edit | Attach | Watch | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r3 - 2009-03-25 - CyrilAllauzen
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback