Huffman Algorithmus? < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:16 So 29.10.2006 | | Autor: | anika23 |
Hallo,
...ich habe ein für mich schwieriges Problem. Ich suche seit Tagen über diverse Suchmaschienen und Suchbegriffen einen
pssenden Algorithmus und bin leider bis jetzt nicht fündig geworden, obwohl soetwas eigentlich
schon existieren müßte.
Ich versuche mein Problem mal etwas genauer und hoffentlich auch verständlich zu umschreiben.
Ich habe einen sehr langen Text, der alle möglichen Namen enthält. Diese Daten muss ich komprimieren. Ich habe nun alle
möglichen Teilstrings > 3 aus dem Text gefiltert.
Beispiel: Das Wort "Theater" enthält folgende Teilstrings: heater,eater,ater,ter,heate,heat,hea,eate,eat,ate usw...
Diese Teilstrings habe ich inkl. Ihrer Häufigkeit in einer Map gespeichert. Jeder Teilstring hat dabei einen 2-Stelligen
Code erhalten. Ich möchte nun meinen Text komprimieren und durch diese Codes ersetzen. Dabei soll der Text natürlich so
gut wie möglich komprimiert werden.
Beispiel: Das Wort "Theater" könnte zu "ThC3er" werden (eat wurde ersetzt durch "C3"). Dies ist aber nicht der optimale
Fall. Besser wäre "TC5" (heater wurde ersetzt durch "C5", "C5" ist der Code für "heater" in meiner Map).
Nun möchte ich die für meinen Text optimalen 256 Teilstrings heraus finden und in einer Extra-Map speichern, wobei der
effektivste Teilsstring(Gewicht aus Länge und Häufigkeit)a an erster Stelle steht in meiner Map, da ich bei der Codierung
von Wörter durch meineMap von oben nach unten durchgehe und die Teilstrings in meinem Wort suche und codiere.
Dabei entsteht aber folgendes Problem:
Das Wort "Puppentheater" könnte ersetzt durch "entheater" doch besser wäre durch "Puppen" und "Theater", obwohl der Teilstring
"entheater"länger ist als die beiden anderen Teilstrings. Wie sortiert man also am besten die Map der Teilstrings
um eine optimale Codierung zu erhalten?
Könnte man z.B die Teilstrings nach dem Huffman Algorithmus sortieren?
Habe mir den Algotithmus auch schon angeschaut.Verstehe ihn aber nicht.....
Ich hoffe mir kann jemand helfen, denn ich brauche dringend eine Lösung!
vielen Dank für alle Bemühungen im Voraus....
lg Anika
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Anika,
der Huffman-Algorithmus oder Huffman-Code wird eigentlich immer so beschrieben, dass man Bytes bzw. Zeichen ihrer Häufigkeit nach Ordnet und dann die häufigsten Zeichen durch einen kürzeren und die weniger häufigen durch einen längeren Code ersetzt. Du ersetzt also im Prinzip gleich große Teile Deines Textes oder generell Deiner Daten durch unterschiedlich lange Codes.
Generell müssen Die Teile Deiner Daten aber gar nicht unbedingt Bytes sein. Du kannst genausogut auch 2 oder mehrere Bytes bzw. Zeichen nehmen und kodieren. Noch allgemeiner müsste der Teil, den Du ersetzt nicht mal einheitlich groß sein.
Bei einem Text könnte das sinnvoll sein, weil bestimmte Zeichenkombinationen sehr häufig aufauchen können, wärend andere gar nicht vorkommen.
Die üblichen Beschreibungen gehen aber davon aus, dass man immer einzelne Zeichen ersetzt.
Da Du die am häufigsten vorkommenden Zeichen bzw. Zeichenkombinationen durch kürzere Codes ersetzt, wird insgesamt die Länge der komprimierten Daten geringer.
Für einzelne Zeichen funktioniert der Code so. Du analysierst erst mal Deinen Text z.B.
HUFFMAN CODES WERDEN ZUM KOMPRIMIEREN VON DATEN VERWENDET IN DENEN MANCHE ZEICHEN HAEUFIGER VORKOMMEN ALS ANDERE
Du hast dann
E 19
_ 15
N 13
R 7
M 7
D 6
A 6
O 5
I 5
H 4
F 3
U 3
C 3
V 3
K 2
Z 2
W 2
T 2
S 2
P 1
G 1
L 1
also insgesamt 22 Zeichen. Jetzt benötigst Du einen Code, der prefixfrei ist. D.h. Du willst ja später aus dem resultierenden Code wieder den Originaltext bekommen können. Dafür musst Du aber wissen, wie Dein komprimierter Text in einzelne Codewörter zerfällt.
Wenn Du das hier mal genau anschaust:
00
01
100
101
1100
1101
11100
11101
111100
111101
1111100
1111101
11111100
11111101
111111100
111111101
1111111100
1111111101
11111111100
11111111101
11111111110
11111111111
dann siehst Du, dass keiner der Codes (Binärdarstellung) einen anderen kürzeren Code enthält, wenn man vereinbart, dass die Codes vom ersten Zeichen ab übereinstimmen müssten. Da das so ist, kannst Du die Codes beliebig aneinander reihen und sie dann beim dekomprimieren wieder eindeutig in den Ausgangstext umwandeln, wenn Du den Komprimierten Text von links liest.
Was Dir sicher noch aufgefallen ist, ist dass die Codes am Ende ziemlich länglich werden. Der letzte besteht aus 11 Bit. Um die 22 verschiedenen Zeichen zu kodieren hätten Dir aber 5 Bit [mm] (2^5-1=31) [/mm] ausgereicht. Die 4 größten Codes verschwenden also eigentlich ziemlich viel Platz. Dass der erste Code aber 2 Bit lang ist, liegt einfach daran, dass ich meinen Code so gewählt habe, dass ich für jede Länge des Codes in Bit gleich 2 Code-Wörter habe. Ich hätte auch einen wählen können, in dem der erste Code mit Länge 1 anfängt und der zweite dann Länge 2 hat und so weiter. Dann wäre die Code-Länge aber sehr schnell gewachsen. Wahrscheinlich kannst Du genauso auch Codes definieren, die noch langsamer wachsen, wenn Du den ersten Code noch länger machst. Hab ich noch nicht versucht, müsste aber gehen.
Ausgehend von der Verteilung ordnest Du im zweiten Schritt die Codes den Zeichen Deines Textes zu:
E 19 00
_ 15 01
N 13 100
R 7 101
M 7 1100
D 6 1101
A 6 11100
O 5 11101
I 5 111100
H 4 111101
F 3 1111100
U 3 1111101
C 3 11111100
V 3 11111101
K 2 111111100
Z 2 111111101
W 2 1111111100
T 2 1111111101
S 2 11111111100
P 1 11111111101
G 1 11111111110
L 1 11111111111
Der Teilstring WERDEN wird dann zu folgendem Bit-String:
111111110000101110100100
Das genannte Beispiel zeigt noch nicht so richtig die Effizienz dieses Codierungsverfahrens, weil ja eigentlich 5 Bit ausreichen würden um die 22 unterschiedlichen Zeichen zu kodieren. Wenn man aber von üblichen 8-Bit-Zeichensätzen ausgeht, wird die Einsparung größer sein, da dann der unterschied vom kleinsten Code zur Bitlänge eines Bytes größer ist (man spart dann 6 Bit für die häufigsten Zeichen statt nur 3 wie im Beispiel).
Texte kann man aber wahrscheinlich durch solche häufig vorkommenden Teilstrings, wie Du es erwähnt hast auch sehr effektiv komprimieren. Vieleicht kannst Du beide Verfahren kombinieren.
Gruß
Jürgen
|
|
|
|
