TWiki> FST Web>FstQuickTour>ArcSortDoc (revision 14)EditAttach

# 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 comparision function object. 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); ``` [bad link?] ```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
Edit | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r14 - 2007-07-02 - 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