Artikel pedia
| Home | Kontakt | Artikel einreichen | Oberseite 50 artikel | Oberseite 50 autors
 
 


Artikel kategorien
Letztes fugte hinzu
    Ms-access

   Instrumentation + schnittstellen

   Pc tuning - volle kraft voraus für ihr system

   Informatorische grundlagen

   Javascript

   Interne sortieralgorithmen - der kern der sache

   Plotter und sonstige drucker

   Frage 20 (rössl priska)

   Internet - programmierung

   Monitore

   Semesterarbeit und spezialgebiet für informatik

   Erörterungs zum thema

   Inhaltsverzeichnis

   Einführung in die entwicklung ganzheitlicher informationssysteme:

   Titel dokument
alle kategorien

  Programmier -

1) Datenkompremierung (File Compression):   Dieser Algorithmus behandelt in erster Linie die Platzreduzierung und erst in zweiter Linie behandelt er die Zeitreduzierung. Diese Technik heißt auch Kodierungsmethode. Im allgemeinen haben Dateien einen hohen Grad an Redundanz. Die Verfahren die wir untersuchen sparen Platz weil die meisten Dateien einen relativ geringen Informationsgehalt haben Einsparungen kann man bei einer Textdatei von 20% bis 50% haben, jedoch bei einer binären Datei hat man Einsparungen von 50% bis 90%. Doch es gibt auch Datentypen bei dem man nur wenig einsparen kann, solche die aus zufälligen Bits bestehen. Tatsächlich ist es so, daß Mehrzweck-Verfahren gewisse Dateien verlängern müssen, den sonst könnte man das Verfahren wiederholen und dadurch beliebig kleine Dateien erzeugen.

  2) Lauflängenkodierung (Run-Length Encoding):   Man spricht hier von einen Lauf (run) dann, wenn sich lange Folgen sich wiederholender Zeichen darstellt.   Siehe dieses Bsp sprich 1.Metode: AAAABBBAABBBBBCCCCCCCCDABAAABBBBCCCD     Diese Zeilenfolge kann viel Kompakter kodiert werde, indem man die wiederholenden Zeichen nur einmal angibt und die Anzahl der Wiederholungen davor schreibt.     Also würde dann unser Bsp. kodiert so aussehen:   4A3B2A5B8CDABCB3A4B3CD     Bei einem Bitraster würde die Lauflängenkodierung so aussehen:   2. Methode oder Bsp.

: 000000000000000000000000000111111111111111000000000 28 14 9 000000000000000000000000001111111111111111110000000 26 18 7 000000000000000000000001111111111111111111111110000 23 14 4 000000000000000000000011111111111111111111111111000 22 26 3 000000000000000000001111111111111111111111111111110 20 30 1 000000000000000000011111110000000000000000001111111 19 7 18 7 000000000000000000011111000000000000000000000011111 19 5 22 5 000000000000000000011100000000000000000000000000111 19 3 26 3 000000000000000000011100000000000000000000000000111 19 3 26 3 000000000000000000011100000000000000000000000000111 19 3 26 3 000000000000000000011100000000000000000000000000111 19 3 26 3 000000000000000000001111000000000000000000000001110 20 4 23 3 1 000000000000000000000011100000000000000000000111000 22 3 20 3 3 011111111111111111111111111111111111111111111111111 1 50 011111111111111111111111111111111111111111111111111 1 50 011111111111111111111111111111111111111111111111111 1 50 011111111111111111111111111111111111111111111111111 1 50 011111111111111111111111111111111111111111111111111 1 50 011000000000000000000000000000000000000000000000011 1 2 46 2     Hier in diesem Bitraster sieht man rechts eine Liste von Zahlen, die einen Buchstaben in einer kompremierten Form speichern können. Man gibt nun links davon die jeweiligen Häufigkeiten an wie oft nun diese Null oder Eins vorkommt, zB.: in der ersten Zeile, sie besteht aus 28 Nullen 14 Einsen und dann folgen wieder 9 Nullen usw geht es mit den anderen Zeilen. Man sieht also, daß es wesentlich besser ist die kodierte Form zu übergeben als die unkodierte, und man kann auch so wieder den Bitraster rekonstruieren. Man hat dadurch eine recht große Einsparung, denn man 975 Bits bei unkodierten Darstellung verwenden, aber jedoch nur 384 Bits bei der kodierten Darstellung, ergibt eine Einsparung von 591 Bits.   3) Kodierung mit variabler Länge (Variable-Length Encoding):   Dieses Datenkompressionsverfahren spart beträchtlich Platz bei Textdateien.

Nehmen wir an wir wollen eine Zeichenfolge „ABRACADABRA“ kodieren, und dieses mit dem herkömmlichen Verfahren des binären-Codes, bei einer Binärdarstellung mit Hilfe von 5 Bits zu Darstellung eines Buchstabens. Dann lautet die Bitfolge so:   0000100010100100000100011000010010000001000101001000001   Um diese zu dekodieren, nimmt man sich 5 Bits her und wandelt sich nach dem Binärcode um. Nun ist dieses ziemlich unpraktisch, denn der Buchstabe D kommt nur einmal vor, aber der Buchstabe A jedoch 5 mal und ich muß A jedesmal die selbe Bitfolge aufschreiben und wieder dekodieren. Es wäre doch besser wenn man versuchen würde, häufig verwendete Buchstaben eine kürzere Bitfolge zuzuweisen, indem man sagt A wird mit 0 kodiert, B mit 1, R mit 01, C mit 10 und D mit 11, so daß dann aus ABRACADABRA dann diese   0 1 01 0 10 0 11 0 1 01 0   Bitfoge dann werden würde. Diese ist schon wesentlich kürzer denn diese Bitfolge hat nur mehr 15 Bits benutzt als die vorhergehende die 55 Bits verbraucht hat. Doch hat dieser Code einen Haken, denn es ist kein wirklicher Code, da er abhängig ist von den Leerzeichen, ohne diese Leerzeichen würde nämlich 010101001101010 als RRRARBRRA heraus kommen.


