heute ist der Geburtstag von
Gabriel Cramer (31.07.1704 - 04.01.1752)


Auf das Thema antworten  [ 22 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Alle Beiträge anzeigen 
SS09: 2. Übung 
Autor Nachricht
Benutzeravatar

Registriert: 10/2007
Beiträge: 27 + 109
Studium: (alt) Master Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
das ist mein code:
ich habs auch vom skriptum in matlab kopiert und adaptiert.
die c-werte speichere ich als normale zahl, wobei ich eine null anhänge, indem ich mit 10 mulptipliziere!
wie gesagt, viele wege führen nach rom :mrgreen:
damit führende nullen auch angezeigt werden, steht am anfang immer eine 2, die ignoriert werden muss.

der Algorithmus spuckt zum schluss den sortierten Vektor der Wahrscheinlichkeiten und danach
die zugehörigen Huffman-Codes in der richtigen reihenfolge.

Code:
function c=huffman(P)
n=size(P,2);
P=sort(P,'descend');
G(1,1:n)=P(1:n);
G(2,1:n)=[1:n];
%sortiere G gem¨aß G(1,:) absteigend
[tmp,ind]=sort(G(1,1:n),'descend');
G=G(1:2,ind);
for i = 1:n-1
G(1,n-i)=G(1,n-i)+G(1,n-i+1);
L(i)=G(2,n-i);
R(i)=G(2,n-i+1);
G(2,n-i)=n+i;
%L¨osche G(i, n-i+1)
G=G(1:2,1:n-i);
%sortiere G gem¨aß G(1,:) absteigend
[tmp,ind]=sort(G(1,1:n-i),'descend');
G=G(1:2,ind);
end

c(L(n-1))=20, c(R(n-1))=21;
for j = n-2:-1:1
c(L(j))=c(j+n)*10;
c(R(j))=c(j+n)*10+1;
end
P
c=c([1:n]);


Mo 23-03-2009 23:18:33
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2007
Beiträge: 27 + 109
Studium: (alt) Master Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
Beim 3. Beispiel habe ich für m=5
$H^*(P)=1+min(2-2p_1,3-3p_1-2p_2-p_3,2-p_1-p_2-p_3)$
Hat das sonst auch noch jemand? Bin mir nämlich nicht ganz sicher....


Mo 23-03-2009 23:58:41
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 26 + 29
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
ja, aber mit der variante hats bei mir mit matlab funktioniert,
der code ist übrigens an dem im skript angelehnt,
der vektor c ist einfaach der vektor mit deinen knoten
musste es aber zeilenweise definieren, da c mit der methode als 'matrix' wächst...
d.h. c(1,:) ist bei mir 10 und der spricht für den knoten A, bzw c(3,:)=011 -->C,
mir kommt dann in matlab der wegtor c zurück und das ist der richtige für A bis h,
wobei durch das sortieren eig 2 verschiedene bäume zulässig sind:
bei mir ist es folgender (der andere wurde bereits weiter oben angegeben):
h
-D
-f
--B
--C
g
-A
-E

bzw. entsprechend
A-10
B-010
C-011
D-00
E-11
f-01
g-1
h-0

ist halt einer dieser vielen wege :)


Zuletzt geändert von s.e am Di 24-03-2009 00:17:08, insgesamt 1-mal geändert.



Di 24-03-2009 00:08:55
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 26 + 29
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
nicht der schönste, aber ist halt auch auch einer.

Code:
function huffman(P)
n=length(P);
G=zeros(2,n);
G(1,1:n)=P(1:n);
G(2,1:n)=[1:n];
G=G';
G=sortrows(G,1);
G=G(n:-1:1,:);
G=G';

for i=1:n-1
    G(1,n-i)=G(1,n-i)+G(1,n-i+1);
    L(i)=G(2,n-i);
    R(i)=G(2,n-i+1);
    G(2,n-i)=n+i;
    G=G(:,1:end-1);
   
    G=G';
    G=sortrows(G,1);
    G=G(n-i:-1:1,:);
    G=G';
end


c(L(n-1),1)='0';
c(R(n-1),1)='1';

for j=n-2:-1:1
  c(L(j),:)=c(j+n,:);
  c(L(j),length(c(j+n,:))+1)='0';
  c(R(j),:)=c(j+n,:);
  c(R(j),length(c(j+n,:))+1)='1';
end   
c
end


Di 24-03-2009 00:15:29
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 05/2008
Beiträge: 27 + 12
Wohnort: Wien West
Studium: (alt) Bachelor Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
kater hat geschrieben:
probiers doch einfach mal mit
c(j+n,0)
:mrgreen:

hehe :D
kater hat geschrieben:
aber wenn du mir sagst, was die c()-funktion macht, was in L(j) drin ist (zeile oder spalte und welche dimension), dann sag ich dir, wie man eine 0 dranhängt 8)

Schau doch einfach mal den Algorithmus auf dem Skriptum an, dann weißt du was die c()-Funktion macht.. ;)


Di 24-03-2009 01:25:50
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 05/2008
Beiträge: 27 + 12
Wohnort: Wien West
Studium: (alt) Bachelor Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
@highstick: Das mit dem "*10" und "*10+1" hatte ich auch probiert.. Jedoch gefällt mir zB bei dem Code der 2er vorne überhaupt nicht! :D
Sieht einfach nicht schön aus. Dann hatte ich mir gedacht, ich mach verzweigungen: if c(j+n)= 0 --> c(L(j))="00" ausgeben..
und else c(L(j))=c(j+n)*10 bzw. das selbe mit 01 und *10+1
Jedoch funktionierte dies nicht mit zahlen, da 00 immer auf 0 gekürzt worden ist und chars nicht erlaubt waren im vektor...
Am Schluss hab ich mir gedacht, ich lass es einfach so! :D Wir werden das Programm eh nicht auf Ausführbarkeit testen, sondern auf der Tafel präsentieren.. Da muss man nur wissen, was der Code so macht.. ;)

EDIT: Tschuldigung für den Doppelpost :)


Di 24-03-2009 01:34:34
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
ich bleib lieber bei python, das kann ich besser :)


Di 24-03-2009 10:12:52
Diesen Beitrag melden
Profil
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 22 Beiträge ]  Gehe zu Seite Vorherige  1, 2
Alle Beiträge anzeigen 


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst neue Themen in diesem Forum erstellen.
Du darfst Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB © phpBB Group.  |  Designed by STSoftware for PTF  |  © Czechnology 2007 - 2021  |  Deutsche Übersetzung durch phpBB.de