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
An n-gram is a sequence of k
symbols: w1 ... wk
. 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 w1 ... wk has a backoff transition (labeled with <epsilon>) to the state associated with its suffix w2 ... wk.
- An n-gram w1 ... wk is represented as a transition, labeled with wk, from the state associated with its prefix w1 ... wk-1 to a destination state defined as follows:
- If w1 ... wk is a proper prefix of an n-gram in the model, then the destination of the transition is the state associated with w1 ... wk
- Otherwise, the destination of the transition is the state associated with the suffix w2 ... wk.
- 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 w1 ... wk, the final weight of that state represents the weight of the n-gram w1 ... wk </s>.