#!/usr/bin/perl -w use strict; my $dice_seq = '23653245666'; my @obs_list = split(//,$dice_seq); my %P_emission = ( 'F' => { 1 => 1/6, 2 => 1/6, 3 => 1/6, 4 => 1/6, 5 => 1/6, 6 => 1/6 }, 'L' => { 1 => 0.1, 2 => 0.1, 3 => 0.1, 4 => 0.1, 5 => 0.1, 6 => 0.5 } ); my %P_transition = ( 'FF' => 0.95, 'LL' => 0.90, 'FL' => 0.05, 'LF' => 0.10 ); my %path; my %v = ( 'F' => [1/6], 'L' => [0.1] ); my $idx = 1; foreach my $tmp_obs (@obs_list) { my $max_state = ''; my $max_state_v = 0; foreach my $state2 qw(F L) { my ($max_v, $max_prev_state, $max_path) = (0,'X','XX'); foreach my $state1 qw(F L) { my $tmp_trans = $state1.$state2; my $tmp_v = $P_emission{$state2}->{$tmp_obs} * $P_transition{$tmp_trans} * $v{$state1}->[$idx-1]; print sprintf("[%d]%s -> %s: %.3f * %.2f * %.5e = %.5e\n", $idx, $state1, $state2, $P_emission{$state2}->{$tmp_obs}, $P_transition{$tmp_trans}, $v{$state1}->[$idx-1], $tmp_v); if( $tmp_v > $max_v ) { $max_v = $tmp_v; $max_prev_state = $state1; $max_path = $state1.$state2; } } print sprintf("MAX PATH to %s: %s, %s%d = %.5e\n", $state2, $max_path, $state2,$idx+1,$max_v); $path{$idx}->{$state2} = $max_prev_state; #push(@{$path{$state2}}, $max_path); $v{$state2}->[$idx] = $max_v; } print "\n"; $idx += 1; } ## Determine the last state my $last_state = 'X'; if( $v{'F'}->[$idx-1] > $v{'L'}->[$idx-1] ) { $last_state = 'F'; } else { $last_state = 'L'; } print "Final state: $last_state (v= $v{$last_state}->[$idx-1])\n"; my @state_seq = (); for(my $i=$idx-1;$i>0;$i--) { my $prev_state = $path{$i}->{$last_state}; push(@state_seq,$prev_state); $last_state = $prev_state; } print "\n[Output]\n"; print join("",@obs_list),"\n"; print join("",reverse @state_seq),"\n";