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);
template <class Arc, class Compare> ArcSort<Arc, Compare> ArcSortFst(const Fst<Arc> &fst, const Compare &compare);
fstarcsort [--opts] a.fst out.fst --sort_type: ilabel (def) | olabel

Examples

A:

Input Label Sort of A:

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

Output Label Sort of A:

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