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 (v_{0},
y_{2}y_{1}). Weights are expressed as 4tuples 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_{0}w_{1}w_{2}x) = tri(w_{0}w_{1}w_{2}) + tri(w_{1}w_{2}x).
The initial weight is defined as
.
Weights are updated as follows:

(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
20000710