%%% Probabilistic CYK Algorithm
%%% see Jurafsky & Martin, Figure 12.3, corrected version



/*
lexicon representation

lex(Word, A, Prob)

A --> Word
*/

/*
rule representation
A --> B C
% optimized representation for first argument indexing on B
rule(B, C, A, Prob) 
*/

cyk(Words,S,Prob) :-
	build_chart(Words,NumWords),
	edge(1,NumWords,S,Prob).

:- dynamic edge/4.

build_chart(Words, NumWords) :-
	retractall(edge(_,_,_,_)),
	init_chart(Words, NumWords),
	induct_chart(NumWords).

init_chart(Words,NumWords) :-
	init_chart(Words, 1, NumWords).

init_chart([],Accu,NumWords) :-
	NumWords is Accu -1.
init_chart([Word|Words],Accu,NumWords) :-
	store_lexical_probabilities(Word, Accu),
	Next is Accu + 1,
	init_chart(Words, Next, NumWords).


induct_chart(NumWords) :-
	from_to(2, NumWords, Span),
	   Loop2End is NumWords - Span + 1,
	   from_to(1,Loop2End,Begin),
	      End is Begin + Span - 1,
		  from_to(Begin, End-1, M),
		     store_phrasal_probabilities(Begin,M,End).
induct_chart(_).

store_phrasal_probabilities(Begin, M, End) :-
	edge(Begin, M, B, BProb),
	SuccM is M + 1,
	rule(B, C, A, AProb),
	edge(SuccM, End, C, CProb),
	Prob is BProb * CProb * AProb,
	(
	  (edge(Begin, End, A, OldProb),
	  Prob >= OldProb,
	  retract(edge(Begin, End, A, OldProb)))
	->
	  assertz(edge(Begin, End, A, Prob))
	;
	  assertz(edge(Begin, End, A, Prob))
	),

	fail.



store_lexical_probabilities(Word, I) :-
	lex(Word, Cat, Prob),
	assertz(edge(I, I, Cat, Prob)),
	fail.
store_lexical_probabilities(_,_).



from_to(From, To, From) :-
	From =< To.

from_to(From, To, Now) :-
	From < To,
	NewFrom is From + 1,
	from_to(NewFrom,To,Now).
		  
	

	
