Hier folgt nun meine Implementierung des Shannon-Fano Algorithmus für Maple, die wir bezüglich unseres Mathematik-Praktikums “Tag7” programmieren sollten!
Aufgabe 1 (Shannon-Fano)
Implementieren Sie einen Algorithmus zur Shannon-Fano Kodierung und berechnen Sie eine Kodierung für das Beispiel 21.1.
Beispiel 21.1: [[a,41],[b,33],[c,23],[d,25],[e,100]]
Prozedur:
restart:
with(GraphTheory):
with(Logic):
with(networks):
##Aus dem Mapleskript zum Sortieren von Listen!
comp2 :=proc(a::list,b::list)
if a[2] < b[2] then true else false fi;
end:
##Der Graph muss vor der Prozedur initialisiert werden!
global G2:
G2:=Digraph():
########################################################################
##Prozedur Shannon-Fano!
ShaFa:=proc(L::listlist)
global prev, ECKE, KANTE, G2;
local i,j,k,l,v,S,Sl,Sr,hauf1,hauf2,hauf3,hauf4,hauf5;
##Sortierung der Liste!
S := sort( L , comp2);
##Lokale Variablen initialisieren!
hauf1:=0;
hauf2:=0;
hauf3:=0;
hauf4:=0;
hauf5:=0;
Sl:={};
Sr:={};
ECKE:={};
KANTE:={};
##Gesamthäufigkeit von S!
i:=1;
while(i<=nops(S)) do
hauf1:=hauf1+S[i][2];
i:=i+1;
od:
##Festlegen einer Grenze für die Häufigkeit, damit Sl und Sr ungefähr die gleiche Häufigkeit haben!
hauf3:=((hauf1/2))+(S[nops(S)][2]/nops(S));
##Algorithmus der S in Sl und Sr überführt!
j:=1;
while(j<=nops(S)) do
hauf2:=hauf2+S[j][2];
if(hauf2<=hauf3) then
Sl:=[op(Sl),S[j]];
fi;
if(hauf2>hauf3)then
Sr:=[op(Sr),S[j]];
fi;
j:=j+1;
od:
##Kontrolle ob auch alles funktioniert!
print(S);
print(“linkerTeilbaum:”, Sl);
print(“rechterTeilbaum:”, Sr);
##Gesamthäufigkeit von Sl! Wird beim Erstellen der Ecken und Kanten gebraucht!
k:=1;
while(k<=nops(Sl)) do
hauf4:=hauf4+Sl[k][2];
k:=k+1;
od:
##Gesamthäufigkeit von Sr! Wird beim Erstellen der Ecken und Kanten gebraucht!
l:=1;
while(l<=nops(Sr)) do
hauf5:=hauf5+Sr[l][2];
l:=l+1;
od:
##Welche Ecken sind in G2 vorhanden!
v:=Vertices(G2);
##Wenn nicht in G2, dann initialisiere die Wurzel!
if not member(hauf1, v) then
ECKE:=[op(ECKE),hauf1];
fi;
##rechter Teilbaum: Fügt entweder eine endgültige Ecke oder eine weitere Ecke hinzu, an der weitere Ecken folgen können!
if(nops(Sr)=1) then
ECKE:=[op(ECKE),Sr[1][1]];
KANTE:=[op(KANTE),[hauf1,Sr[1][1]]];
else
ECKE:=[op(ECKE), hauf5];
KANTE:=[op(KANTE),[hauf1,hauf5]];
fi;
##linker Teilbaum: Fügt entweder eine endgültige Ecke oder eine weitere Ecke hinzu, an der weitere Ecken folgen können!
if(nops(Sl)=1) then
ECKE:=[op(ECKE),Sl[1][1]];
KANTE:=[op(KANTE),[hauf1,Sl[1][1]]];
else
ECKE:=[op(ECKE),hauf4];
KANTE:=[op(KANTE),[hauf1,hauf4]];
fi;
##Kontrolle ob auch alles funktioniert!
print(“Ecken:”,ECKE);
print(“Kanten:”,KANTE);
##Die Ecken und Kanten werden dem Graphen G2 hinzugefügt!
G2:=AddVertex(G2,ECKE);
G2:=AddArc(G2, KANTE);
##rekursiver Aufruf bis Sl und Sr =1 sind!
if(nops(Sr)>1) then ShaFa(Sr); fi;
if(nops(Sl)>1) then ShaFa(Sl); fi;
##Rückgabe des Graphen G2 zum Zeichnen!
return G2;
end:
########################################################################
Aufruf:
S:=ShaFa([[a,41],[b,33],[c,23],[d,25],[e,100]]);
Graphzeichnen:
DrawGraph(S);