Changes between Version 1 and Version 2 of ViterbiAlgorithm


Ignore:
Timestamp:
Nov 11, 2013, 9:51:24 AM (13 years ago)
Author:
Stefano Sabatini
Comment:

complete text, the last part was left out

Legend:

Unmodified
Added
Removed
Modified

  • ViterbiAlgorithm

    v1 v2  
    4848
    4949
    50 The Viterbi algorithm simply solves column by column. For the previous column each point has a best path and a associated
     50The Viterbi algorithm simply solves column by column. For the previous column each point has a best path and an associated
    5151score:
    5252
    … …  
    6565}}}
    6666
     67To move one column forward we just need to find the best path and associated scores for the next column here are some edges we could choose from:
     68{{{
     69    O-----5--3--O
     70     \      \8
     71      \       \
     72    O  \  1--9--O
     73        \/  \3
     74        /\     \
     75    O  /  2--1--O
     76      /     \2
     77     /        \
     78    O-----2--4--O
     79}}}
     80
     81Finding the new best paths and scores for each point of our new column is trivial given we know the previous column best paths and scores:
     82{{{
     83    O-----0-----8
     84     \
     85      \
     86    O  \  0----10
     87        \/
     88        /\
     89    O  /  0-----3
     90      /     \
     91     /        \
     92    O     0     4
     93}}}
     94
     95The Viterbi algorithm continues exactly like this column for column until the end and then just picks the path with the best score (above that would be the one with score 3).
    6796{{{#!comment
    6897Adapted from `doc/viterbi.txt`.