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

Examples

`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

Topic attachments
I Attachment History Action Size Date Who Comment
jpg arcsort1.jpg r1 manage 14.0 K 2007-06-21 - 21:43 MichaelRiley
jpg arcsort2.jpg r1 manage 14.1 K 2007-06-21 - 21:43 MichaelRiley
jpg arcsort3.jpg r1 manage 14.5 K 2007-06-21 - 21:43 MichaelRiley
Topic revision: r18 - 2018-04-26 - MichaelRiley

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback