Next: Comparison with Dijkstra's algorithm Up: Complications for Ngrams Previous: Complications for Ngrams

#### Example: nlp_speech_trigram method.

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:

 (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