Example: nlp_speech_trigram method.

The start state of the graph search now is the vertex (v₀, y₂y₁). Weights are expressed as 4-tuples by extending the triples of the nlp_speech method with a fourth component expressing trigram weights. These trigram weights are expressed using negative logarithms of (estimates of) probabilities. Let tri be the function which returns for a given sequence of three words this number. Moreover, the definition of this function is extended for longer sequences of words in the obvious way by defining tri(w₀w₁w₂x) = tri(w₀w₁w₂) + tri(w₁w₂x).

The initial weight is defined as $\mbox{\it ini\/}=\langle 0,0,0,0\rangle$. Weights are updated as follows:

$$\small\begin{minipage}[t]{.9\textwidth}\normalsize\begin{flus... ...edges}\\ \end{array}\right. $\ \end{flushleft} \end{minipage}$$ (36)

Finally, we define an ordering on such tuples. The function $\mbox{\it total}$ is defined on tuples as follows. Here $k_{\mbox{\scriptsize nlp}}$ and $k_{\mbox{\scriptsize wg}}$ are constants.

$$\mbox{\it total\/}(\langle c_1, c_2, c_3, c_4\rangle) = c_4... ...{\scriptsize nlp}}*(c_1+c_2) + k_{\mbox{\scriptsize wg}}*c_3.$$ (37)

We then define the ordering as:

$$\langle c_1, c_2, c_3, c_4\rangle \prec \langle c'_1, c'_2, ... ...) < \mbox{\it total\/}(\langle c'_1, c'_2, c'_3, c'_4\rangle).$$ (38)