% Viterbi Algorithm as by Thorsten Brants(1999: p.19-20): 
% Tagging and Parsing with Cascaded Markov Modells

% comment out for quiet version
:- dynamic(verbose/0).
:- asserta(verbose).

% Viterbi algorithm
% viterbi(+Words,+Probability,+States)
% The variable delta is represented by a list of delta/3-terms.
% delta(State,AccumulatedProbabilityOfState,PreviousStates)
% PreviousStates is a list which represents in reversed order
% the path with the highest probability so far.

viterbi([W1|Words], P, Path) :-
	delta1(W1, Delta1),                           % Eq. V1            
	induct_delta(Words, Delta1, DeltaT),          % Eq. V2
	best_path(DeltaT, P, Path).                   % Eq. V3


% Initialization of Delta (Equation V1)
% delta1(FirstWord, Delta1)

delta1(W1, Delta) :-
	findall(delta(Q,P,[]), (a(s0, Q, P1), b(Q, W1, P2), P is P1*P2), Delta),
	(verbose -> verbose_delta(Delta) ;true ).

% Induction of Delta (Equation V2)
% induct_delta(Words, Delta_t, Delta_T)
% Compute recursively the variable delta_t+1 from delta_t

induct_delta([], Delta, Delta_T):-
	findall(
		delta(se,P,[S_Bar|Path]),
		(
			member(delta(S_Bar,P_S_Bar,Path), Delta),
		   	a(S_Bar, se, P2),
		    P is P_S_Bar * P2
		),
	   Delta_T),
	(verbose-> verbose_delta(Delta_T);true ).

induct_delta([W_t|Words], Delta, Delta_T) :-
	findall(delta(Q,P_Q,MaxPath),
			(
			  s(Q),
			  findall(P1-[S_Bar|Path],
					  (
						member(delta(S_Bar,P_S_Bar,Path), Delta),
						a(S_Bar, Q, P2),
						P1 is P_S_Bar * P2
					  ),
					  Pairs
		 	),
		
		 	max_key(Pairs, P3-MaxPath),
		    b(Q, W_t, P_W_t_Q),
			P_Q is P_W_t_Q * P3		   
		),
	   Delta_t_plus_1
	),
	(verbose ->verbose_delta(Delta_t_plus_1);true),
	induct_delta(Words, Delta_t_plus_1, Delta_T).

% Compute the path with the highest probability from Delta_T
% best_path(+Delta_T,-Probability,-Path)

best_path(DeltaT, P, Path) :-
	findall(P-RevPath, member(delta(se,P,RevPath),DeltaT),Pairs),
	max_key(Pairs, P-RevPath),
	reverse(RevPath, Path).


% From a list of Key-Value pairs select the one with the maximal key
% Key must be an arithmetic term

max_key([First|Rest],Max) :-
	max_key_accu(Rest, First, Max).
max_key_accu([],Max,Max).
max_key_accu([Num1-Val1|Rest],Num2-Val2, Max) :-
	( Num1 > Num2
	->	max_key_accu(Rest, Num1-Val1,Max)
	;	max_key_accu(Rest, Num2-Val2, Max)
	).

verbose_delta([]).
verbose_delta([D1|Ds]):-
	D1 = delta(_Q,_P_Q,Path),
	length(Path,Step0),
	Step is Step0+1,
	verbose_delta([D1|Ds],Step).
verbose_delta([],_Step).
verbose_delta([delta(Q,P_Q,Path)|Ds],Step):-
	(Path == [] -> From = s0;Path= [From|_]),
	format('Delta Step ~d: In state "~p" coming from "~p" with probability ~f.~N' ,[Step,Q,From,P_Q]),
	verbose_delta(Ds,Step).

% member/2
:- ensure_loaded(library(lists)).