Also muß man die Zahl mit Begrenzern dekodieren, aber dann noch ist die Zahl von 15 Bits plus 10 Begrenzern noch immer Kleiner als der Standart-Code.   Wenn kein Zeichencode mit dem Anfang eines anderen übereinstimmt werden keine Begrenzer benötigt. Deswegen werden wir die zu kodierenden Buchstaben anders gewählt, nämlich: A mit 11, B mit 00, C mit 010,D mit 10 und R mit 011 so gäbe es nur eine Möglichkeit die 25 Bits Zeichenfolge   1100011110101110110001111   zu dekodieren.       Eine noch einfachere Methode zur Darstellung eines Codes ist ein Trie.     Dazu ein Bsp.: Wir wollen wieder ABRACADABRA kodieren, aber dieses mal mit dem Trie.

Dazu sollte man wissen, daß man bei einem Trie immer von der „Wurzel“ ausgeht und so sein Zeichen bestimmt. Wenn man bei einem Knoten angelangt ist, muß man sich entscheiden ob nach links oder rechts. Für links muß man mit 0 codieren und für rechts mit 1.   1.Bsp: 2.Bsp:   1100011110101110110001111 01101001111011100110100         A R B D A B C R D C   Nun, man sieht hier, daß der rechte Code um 2 Bits kürzer ist als der andere.

Die Trie-Darstellung garantiert also, daß kein Code für ein Zeichen mit den Anfang eines anderen Zeichen übereinstimmt, so daß sich die Decodierung für die Zeichenfolge eindeutig festlegen läßt. Doch welchen Trie soll man Benutzen? Hier gibt es eine Lösung bei der man bei gegebener Zeichenfolge einen Trie berechnen kann und der eine minimale Bitfolge hat. Dieses Verfahren wird Huffman Kodierung genannt.   4) Erzeugung des Huffman-Codes (Building the Huffman Code):   Bei dem Erzeugen des Huffman-Codes kommt es in erster Linie darauf an wieviel Zeichen zu decodieren sind plus Leerzeichen. Nun ermittelt das folgende Programm die unterschiedlichen Häufigkeit der Buchstaben eines Zeichenfeldes, und trägt sie dann in ein Feld count[0-26] ein.   Nun wieder ein Beispiel das wir kodieren möchten, die Zeichenfolge lautet: „A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBERS OF BITS“.

Der erste schritt ist der Aufbau eines Tries entsprechend seiner Häufigkeiten, dazu sollte man sich eine Buchstabentabelle machen.   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 count[k] 11 3 3 1 2 5 1 2 0 6 0 0 2 4 5 3 1 0 2 4 3 2 0 0 0 0 0   Danach kann man schon mit dem Trie beginnen, man fängt an in dem man die Buchstaben (Knoten) mit der Häufigkeit 0 wegläßt, und alle anderen Knoten mit ihrer Häufigkeit in einer Ebene darstellt. Nun nimmt man die Knoten mit den niedrigsten Häufigkeiten und fasse sie zusammen. Man nimmt nun die nächst höhere Häufigkeit und fasse sie wieder zusammen, dieses geht so lange weiter bis alle Häufigkeiten in einem Baum dargestellt sind.   Beachten muß man jedoch daß die sich Knoten mit geringer Häufigkeit weit unten im Baum befinden und Knoten mit hoher Häufigkeit weit oben im Baum befinden. Die Quadratischen Knoten sind Häufigkeitszähler und die runden Knoten sind Summen Knoten und lassen sich durch ihre Nachfolger wieder darstellen.

  5) Implementation (Implementation):   Bei der Implementation kommt es mehr darauf an den Huffman-Code richtig anzuwenden bzw. die Vorausberechnen richtig zu rechnen um denn daraus eine effiziente Kodierung zu kriegen. Man sollte hier einen Trie finden der die Häufigkeit der Buchstaben berechnet oder für Zeichen verwendet, deren Häufigkeit in einem Pascal Programm auftritt zB.: ; und dafür eine Bitfolge reserviert. So ein Kodierungsalgorithmus kann mit Hilfe des Huffman Codes 23% Einsparung liefern.                                    

Suchen artikel im kategorien
Schlüsselwort
  
Kategorien
  
  
   Zusammenfassung Der Vorleser

   sachtextanalyse

   interpretation zwist

   Fabel interpretation

   literarische charakteristik

   interpretation bender heimkehr

   felix lateinbuch

   interpretation der taucher von schiller

   textbeschreibung

   charakterisierung eduard selicke
Anmerkungen:

* Name:

* Email:

URL:


* Diskussion: (NO HTML)




| impressum | datenschutz

© Copyright Artikelpedia.com