Importance of Sorting when Composing WFSTs

For efficient composition of large WFSTs it is essential to correctly the sort the input and output labels of the components WFSTs. When performing the composition A○B, sorting A by output label and B by input label should give the fastest composition. The OpenFst documentation states that only one transducer need to be sorted and it is preferential to sort the transducer with the largest out-degree.

Below is a quick comparison of the  composition speed when the joining dimensions of the two FSTs are orders differently.

The first composition pair is a speech recognition lexicon L and a backoff n-gram language mode G.

L - Sort G - Sort Time (seconds)
None None Error
None Input 1322
Input None Error
Input Input 1399
Output None 14
Output Input 14

Error is when the OpenFst composition command detects an FST is not not sorted and terminates. Here we observe that it is essential to sort the output side of the lexicon for fast composition.

The previous LG combination was defeminized and composed with a context dependency transducer C.

C - Sort det(LG) Sort Time (seconds)
None Output 14
Output Output 14
Input Output Error
NONE Input 14
Output Input 14
Input Input 24

For these specific transducers there is not much difference but incorrectly sorting C by input gives a slower composition.