% viterbi(mu,A,E,X) uses the Viterbi algorithm to find the most likely hidden state sequence associated with the data in (matrix) X

function [Pi] = viterbi(mu,A,E,X)

m = length(mu);                        % number of hidden states
n = length(X(1,:));                    % number of observed values

v = zeros(m,n+1);                      % place to store probabilities
                                       % row is hidden state
                                       % column is observation number

warning off
v(:,1) = log(mu');                     % log of initial probabilities
LA = log(A);                           % replace probabilities by logarithms
LE = log(E);                           % replace probabilities by logarithms
warning on

for i=2:n,                             % loop through all observations
  [ma,j] = max(v(:,i-1)*ones(1,m) + LA); % find most likely previous states
  v(:,i) = ma' + sum(LE(:,X(:,i)),2);  % add emission probs over replications
  point(:,i) = j';                     % points back to most likely state
end

[ma,j] = max(v(:,n));                  % find the most likely last hid. state
Pi(n) = j;                             % use this for the end of Pi

for i=n:-1:2,
  Pi(i-1) = point(Pi(i),i);            % look back to find most likely h states
end

if length(v(1,:)) < 8,
  exp(v)
end