Declaratieve Talen/oplossingHuffmanBoom

Deze oplossing houdt de reeds geconstrueerde codewoorden bij, door de huffman-boom op te bouwen. Dit laat toe tijdens het nakijken van een codewoord meteen het toegevoegde codewoord op te nemen. De beste oplossing zoeken gebeurt mbv de ingebouwde sort in bagof/3 (Joris Peeraer)

% decodeer(Number, Msg, Res)
%
% Number = aantal codewoorden
% Msg    = achter elkaar geplaatste codewoorden
% Res    = lijst met gesplitste codewoorden
decodeer(N, Msg, Res) :-
    zoek(0, N, Msg, [], nil, [], RRes),
    reverse(RRes, Res).

% zoek(CodeNr, Number, Msg, Current, Tree, Acc, Res)
%
% CodeNr  = volgnummer huidig vormend codewoord
% Number  = aantal codewoorden
% Msg     = resterende te decoderen boodschap
% Current = huidige vormend codewoord
% Tree    = huffman-boom
% Acc     = accumulator voor resultaat
% Res     = resultaat
zoek(N, N, [], [], _, Res, Res).
zoek(N, Nmax, [M|Ms], C, TO, Acc, Res) :-
    append(C, [M], CN),
    plaatsInBoom(CN, TO, T, A),
    (
        A = recurse,
        N1 is N + 1,
        zoek(N1, Nmax, Ms, [],  T, [N-CN|Acc], Res)
    ;
        zoek(N , Nmax, Ms, CN, TO, Acc, Res)
    ).

% plaatsInBoom(Code, OldTree, NewTree, Action)
%
% Code    = code
% OldTree = huffman-boom voor toevoegen
% NewTree = huffman-boom na toevoegen
% Action  = action to proceed with € {recurse, expand}
plaatsInBoom([], nil, code, recurse) :- !.
plaatsInBoom([], code, _, _) :- !, fail.
plaatsInBoom([], T, T, expand).

plaatsInBoom([0|C], nil, t(L, x, nil), A) :-
    plaatsInBoom(C, nil, L, A).
plaatsInBoom([1|C], nil, t(nil, x, R), A) :-
    plaatsInBoom(C, nil, R, A).
plaatsInBoom([0|C], t(L, x, R), t(LL, x, R), A) :-
    plaatsInBoom(C, L, LL, A).
plaatsInBoom([1|C], t(L, x, R), t(L, x, RR), A) :-
    plaatsInBoom(C, R, RR, A).


% quality(Huffman, Freq, Acc, Quality)
%
% Huffman = huffman codering
% Freq    = frequentie van de woorden
% Quality = kwaliteit van de code (lager is beter)
quality([], [], Q, Q).
quality([W-C|Cs], [W-N|Fs], Acc, Q) :-
    length(C, L),
    Q1 is L * N + Acc,
    quality(Cs, Fs, Q1, Q).


% beste(Number, Msg, Freq, Res)
%
% Number = aantal codewoorden
% Msg    = achter elkaar geplakte codewoorden
% Freq   = lijst met frequenties van woorden
% Res    = beste huffman codering
beste(N, Msg, Freq, Res) :-
    setof(Q-Res, (decodeer(N, Msg, Res), quality(Res, Freq, 0, Q)), Set),
    Set = [_-Res|_].