Declaratieve Talen/alternatiefHuffman

Oplossing1

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].

Oplossing2

decodeer(N,Code,Res):-
	%lijst 0-N-1
	NewN is N-1,
	lijst_maken(NewN,[],Lijst),
	%geef een opl (niet-rekeninghoudend met N)
	geef_opl(Code,[],Opl),
	%test of opl voldoet aan N
	length(Opl,N),
	%zet in juiste vorm
	zet_vorm(Opl,Lijst,[],Res).


%maakt een lijst met elementen van 0-N
lijst_maken(-1,L,L).
lijst_maken(N,L,Elem):-
	NewN is N-1,
	lijst_maken(NewN,[N|L],Elem),!.


geef_opl([],Opl,Opl).
geef_opl(Code,TempOpl,FinalOpl):-
	append(L,R,Code),
	L \== [],
	is_geen_prefix_vorige(L,TempOpl),
	\+ is_prefix_volgende(L,R),
	append(TempOpl,[L],NewTempOpl),
	geef_opl(R,NewTempOpl,FinalOpl).


is_geen_prefix_vorige(_Code,[]).
is_geen_prefix_vorige(Code,[A|Vorige]):-
	\+ append(Code,_R,A),
	is_geen_prefix_vorige(Code,Vorige).

is_prefix_volgende([],_Volgende).
is_prefix_volgende([C|Code],[C|Volgende]):-
	is_prefix_volgende(Code,Volgende).
	

zet_vorm([],[],Res,Res).
zet_vorm([O|Opl],[L|Lijst],TempRes,FinalRes):-
	append(TempRes,[L-O],NewTempRes),
	zet_vorm(Opl,Lijst,NewTempRes,FinalRes).



beste(N,Code,Freqs,Res):-
	%alle decodaties vinden
	findall(Dec,decodeer(N,Code,Dec),Decs),
	%voor elke tellen hoeveel cijfers gebruikt
	findall(Dec-Cijfer,(member(Dec,Decs),hoeveel_cijfers(Freqs,Dec,0,Cijfer)),Cijfers),
	%best=met minste cijfers
	minste_cijfers(Cijfers,Res).
	

hoeveel_cijfers([],[],Cijfer,Cijfer).
hoeveel_cijfers([Symbool-Aantal|Freqs],[Symbool-Code|Dec],TempC,FinalC):-
	length(Code,Lengte),
	N is Aantal*Lengte,
	NewTempC is TempC+N,
	hoeveel_cijfers(Freqs,Dec,NewTempC,FinalC).

minste_cijfers([C|Cijfers],Res):-
	minste_cijfers2(Cijfers,C,Res).

minste_cijfers2([],Res,Res).
minste_cijfers2([Dec1-N1|Cijfers],Dec2-N2,Res):-
	(
	N1<N2 ->
		minste_cijfers2(Cijfers,Dec1-N1,Res)
	;
		minste_cijfers2(Cijfers,Dec2-N2,Res)
	).

Nog een alternatieve oplossing --Lynn 15 jan 2011 21:50 (UTC)

Oplossing3

decodeer(X,Code,Resultaat):- verdeelcode(X,Code,Res), schrijfNummer(Res,0,Resultaat).

verdeelcode(1,Code,[Code]). verdeelcode(X,Code,[A|Res]):- Y is X-1, append(A,NewCode,Code), length(A,La), length(NewCode,Ln), La>0, Ln>0, \+append(A,_,NewCode), \+append(NewCode,_,A), verdeelcode(Y,NewCode,Res), forall(member(Z,Res), ( \+append(A,_,Z), \+append(Z,_,A) )).

schrijfNummer([],_,[]). schrijfNummer([X|Xs],N,[N-X|Res]):- M is N+1, schrijfNummer(Xs,M,Res).

beste(X,Code,Freqs,Y):- findall(Res1,decodeer(X,Code,Res1),List), member(Y,List), minimaal(Y,Freqs),!.

minimaal(Code,Freqs):-minimaal(Code,Freqs,0,0). minimaal([],[],_,_). minimaal([N-X|Rest1],[N-Y|Rest2],0,0):-length(X,M), minimaal(Rest1,Rest2,M,Y). minimaal([N-X|Rest1],[N-Y|Rest2],KleinsteCode,Voorkomen):- length(X,M), ( M>KleinsteCode-> ( Y<Voorkomen-> minimaal(Rest1,Rest2,M,Y) ; fail ) ; minimaal(Rest1,Rest2,KleinsteCode,Voorkomen) ).

Nog een alternatieve oplossing --Greet