Module compact 

Collapsing a lattice’s alignments, so each word sequence appears once.

The lattice a decoder produces has one arc per frame. A word that took eight frames to say is eight arcs, and every way of placing its boundaries is a separate path, so the same sentence comes back dozens of times, differing only in where the words were cut. n-best over that is not n sentences, and rescoring it does the same work over and over.

A compact lattice has one arc per word, with the frames it spanned moved into the weight (CompactLatticeWeight). Once they are in the weight, ordinary determinization over words does the collapsing: two arcs for the same word merge, and ⊕ keeps the better alignment instead of both.

Upstream says the same thing, and says why gallic will not do (fstext/determinize-lattice.h):

We determinize this using acceptor determinization with epsilon removal. […] CompactLatticeWeightTpl has a special kind of semiring where we always take the string corresponding to the best cost […] and discard the other. […] We couldn’t use the Gallic weight for this, or it would die as soon as it detected that the input FST was non-functional.

A lattice is exactly that non-functional transducer: one word sequence, many alignments.

What the algorithm needs beyond the semiring is the right common divisor. Determinization normalises each subset by dividing out what its members share, and for this weight that is the better cost together with the longest common prefix of the alignments, rather than ⊕, whose alignment belongs to one member and divides none of the others. That is the one piece CompactLatticeCommonDivisor supplies; the rest is sicada’s own determinize_fsa, which already takes a divisor because OpenFst’s does.

Kaldi writes its own determinizer instead, to prune as it goes and to keep the alignments in a shared trie rather than copying them. Neither is here. What is here is the outer half of the same idea: determinize_lattice_pruned narrows the lattice and tries again when determinization runs away, which is what Kaldi’s wrapper does around its own. That much matters, because a bare CTC topology constrains nothing, so a thousand-frame lattice has astronomically many symbol sequences inside any generous beam, and determinizing it whole does not finish.

Structs

CompactLatticeCommonDivisor

What the members of a determinized subset share.

DeterminizeLatticeOptions

What determinize_lattice may be asked to do differently.

PrunedDeterminizeOptions

What determinize_lattice_pruned may be asked to do differently.

PrunedLattice

A collapsed lattice, and the beam it took to get one.

Functions

determinize_lattice

Rewrites lattice so that each word sequence appears once, with its best alignment.

determinize_lattice_pruned

As determinize_lattice, narrowing the lattice and trying again when an attempt runs past max_states.

to_compact

Moves each arc’s input label into its weight, leaving the words on the arcs.

Type Aliases

CompactLattice

A lattice with one arc per word, for a decoding graph over A.