Next: Comparison with Dijkstra's algorithm
Up: Complications for Ngrams
Previous: Complications for Ngrams
The start state of the graph search now is the vertex (v0,
y2y1). 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(w0w1w2x) = tri(w0w1w2) + tri(w1w2x).
The initial weight is defined as
.
Weights are updated as follows:
![\begin{displaymath}\small\begin{minipage}[t]{.9\textwidth}\normalsize\begin{flus...
...edges}\\
\end{array}\right. $\
\end{flushleft} \end{minipage}\end{displaymath}](img110.gif) |
(36) |
Finally, we define an ordering on such tuples. The function
is defined on tuples as follows. Here
and
are constants.
 |
(37) |
We then define the ordering as:
 |
(38) |
Next: Comparison with Dijkstra's algorithm
Up: Complications for Ngrams
Previous: Complications for Ngrams
2000-07-10