NGram Model Format

The following gives the encoding of all n-gram models produced by the utilities here, including those with unnormalized counts, as a cyclic weighted finite-state transducer in OpenFst format.

An n-gram is a sequence of k symbols: w₁ ... w_k. Let N be the set of n-grams in the model.

• There is a unigram state in every model, representing the empty string.
• Every proper prefix of every n-gram in N has an associated state in the model.
• The state associated with an n-gram w₁ ... w_k has a backoff transition (labeled with <epsilon>) to the state associated with its suffix w₂ ... w_k.
• An n-gram w₁ ... w_k is represented as a transition, labeled with w_k, from the state associated with its prefix w₁ ... w_k-1 to a destination state defined as follows:
  • If w₁ ... w_k is a proper prefix of an n-gram in the model, then the destination of the transition is the state associated with w₁ ... w_k
  • Otherwise, the destination of the transition is the state associated with the suffix w₂ ... w_k.
• Start and end of the sequence are not represented via transitions in the automaton or symbols in the symbol table. Rather
  • The start state of the automaton encodes the "start of sequence" n-gram prefix (commonly denoted <s>).
  • The end of the sequence (often denoted </s>) is included in the model through state final weights, i.e., for a state associated with an n-gram prefix w₁ ... w_k, the final weight of that state represents the weight of the n-gram w₁ ... w_k </s>.