ArcSort

Description

This operation sorts the arcs in an FST per state.

At the C++ level, the sort order is determined by a function object compare of type Compare. Comparsion function objects ILabelCompare and OLabelCompare are provided by the library. In general, Compare must meet the requirements for an STL sort comparison functor. It must also have a member Properties(uint64) that specifies the known properties of the sorted FST; it takes as argument the input FST's known properties before the sort.

At the shell level, the sort order is determined by the --sort_type flag, which can have values ilabel and olabel.

Usage

template <class Arc, class Compare> 
void ArcSort(MutableFst<Arc> *fst, Compare compare);
doc
template <class Arc, class Compare> ArcSort<Arc, Compare>
ArcSortFst(const Fst<Arc> &fst, const Compare &compare);
doc
fstarcsort [--opts] a.fst out.fst
  --sort_type: ilabel (def) | olabel
 

Examples

A:

arcsort1.jpg

Input Label Sort of A:

arcsort2.jpg

ArcSort(&A, ILabelCompare<Arc>());
ArcSortFst<Arc, ILabelCompare<Arc> >(A, ILabelCompare<Arc>());
fstarcsort --sort_type=ilabel a.fst out.fst

Output Label Sort of A:

arcsort3.jpg

ArcSort(&A, OLabelCompare<Arc>());
ArcSortFst<Arc, OLabelCompare<Arc> >(A, OLabelCompare<Arc>());
fstarcsort --sort_type=olabel a.fst out.fst

Complexity

ArcSort:

  • Time: O(V D log D))
  • Space: O(D)
where V = # of states and D = maximum out-degree.

ArcSortFst:

  • Time: O(v d log d)
  • Space: O(d)
where v = # of states visited, d = maximum out-degree of the states visited. Constant time and space to visit an input state or arc is assumed and exclusive of caching.

-- MichaelRiley - 15 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg arcsort1.jpg r1 manage 14.0 K 2007-06-21 - 21:43 MichaelRiley  
JPEGjpg arcsort2.jpg r1 manage 14.1 K 2007-06-21 - 21:43 MichaelRiley  
JPEGjpg arcsort3.jpg r1 manage 14.5 K 2007-06-21 - 21:43 MichaelRiley  
Topic revision: r17 - 2017-02-15 - KyleGorman
 
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