Declaratieve Talen/alternatiefHuffman

Deze oplossing is een alternatief, maar daarom niet beter of minder goed dan de andere oplossing. Hier werd vooral veel commentaar genoteerd.

decodeer(N,Mes,Res) :-
	decodeer(0,N,Mes,[],Res).
decodeer(N,N,[],Acc,RAcc) :-				% Uiteindelijk eindig je.
	reverse(Acc,RAcc).
decodeer(N,M,Mes,Acc,Res) :-
	length(Mes,MesLen),				% Bereken de lengte van het bericht
	numlist(1,MesLen,MesLL),			% Maak een lijst lengtes van deelverz van het bericht
	member(MesAm,MesLL),				% Haal zo'n lengte uit de lijst
	take(MesAm,Mes,MesPart),			% Neem dat aantal elementen uit het bericht
	delete(MesAm,Mes,MesRest),			% Verwijder die ook, zodat er enkel een rest is
	no_conflict(N-MesPart,Acc),			% Kijk of er geen conflict is met reeds berekende
	NAcc = [N-MesPart|Acc],				% Voeg berekende toe aan accumulator, vooraan op het einde reverse
	Nn is N+1,					% Bereken nieuwe N
	decodeer(Nn,M,MesRest,NAcc,Res).		% Decodeer rest bericht

no_conflict(_,[]).					% Je kan moeilijk conflict hebben met niets
no_conflict(MesC-MesP,[_-MesH|T]) :-
	\+ prefix(MesP,MesH),				% Check of geen prefix van elkaar
	no_conflict(MesC-MesP,T).
	
prefix(_,[]).						% Niets is pefix van alles
prefix([],_).						% Niets is pefix van alles
prefix([H|PR],[H|RR]) :-				% Controlleer of top lijst gelijk is (prefix)
	prefix(PR,RR).

take(0,_,[]).
take(N,[H|T],Res) :-
	Nn is N-1,
	take(Nn,T,TRes),
	Res = [H|TRes].
	
delete(0,A,A).
delete(N,[_|T],Res) :-
	Nn is N-1,
	delete(Nn,T,TRes),
	Res = TRes.
	
bereken([],_,0).					% Het gewicht van een lege codering is 0
bereken([Nn-Ms|Rest],Freq,Res) :-			% Neem eerste codering
	member(Nn-W,Freq),				% Zoek de frequentie
	length(Ms,MsLen),				% Bereken lengte codering
	bereken(Rest,Freq,TRes),			% Bereken rest van codering
	Res is TRes + MsLen*W.				% Resultaat is berek. rest + lengte cod. * freq-gewicht
	
beste(N,Mes,Freqs,Res) :-
	findall(Ress,decodeer(N,Mes,Ress),ResList),
	geef_beste(ResList,Freqs,Res).
	
geef_beste(ResList,Freqs,Res) :-
	bereken_alle(ResList,Freqs,BResList),
	min_list(BResList,Min),
	geef_beste(ResList,BResList,Min,Res).
	
geef_beste([HE|_],[Min|_],Min,HE).			% Verwijder 1 voor 1 tot je bij beste komt
geef_beste([_|TE],[HB|TB],Min,Res) :-
	HB > Min,
	geef_beste(TE,TB,Min,Res).
	
bereken_alle([],_,[]).					% Bereken alle coderingen a.d.h.v. frequentie
bereken_alle([H|T],Freqs,Res) :-
	bereken_alle(T,Freqs,TRes),
	bereken(H,Freqs,Berek),
	Res = [Berek|TRes].</nowiki>