Changes between Version 1 and Version 2 of ViterbiAlgorithm


Ignore:
Timestamp:
Nov 11, 2013, 11:51:24 AM (3 years ago)
Author:
saste
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`.