Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Grundlagen der Informatik und Computernetze (VL 09): Codierung, Kompression, Lempel-Ziv-Welch (LZW)

Ulrich Greveler1:22:32 726 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 540 Zeilen
Herunterladen
  1. ja schönen guten Morgen Grüße diese neunten Vorlesung grundlag der Informatik und Computernetze auch schön heute wieder dass viele von ihnen
  2. gekommen sind trotz des ja furchtbaren Wetters im Moment einige wohl nass geworden mich eingeschlossen ja heute geht's um
  3. Codierung wir haben darüber schon mal gesprochen im einen oder anderen Kontext also auch der ASK Code ist natürlich ein coache und damit auch eine Codierung und
  4. dann etwas mehr im Schwerpunkt dann auch um Daten Kompression das ist also eine besondere Form der Codierung da geht's dann darum Speicherplatz zu sparen das
  5. soll uns heute beschäftigen noch dazu habe ich Folien vorbereitet also wie gesagt der Begriff Codierung ist un schon begegnet
  6. das ist ja auch ein Alltagsbegriff dort allerdings oft in dem sehr starken Kontext geheime Codierung ne erwähnte ich ja auch schon bei uns ist das nicht
  7. geheim wir haben natürlich auch eine Disziplin bei der it Sicherheit so auch dort geschnitten mit der Mathematik dann wäre das Kryptographie da geht's
  8. dann tatsächlich darum etwas wirklich geheimzuhalten zu schützen also Sicherheitsziele wie Vertraulichkeit oder Integrität von Daten zu schützen
  9. darum geht's aber heute nicht da haben sie eine eigene Vorlesung zu dann in ihrem vierten Semester also vierten gelesenen Semester heute geht's also
  10. wirklich um Codes und da sehen sie auch eine Definition letztlich ist das nur eine Funktion Wörter werden abgebildet auf
  11. Wörter und wir haben halt Alphabete auf beiden Seiten und dann wird eben ein Wort über dem einem Alphabet auf ein Wort über dem
  12. anderen Alphabet abgebildet und bei aski ist es ja auch irgendwie offenkundig ne da habe ich so ein Zeichen wie das große a ne und das bilde ich dann ab auf die
  13. Zahl 65 oder auf den 7 bit String der dann dem Wert 65 entspricht sie wissen ask ist z.B ein 7 bit Code wir verwenden oft als 8 Bit Code das liegt aber eher
  14. daran dass das acht eine runde Zahl ist ähnlich wie Unicode da hat wir sogar verschiedene kennengelernt so also Möglichkeiten die unico Zeichen dann
  15. noch abzubilden UTF8 UTF 16 bis UTF 32 und das sind mögliche Codes die natürlich von höchster Praxis relevan sind aber es gibt noch weitere aber
  16. zunächst mal das ist eben die allgemeine Definition also wie gesagt hat nichts mit lustigen Geheimagenten zu tun wieder auf der rechten Seite abgebildet sind
  17. sehr oft haben wir es eben damit zu tun dass wir irgendwas auf Bits und bites abbilden ja klar ne damit es maschinenlesbar wird damit wir es in
  18. Algorithmen einfüttern können allgemein spricht man dann von binärer Codierung das kommt Hal so häufig vor dass man da einfach ein einzelnen Begriffe gewählt
  19. hat ansonsten können Sie aber auch beliebig über irgendwelche Alphabete einen Code definieren und das ist je nach Kontext dann auch sehr sinnvoll und
  20. no nicht notwendigerweise binäre Kodierung ja Kompression wird jetzt wie gesagt unsere Hauptanwendung für heute
  21. sein wer kann eigentlich sagen so in einem Satz ne so wie der partywissen Informatik was ist eigentlich Datenkompression was passiert
  22. da ja also Optimierung der Speicherung des Speicherplatz ist ich fass das mal so
  23. zusammen weil es auch nicht jeder hört was wollten sie sagen ich h gesagt dass man unnötige Daten die man anderer Stelle schon herauslesen kann weglen D
  24. Speich Vering unnötige Daten weglassen aber auch mit demselben Ziel Speicherplatz verringern genau kommt das denn vor dass man unnötige Daten hat auf
  25. dem Computer ich kann Videos erklären da wird Kompression so eingesetzt dass wenn einer Stelle ein Pixel sich für die
  26. nächsten 2 Minuten nicht verändert wird einfach nur der letzte bekannte Wert des Pixels genommen und die ganze Zeit angezeigt wurch dann weil unkfierten
  27. Video für jeden Pixel dieser farbwerticher werden würde der allerdings wenn man Pass anwendet nicht okay also ich versuch no mal ganz kurz
  28. zusammenzufassen Beispiel bei Video ein Pixel ändert sich ja nicht unbedingt ne und es gibt ein Pixel das WE ich blauer Himmel ne dann bleibt das erstmal blau
  29. vielleicht für 30 Seen und dann wäre es sozusagen überflüssig immer wieder zu sagen im nächsten Frame da ist ein blaues Pixel im nächsten Frame da ist
  30. ein blaues Pixel das kann man vermutlich geschickter machen genau das wären also so Redundanzen die man ausnutzt und dann kann man
  31. komprimieren der Begriff ist aber gar nicht so ohne ne also wenn sie jetzt vorstellen haben irgendwie eine große Datei ich deute das jetzt n mal an durch
  32. so ein Rechteck ne und dann haben Sie jetzt vielleicht ein Programm also sie kennen ja wahrscheinlich sowas wie wie gzip sezip pkzip oder wie die alle
  33. heißen ist ja oft auch eine Funktion als Teil eines Datei Explorers oder so will auch keine Werbung machen gibt genug kostenlose gute Tools ich schreib
  34. einfach mal siip ne das ist wie im Englischen da ist auch dieser Reißverschluss man man packt irgendwas zusammen es wird dadurch enger oder so
  35. das scheint hier irgendwie die wortweall mal beeinflusst zu haben ich habe aber nie Amerikaner gefragt oder ein Engländer und dann wir die Datei
  36. irgendwie kleiner ich deute das mal an durch ein klein es Rechteck ne das ist deswegen so ein bisschen schwierig
  37. weil so einfach geht's ja gar nicht ne also ich meine wir werden einfach Algorithmen kennenlernen aber ich kann das ja nicht einfach sagen ich habe ein
  38. Programm das macht aus einer großen Datei eine kleine Datei jedenfalls wenn es das immer täte ne dann könnte ich das ja auch fortsetzen ne kann ich das ja
  39. noch mal zippen oder so und dann hätte ich dann irgendwie noch kleinere Datei und selbst wenn ich sage okay das geht nur einmal ist auch dieser Vorgang schon
  40. diskutabel ne weil wenn ich jetzt alle größeren Dateien zu kleineren Dateien machen kann dann merken sie das ist so ein
  41. mathematischer Widerspruch weil es gibt ja viel mehr bitstrings einer großen Länge ne als bitstrings einer kleineren Länge oder auch beitfolgen wie auch
  42. immer aber das ist ja irgendwie offenkundig ich kann ja auch nicht alle zehnstelligen Zahlen auf dreistellige Zahlen abbilden ähm ich meine kann ich
  43. schon aber dann ist es nicht injektiv ne also dann kann ich das nicht rückgängig machen und wir erwarten ja dass wir das wieder rückgängig machen können also
  44. wieder die ganze Datei erhalten ja wer kann denn das Auflösen ne also zum einen kann ich das mehrfach machen oder zum anderen warum ist es dann in der Praxis
  45. doch kein Widerspruch warum kann ich überhaupt aus großen Dateien kleinere machen ohne sozusagen die Mathematik zu verletzen dass ich dann ja viel zu viele
  46. Dateien habe die ich auch viel zu wenige abbilde was ist denn sozusagen die Idee was ist der Trick warum das praktisch nicht weiter schwierig ist ne man guckt
  47. erstmal theoretisch drauf und muss überlegen woran es denn liegt kann das jemand trauen Sie sich ruhig erwte jetzt hier bestimmt keine
  48. perfekte Antwort ja vi man dietionsverfen wieder rückgängig anwenden kann also wenn man den Weg der Kompression KT kann man wieder rüwär
  49. gehen genau also man muss die das Kompressionsverfahren grundsätzlich in beide Richtungen durchführen können ja aber wie können sie denn dann
  50. die diesen scheinbaren Widerspruch auflösen dass aber aus einer großen Datei nicht immer eine kleinere werden kann ne
  51. ja es gibt mehr Zeichen der kleineren ah das wir tatsächlich denkbar also wenn wir jetzt hier z.B sagen wir mal also ich ma jetzt mal ganz einfaches Beispiel
  52. wir hätten jetzt hier was ich beides wäre Unicode hätten wir nur A und B drin und in der kleineren Datei würden wir viel mehr Zeichen
  53. verwenden genau das das würde gehen also man kann sicherlich große Dateien die nur aus as und Ben bestehen aus a und BS bestehen auf jeweils kleinere übersetzen
  54. die dann den Zeichenvorrat ausnutzen ja allerdings ist das nürlich eine also das Beispiel wäre soweit okay aber können wir das allgemein für Dateien so sagen
  55. dass die potentialauweis weil sie den zeichenverrat nicht gut ausnutzen das äh mag so sein ne also
  56. sicherlich das war ein Teilaspekt ja ich frag mal umgekehrt vielleicht kommen wir dann der Lösung näher gibt's denn Dateien die man nicht oder nicht
  57. gut komprimieren kann einige nicken jetzt genau Beispiele ja wenn bei der Videodatei bleiben
  58. wes die kann man nicht gut kompromieren meinen sie ja ich also sein Beispiel war eine Videodatei wo Jes Frame andere Information hat aber
  59. jetzt noti mal gut komprimierbar das Wort li wir jetzt nicht ganz so leicht von der Hand ne und
  60. sozusagen schlecht komprimierbar also zunächst mal wir festgestellt also Videodaten eher gut also Ausnahmen gibt vielleicht
  61. immer also Videodaten und ihr Beispiel Frame wo sich alles ändert ähm kann man das irgendwie so beschreiben in einem Adjektiv oder vielleicht finden Sie
  62. andere Daten mit demselben Effekt ne im Video ist es tatsächlich jetzt sehr schwierig den Fall so zu beschreiben jetzt so ganz ohne
  63. Vorkenntnisse aber wir können erstmal allgemein sammeln also allgemein sind Videodaten gut komprimierbar Ausnahmen kann man sich vorstellen was ist denn
  64. allgemein auch noch gut oder nicht so gut ja prrm mhm also mein sie jetzt Maschinensprache oder Quellcode
  65. oder ich WE bei qucode aber ich vorstellen also Quellcode ist tatsächlich komprimierbar in der aller
  66. Regel das ist würde ich jetzt nicht würde ich jetzt sehr ungern da unten reinschreiben D wäre schon besonderer Quellcode also
  67. jetzt nicht so stark wie jetzt andere Beispiele die vielleicht haben sehr würde ich nicht selber die die Beispiele sie noch ein bisschen brainstormen
  68. lassen Maschinensprache da schon eher aber das das ist jetzt so ein bisschen speziell da ich will nicht zu sehr in so eine nebendiskussion aber da sind sie
  69. schon näher dran also Quellkode ist im Allgemeinen auch größer als die Maschinensprache wenn das Z empler wä wäre das ja auch wie so ein Packer also
  70. wie also Packer ist dasselbe wie so ein sipper oder eben so so ein Programm was komprimiert ne dann kann ich es auch wieder disassemblieren hätte wieder den
  71. Quellcode aber das ist jetzt auch eine sehr spezielle Sache mit der Maschinensprache deswegen den den Exkurs machen mal lieber zu was ist denn noch
  72. schlecht komprimierbar vielleicht finden wir noch mehr Beispiele die jetzt für viele leicht verständlich sind ja schon
  73. vorenform genau dieses vorkomprimierte vorkom das ist ja auch mal ein Wort vorkomprimierte Dateien schreibe ich jetzt
  74. mal genau das heißt das was ich hier so geschrieben hat das geht tatsächlich in der Praxis nicht also ich habe immer solche
  75. Aussagen jetzt das ist so sag diese 95% aufwärtsaussagen es gibt immer Ausnahmen oder vielleicht geht noch ein bisschen komprimierbar aber erstmal
  76. geht's nur einmal richtig und danach praktisch nicht mehr noch ganz ganz gering vielleicht muss ich Verfahren noch mal ändern dann kann man vielleicht
  77. noch ein paar Prozente rausholen aber generell geht's nur einmal also das merken wir schon mal genau vorkomprimierte Daten sind
  78. schlecht komprimierbar kann das jemand abstrahieren welche Eigenschaft haben den vorkomprimiert od allgemein komprimierte Daten die jetzt sich
  79. negativ auswirken auf die Komprimierbarkeit ja keine Redundanzen war oben auch eine Meldung son sammel ich das mal Nein oder
  80. hier noch mal ja gerade gemint hat z.B die hintergrunddateien also wenn ler bei ist wo einfach nur Weier scen ist würde der
  81. Weg mhm also sag mal Redundanzen sind gut das kann man dann oben aufführen also gut im Sinne von komprimierbar
  82. Redundanzen die sind oft schlecht weil sie Speicherplatz verschwenden was sie auch andeutet ich habe manchmal sowas wie Dateien die irgendwie Platz
  83. verschwenden weil sie solche Redundanzen eben haben als Überschrift besser kennzeichnen und das andere also wenig Redundanz gut jetzt wenn ich
  84. das jetzt hier einfach negiere ist natürlich einfach aber versuch noch so ein bisschen was rauszukitzeln ne das gibt's auch bei Filmdaten das
  85. gibt's auch bei Audio haben noch gar nicht genannt aber das gilt dasselbe Videodaten Audio aber welche Eigenschaft von dem Audio da ist der
  86. Begriff auch glaube ich noch geläufiger bei Videos kommt aber auch vor oder auch bei anderen Dateien da gibt's wieder einen anderen Begriff der so ähnlich ist
  87. macht das denn schlecht macht es wenig redundant ja genau das sind die beiden also Rauschen und Zufall also bei Audio Video
  88. sprechen wir oft von Rauschen es gibt auch eine allgemeine signaltheorie und und Informationstheorie ich will da aber
  89. nicht zu tief rein ich will nur sagen falls da jemand Vorkenntnisse hat viicht auch jemand schon mal Nachrichtentechnik studiert dann denkt er sich gerade oh da
  90. gibt's aber noch viel mehr das stimmt aber genau wenn etwas rauscht dann dann flackern ja auch diese Pixel haben wir das gerade gerade nicht ne dass dass der
  91. Himmel an einer Stelle immer denelben Blauton hat ne dann bewegt sich das sozusagen im Farbraum zufällig hin und her das war sehr vereinfacht
  92. dargestelltes Rauschen allgemein eben Zufall oder auch pseude zufällige Daten genau also das heißt wenn die wenn die bit da so wild zufällig ausgewählt
  93. erscheinen können Sie die Datei regelmäßig nicht komprimieren sie werden dann den Algorithmus auch nicht finden der
  94. seinerseits herausfindet mit welchem Algorithmus diese Daten erzeugt worden sind wenn dann geht das natürlich W wir z die Nachkommstellen von PI nehmen ne
  95. die sind ja mit äußerem Blick Zufallszahlen aber es sind natürlich keine Zufallszahlen weil es ist ja immer die nächste Nachkommastelle ne das heißt
  96. wenn ein ein ein so ein Packprogramm das das merken würde okay das die nachkommstelle von P dann kann man das irgendwie beschreiben ne dann kann man
  97. da megabyteweise zusammenfassen ganz kurz aber das ist natürlich fast nie der Fall ne dass man so so ein Muster so erkennt gerade wenn es so zufällig
  98. aussieht und also all das was zufällig ste zufällig ist was rauscht kann man nicht komprimieren und dann merken sie damit wie die scheinbare Widerspruch
  99. auch aufgelöst die allermeisten Dateien haben natürlich keine Redundanz ne also wenn ich jetzt zufällig eine Datei quasi ziehech ein Münzwurf oder so dann ist
  100. die ja genau das ne äh dann enthält die zufällige Daten und dann wird sich das Packprogramm der sipper das Komprimierungsprogramm dann eben die
  101. zehne ausweißen das erstmal nur so als als Grundidee dass wir wissen worüber wir sprechen also wir können komprimieren aber wir brauchen dazu
  102. Voraussetzungen die Dateien mit dem man aber in der Realität oft zu tun hat haben offenbal diese Voraussetzungen sonst würden wir das nicht dauernd
  103. anwenden übrigens nicht nur bei der Speicherung auch bei der Datenübertragung ist das natürlich genauso wichtig aber ich denke das ist
  104. ih auch sofort geläufig okay also hier ist das noch mal als Definition ne wir können komprimieren das nennt man Datenkompression also letztlich ist das
  105. ein Algorithmus ein digitales Verfahren um Speicherplatz zu reduzieren ne oder wenn wir Übertragung denken also Daten in transit dann geht es darum die Zeit
  106. zu verkürzen und wie sie schon sagt das steht hier auf der Folie so Videodaten und allgemein audioovisuelle Daten sind
  107. gut komprimierbar ne weil da offenbar sich dann doch einiges so wiederholt wenn man das so pixelweise betrachtet ne und solche redondanzen kann man dann
  108. erkennen da gibt's natürlich Algorithmen und dann sind die nicht so extrem riesengroß also das das kann ja einmal ganz schnell die ganze Festplatte füllen
  109. wenn wir so mit höchster Auflösung stundenlang da Pixel übertragen da gibt es also harte Anforderungen oft dass man diese Datenmenge reduzieren
  110. muss die neue Datei die herauskommt muss aber eine prentation der Daten sein ne das heißt wie sie schon sagten es muss auch in die andere Richtung wieder gehen
  111. ne also mathematisch sagen wir das ist dann injektiv also es muss auch ein Ansip geben z.B und weil sonst wäre das ja auch Quatsch ne also wenn ich die
  112. nicht zurückholen könnte habe ich ja nicht viel gewonnen die Idee ist ja dass ich speicherblatt spare aber nicht dass ich Datein verliere ne da wir inzwischen
  113. gerade im Bereich aUDIO VIDEO aber manchmal kom machen wurden noch diese Begriffe eingeführt also ganz allgemein ist Komprimierung die sogenannte
  114. verlustfreie Komprimierung ne das heißt beim entkomprimieren beim auspacken muss ich Bit für Bit Bit für bit exakt die Dateien wiederkriegen auch kein
  115. Kompromiss also stellen sich vor dass wir Maschinensprache und ab und zu fehlt ein Bit oder so das Programm wäre gar nicht mehr ausführbar wde quasi sofort
  116. Abstürzen ne also wir erwarten dass das hier wirklich fehlerfrei ist dass nicht ein einziges Bit auch nur giipt aber das können natürlich erfahren im Bereich
  117. aUDIO VIDEO da muss man nicht ganz so streng sein weil es ist ja nicht Maschinensprache die wir ausführen sondern wir gucken ja nur oder wir hören
  118. ja nur und dann kann man nich dadurch Daten sparen dass wir sagen das ist für den Menschen gut genug oder es ist sogar für den Menschen ununterscheidbar vom
  119. Original das ist so das Ziel das hat man z bei bei MP3 zumindestens angestrebt kann man lange diskutieren ob das erzielt wurde einige schwören ja da
  120. drauf die hören immer noch Unterschiede unter Laborbedingungen sind es dann immer sehr viel weniger kann ich schon mal sagen aber das ist eine Diskussion
  121. für sich ne also Audio Freaks haben da sicherlich ihre Meinung die benutzen auch goldene Kabel um ippakete zu übertragen oder so die kann ich auch
  122. nicht alle ernst nehmen in der Community aber generell kann man natürlich dort tatsächlich auch Verluste hinnehmen wenn es eben wie gesagt gut genug ist
  123. oder vielleicht die Auflösung verringern wenn jetzt nur ein Videotelefonat ist brauche ich vielleicht auch nicht so viel Klarheit wie es jetzt wäre wenn ich
  124. ein Hollywood Film streame für den ich vielleicht auchch gerade bezahlt habe ne also das wären dann erlaubte Verluste oder allgemein eben das wäre eine
  125. verlustfreie kom eine nicht verlustfreie als eine verlustbehaftete Komprimierung entschuldigung aber jetzt für uns bis auf weiteres wir haben noch das
  126. Kapitel Computergrafik später wo wir da kurz reingucken wollen wir jetzt alles hier verlustfrei haben
  127. bei Grafiken kann man auch noch mal überlegen je nachdem wie man die vektoriell darstellt oder rendert ist es da auch möglich
  128. ein ein Verlust hinzunehmen ohne dass der Mensch dadurch ein Nachteil hat genau und diese Packprogramme habe ich hier genannt also die heißen alle
  129. irgendwie so ne siip oder RA TGZ so Kommandozeilen Umfeld hat glaube ich jeder schon mal benutzt meistens reicht das so die
  130. rechte Maustaste oder so wenn Sie eine haben und dann gibt's meistens so ein Menüpunkt dass ich irgendwas m Archiv hinzufüge
  131. genau der Archivierung fällt das auch oft wobei es gefährlich ist die Begriffe zu verwechseln deswegen sagen wir eindeutig
  132. Datenkompression ja und die einfachste Methode ist eben die Wiederholung zu erkennen ne wie sie schon sagten ein Pixel wiederholt sich immer wieder Bild
  133. für Bild ne das passiert nicht nur Bild für Bild sonder auch innerhalb eines Bildes gerade wenn z.B maschinell generierte Bilder sind wiederholt sich
  134. natürlich dauernd ein Pixel ne also das wird schon fast langweilig wenn man das guckt sich anschaut auf Dateiebene so Beit für Beit hat man Eindruck da
  135. passiert ganz lange nichts können Sie kilobyweise immer wieder dieselbe Zahl lesen oder so und das motiviert eben so das einfachste
  136. Komprimierungsverfahren was man sich so ausdenken kann das was wir auch ansonsten alss als Mensch verwenden selbst wenn wir jetzt nicht
  137. programmieren selbst wenn wir nicht mit digitalen Systemen arbeiten kommt das da ja mal vor ne dass wir sagen ich habe hier eine ein mit 100
  138. Null z.B ne das ist dieses Beispiel auch auf der Folie ne also 2 hoch 100 binär ne das ist n ein mit 100 Null oder 10 hoch 100 dezimal ist eine ein mit 100
  139. Null und das kanönnte ich ausschreiben ich sage ah das Ergebnis ist 1 und so weiter könnte die 100 Nullen aufzählen ne das dauert aber nicht nur
  140. länger sonst wde auch mehr Speicherplatz oder ne wenn ich es aufschreibe mehr mehr Papier verbrauchen als wenn ich es einfach
  141. beschreibe wä es möglich dass sie sich nicht weiter hier drin unterhalten ich habe ihr Gespräche schon längere im Ohr ne also wir ist noch ganz
  142. nah an der Tür sonst können sie draußen die Besprechung machen genau also das wä eine Eins mit 10 Null und da ist die textuelle Beschreibung schon mal kürzer
  143. ne ohne da jetzt ein großen Algorithmus draus zuachchen als das Ausschreiben dieser viehel null okay also das wäre die
  144. lauflngencodierung das kann ich als Algorithmus natürlich auch fassen dass ich sage Nut folgen was ist ich 10 Bytes mit dem Wert 0 danach 5 byes mit dem
  145. Wert 255 oder so ich muss diese Eigenschaft das will ich natürich nicht immer so im deutschen oder englischen Satz schreiben diese muss ich eben
  146. möglichst geschickt oder kurz darstellen ne und wenn ich das mal festgelegt habe dann besteht eine Datei nicht mehr aus derer Folge von bites ne sondern nach
  147. der Komprimierung aus einer Folge von Lauflängen und hier ist es mal ganz konkret ne also sie sehen wenn die Farben bei ihn halbwegs auch rüberkommen
  148. beim B immer so eine Sache im Schwarz die also in schwarzer Farbe die unkomprimierten Daten und die Semantik ist jetzt völlig egal das kann jetzt
  149. Teil einer Grafik sein eines Audios oder vielleicht auch menschlicher Text oder so also menschenlesbarer Text F0 F0 F0 f1080808 was wir merken hier gibt offen
  150. Wiederholungen ne und die lauflängencodierung funktioniert eben so dass wir einfach sagen dann machen wir mal paarweise eine Beschreibung dann
  151. schreiben wir 03 F0 01 F1 ich betone das jetzt so stark damit Sie es direkt erkennen ne 06 08 ne 01 05 also da ist immer die Anzahl dazu gesagt also statt
  152. dreimal F0 zu schreiben dass es jetzt hexadezimal ist die bites können sie ignorieren das macht es aber einfach schöner beim auf schreiben äh da hat man
  153. immer zweistellige Werte deswegen nimt man das da gerne also statt F0 F0 F0 schreibe ich 03 F0 also dreimal das bite F0 und statt diese vielen mal 08 ich
  154. glaub sechs Stück sind's genau sechs Stück schreibe ich eben 06 08 ne dann habe ich auch ordentlich gespart ne also ich aus 6 x 08 also 6
  155. Bytes habe ich 2wei bites gemacht also zwei Drittel gespart das ist schon viel wir merken aber auchfahren hat hat hier einen Nachteil ähm manche bites kommen
  156. dann eben doch nicht als Lauflänge vor oder eben als Länge 1 nur vor wie die F1 hier im Beispiel und da muss ich schreiben 01 F1 das heißt in dem Fall
  157. verdoppelt sich sogar die äh die Anzahl von bals zur Speicherung das Verfahren äh hängt also in seiner Wirksamkeit davon ab dass das nicht allzu häufig
  158. vorkommt dass bit auch einzeln in dieser Folge sind also eben keine Folge sind sondern so also Einzelfolgen darstellen ne und ähm das sehen wir auch im
  159. Ergebnis also ich habe da was gespart ne aber zwischendurch habe ich dann auch ein bisschen was verschwendet es ist offenbar ein
  160. Verfahren das jetzt bei vielen Daten auch nicht gut funktionieren würde selbst wenn es Redundanzen gäbe sie hat noch Beispiele genannt jetzt wie z.B
  161. Quellcode oder so da kommt natürlich selten vor dass jetzt ein Schlüsselwort z.B jetzt vi a hintereinander hat oder so ne also kann mal vielleicht sowas wie
  162. space und Tab oder so das das könnte noch was sein was wirklich häufig htereinander vorkommt der Rest aber eher nicht so das heißt diese Redundanzen
  163. eines Java quellcods oder so kriegt man damit wahrscheinlich nicht so gut hin aber es ist auch wie gesagt das einfachste Verfahren also das was man
  164. sofort versteht das können Sie direkt runter programmieren ne mit einem Java prramm diese bites lesen und dann komprimiert ausgeben also ja viel
  165. einfacher kann ich mir nicht vorstellen jedenfalls ne und jetzt kann man anfangen zu optimieren wir machen das jetzt nicht beliebig weit aber dass man
  166. man so erkennt was sind denn jetzt Möglichkeiten ein richtiges ein komplexeres Komprimierungsverfahren hier zu konstruieren z.B diese einzelnen
  167. bites wenn die mich stören kann ich auch sagen nee dann mache ich das auch nicht so dass ich im schreibe jetzt habe ich einmal eine F1 ich ma das umgekehrt wenn
  168. ein Bit einfach so da steht dann ist es das bald ne und wenn es eine Lauflänge gibt von viel bit das ist ja sousag die Hoffnung dabei vielleicht erwische ich
  169. mal 100 oder sogar Taus mal dasselbe bit vielleicht am Anfang am Ende ein der Datei oder eine Tabelle oder so wo die Werte plötzlich wegfallen ne dann habe
  170. ich so markarbeit und das sagt eben achtung jetzt kommt eine Folge dadurch werden die Folgen natürlich länger weil die immer mit einer markarbeit
  171. eingeleitet werden müssen aber auf der Habenseite die einzelnen bites bleiben einzelne bites und dann wä das die Hoffnung dass
  172. das typische Daten der Realität eben ein Vorteil bringt beim Quellcode oder so wäre das sicherlich ein großer Vorteil dann würde man wirklich nur diese wenn
  173. das eben spaces z.B sind die da großer Folge auftreten würde man nur auf diese quasi jagen und die dann entsprechend verkürzen also hier daselbe Beispiel mit
  174. markarbeit da steht D FF 03 F0 dieses FF ist eben das die die Markierung achtung es kommt eine Folge und dann eine Folge von dal
  175. F0 dann kommt F1 f für sich ne also F1 ist F1 da wird nicht komprimiert aber es wird auch nicht größer aufgrund irgendeines Overheads ne dann kommt
  176. wieder FF 0608 ne also eine Markierung achtung jetzt kommen se mal se mal kommt das Bit mit dem Wert 8 also hexadezimal 08 was aber auch sonst das war die
  177. Nummer 8 wäre ne und so weiter ne zum Schluss sehen sie noch mal FF 0300 also am Schluss sind 30 beits ne das wäre also in einigen Fällen
  178. besser in anderen vielleicht nicht hier konkret in dem Beispiel war es jetzt wieder sogar Beit länger es hat sich also nicht so ganz gelohnt ne es lohnt
  179. sich eben vor allem wenn da mal eine längere Folge kommt oder so ne okay aber ne daran könnte man eben drehen man könnte das weit identifizieren was jetzt
  180. hier Gründe sein könnten Redundanzen zu erkennen vielleicht sag do jemand na vielleicht sollte ich eher nach deutschen Worten oder nach nach
  181. doppelbeit suchen weil die sich eher wiederholen ne das kann auch sein z.B UTF wäre ne dann wä es vielleicht besser das jeweils für zwei bites zu machen ne
  182. aber das wären eben solche Gedanken da müsste ich mich mit den Daten weiter auseinandersetzen und so ein bisschen feilen an diesem Verfahren aber es ist
  183. eben eine ansonsten brauchbare Methode leicht zu erlernen und auch offenbar hier auch zu dekodieren also ich kann auch entkomprimieren ohne dass
  184. hier irgendwas verlustig geht weil man ja versteht welche Zeichenfolge hier beabsichtigt war hier das ist mal ein Beispiel dafür wann lohnt sich überhaupt
  185. eine lauflängencodierung für Quellcode haben wir schon gesagt eher nicht für Maschinensprache haben sie jetzt auch eine gewisse Vorstellung eher auch nicht
  186. ne also ich obcode Parameter ist doch selten dass ich das alles mal HT Mal wiederholt oder so ne aber es gibt ja Grafiken wo tatsächlich sehr wenig
  187. passiert ne ich sagte ja vorhin schon maschinell erstellte Grafiken also weniger das verrauschte Foto vom Sonnenuntergang was Sie vielleicht im
  188. Urlaub machen oder so ne aber wir haben ja auch in der gerade jetzt in der digitalen Welt sehr viele so Icons Piktogramme also super simple Grafiken
  189. die aber auch sehr wichtig sind ne also um z.B was ich Buttons zu beschriften oder eine Funktion eben die ich mit Finger anchippe zu erkennen also oft
  190. haben sie so eine Komplexität wie dieses Beispiel al ich ein senkrechter Strich heißt das irgendwas ne also das ist jetzt völlig abstrakter Strich aber sie
  191. wissen es gibt solche Symbole Z ein und ausschalten manchmal nur so ein Strich oder so halbe eine halbe Rundung noch drüber ne oder auch so verkehrschilder
  192. z.B ne also wenn ich so ein Stoppschild oder so als Grafik dann im Computer entwerfen und das pixelweise betrachten D sehen Sie okay da kommen jetzt ganz
  193. viele rote Pixel ne und dann wieder ganz viele äh weiße ne man Wort Stopp ist doch weiß oder kann überlegen man sieht jeden Tag aber äh sich ja gar nicht
  194. sicher wenn man es gerade nicht vor Augen hat ne aber jedenfalls da gibt's nicht so viele Farben und es gibt sehr große Flächen buchstäblich groß damit
  195. man es auch aus der Entfernung erkennt ne und solche Grafiken ne die kann ich tatsächlich sehr gut komprimieren dazu muss ich erstmal aber wissen eine Grafik
  196. besteht aus Pixeln den Begriff kläme noch mal etwas genauer aber wie gesagt wir haben noch mal so ein kurzes Kapitel Computergrafik
  197. das stelle ich jetzt also mal zurück jeder von ihnen weiß aber ungefähr was ein Pixel ist stellen sich einfach ein kleines Quadrat vor aus dem die Grafiken
  198. aufgebaut sind bis auf weiteres reicht das ne und dann wird das wird so eine Grafik aufgezählt und da hat man mal festgelegt das macht man so
  199. ähnlich wie beim Schreiben also von links nach rechts und von oben nach unten so zeilenweise ne und jetzt kann ich ja mal überlegen wie könn ich so
  200. eine Grafik codieren wie diesen schwarzen senkrechten Strich auf gelben Grund ist jetzt einfach mal festgelegt das ist ein Piktogramm ne so ein kleines
  201. Icon 128 x 128 Pixel also wirklich klein fast alles gelbe Pixel und eben der Strich mit schwarz Z Pixeln ne und wir kümmern uns jetzt nicht weiter um
  202. das Grafikformat wir müssen aber jetzt einfach fürs fürs codieren gelb ist A0 und schwarz ist 00 jedes Pixel soll jetzt hier genau ein Bit haben ne sonst
  203. kann man das Verfahren aber natürlich auch abstrahieren und auch auf 16 32 B natürlich übertragen und noch diese Pixel zählen aber der Kern ist derselbe
  204. wir machen das jetzt mit bites da hab ist jetzt auch gerade so schön eingeführt okay es gibt bites mit A0 und es gibt bites mit null ull ne also mit
  205. gelb und mit schwarz und wenn ich oben links anfange ja habe ich erstmal die erste Zeile 128 gelbe Pixel und dann kommen noch mal 128 gelbe
  206. Pixel ne eine Festlegung die wir treffen können bei der lauflengcodierung da 00 als lauflenge Al jetzt hier ohne markarbeit ne 00 als
  207. Lauflänge macht keinen Sinn als zu sagen jetzt kommt Null mal irgendein Wert oder so also sinnvoll ist ja nur wenn er einmal zweimal dreimal oder so vorkommt
  208. also nimmt man für 00 auf das Maximum was man sonst nicht erreichen kann also eins mehr als das sonstige maximum meine ich ne dann sagt man bei Beit das ist
  209. steht dann für 256 das ist auch gut dann habe ich so eine schöne runde Zahl weil es ist ja oft eine zweier Potenz okay also da
  210. sehen sie 00 A0 heißt also 256 gelbe Pixel und da dieses Quadrat jetzt auch eine Kantenlänge von 128 hat heißt das genau zwei Zeilen also mit
  211. zwei bites kann ich zwei Zeilen gelb machen habe ich hier gerade kein Gelb aber sie können sich das vorstellen einen senkrechten Strich ne
  212. und jetzt habe ich hier zwei Zeilen das jetzt hier mal ganz einfache Skizze zwei Zeilen
  213. entspricht 256 Pixel und das ist unkomprimiert hier auch 256
  214. Bytes bei diesem Grafikformat ne es gibt auch Grafikformate B 4 Bit für Pixel oder so aber wie gesagt das lern wir jetzt heute nicht
  215. kennen okay das heißt ne mit diesem 00 was F0 diese Farbe Gelb ne a 00 A0 kann ich also zwei zeahlen direkt codieren weil da nichts passiert eine wunderbare
  216. Lauflänge also solche Grafiken wie gesagt da kombinierbar mit laufläen und das kann ich noch mal machen und noch mal ich muss im Prinzip nur
  217. ausrechnen wie groß denn hier oben und unten der Abstand ist jetzt haben wir gesagt 128 das ganze ist zentriert also habe ich oben und unten 14
  218. Pixel Deut ich jetzt hier mal nur an diese diese Messung also 14 Pixel die mir oben und unten quasi fehlen die nicht schwarz sind sondern die auch gelb
  219. sind und dann ist der Rest so ein bisschen Rechnerei ne also 00 A00 a habe ich vi noch mal habe ich 6 und so weiter und insgesamt brauche ich 14 gelbe
  220. Zeilen ne weil oben und unten 14 wie schon vorgerechnet ne und dann habe ich bei der 15 Zeile ne also ne also wie gesagt von wenn ich das
  221. von 0 bis 13 mache oder so jetzt hier nichts verwechseln aber ist auf jeden Fall eine gerade Anzahl oben oder unten ne nicht dass sie hier so ein off by one
  222. problem haben jedenfalls in der dann folgenden 15 Zeile ne da geht ja auch noch mit Gelb los bis ich die beiden schwarzen Pixel erwische ne das heißt
  223. auch noch ein bisschen gelb ne das muss ich einmal ausrechnen und dann komme ich eben auf 63 gelbe Pixel und das entspricht dann offenbar wo steht's 3F
  224. A0 ne also 3F ist offenbar die 63 ja kommt do hin 40 64 genau ne also 3f0 noch mal für die 63 gelben Pixel dann kommt das eigentliche Objekt ne das hat
  225. die breite 2 weil das Beispiel ist einfach mal so festlegt breite 2 Pixel da sehen sie 0200 ne und das wiederholt sich ne jetzt jeweils über ein Rand ne
  226. also 63 rechts und dann Zeilenwechsel wieder 63 links ne also macht dann 126 oder 7e und bis dieser ganze schwarze
  227. Streifen voll ist ne also das muss ich dann sozusagen 100 mal wiederholen immer dieser Wechsel von schwarz auf gelb und unten ist dasselbe wie oben habe ich
  228. wieder 14 Zeilen gelbe Pixel und dieser Rest W das jetzt so ein bisschen zu schnell ging aber sagen wir mal dass man das schnell ausrechnen kann vielleicht
  229. mal sich Taschenrechner ansonsten so g das ist ihn unmittelbar klar wenn Sie wissen okay eine Grafik klar von oben links nach unten rechts wenn die Pixel
  230. aufgezählt und D muss ich halt gucken wie oft es zu diesem Wechsel kommt zwischen gelb und schwarz das Aufzählen und dann habe ich meine Lauflängen und
  231. wenn ich das alles so runterschreibe kommt man dann auf 430 Bytes also waren offenbar 215 Lauflängen am schlechtesten lief das so
  232. mit den schwarzen Pixel es immer zwei war da kann ich nichtich sparen wenn ich sage zweimal das beid Null h direkt 0000 schreiben können okay aber hat das jetzt
  233. hier nicht weiter verschlechtert ne aber aufgrund dieser extrem vielen gelben Pixel war die lauflängencodierung hier Gold richtig ich habe also 430 byes
  234. anstatt 16384 byes ne wenn man das mal so vor Augen sieh wow das ist ja enorm das ist ungefähr ein 32 ne also wenn sagen
  235. weniger als 512 ne also habe ich jetzt hier so im Kopf 97% etwa eingespart also eine
  236. wahnsinnskompression bei diese Art von Daten scheint sich das sehr stark zu lohnen ne dasel wenn ein bisschen mehr los ist ne sie haben trotzdem immer
  237. diese Lauflängen bei allem was so piktogrammartig ist und oft sind das ja noch viel größere also 128 x 128 ja heute schon sehr wenig kann das Handy ja
  238. fast gar nicht mehr so darstellen dass da noch ihre Fingerspitze drauf passt ne da hat man schnell schon mit größeren Werten zu tun ne okay also offenbar ein
  239. Beispiel was so gewählt ist dass die lauflängencodierung hier Gold richtig ist es bleibt aber natürlich dann die Frage was mache ich denn mit diesen
  240. anderen Beispielen ne wie wie Quellcode oder Maschinensprache oder Audio Video sonst wo vielleicht auch mal zwischendurch was
  241. verrauscht ist oder wo es vielleicht äh Dinge gibt die sich wiederholen aber nicht so als als Lauflänge eben wiederholen ne sondern sich vielleicht
  242. auch hin und her abwechseln das müssen wir also noch im Kopf behalten andere Idee ne wo kann ich das noch besonders gut machen
  243. wenn sie so eine Grafik wie oben rechts sehen die z.B monochrom das hat man ja auch das öfteren also dass auch Bilder vielleicht zusammengesetzt sind aus
  244. monochromen einführbildern oder dass ich wirklich irgendwo eine Art schwarzweiß Oberfläche habe ne vielleicht auch für für bei fondz oder so die werden erstmal
  245. auch definiert eben als ne schwarze Buchstaben A weißen Grund also quasi man unterscheidet einfach diese beiden Farben man legt auch gar nicht unbedingt
  246. fest dass das Schwarz oder Weiß ist das passiert dann eher wenn Sie den den Texteditor bzw wordprocessor anmachen und wenn ich sowas habe wie monochrome
  247. Grafiken ne dann muss ich auch gar nicht mehr sagen achtung jetzt kommen so viel schwarze Pixel jetzt kommen so viel weiße Pixel und so ich kann ja direkt
  248. sagen hier Moment wenn die schwarzen fertig sind dann kommen natürlich weiße weil andere habe ich ja nicht ne also ich mal bei schwarz-weiß als Beispiel
  249. und wenn die weißen wieder fertig sind kommen natürlich schwarze ne das heißt diese Information immer jetzt kommen schwarze jetzt kommen weiße jetzt kommen
  250. schwarze jetzt kommen weiße die muss ich nicht codieren die ergeben sich aus dem Kontext ich muss elich nur sagen was am Anfang ist ne und hier z. kann ich
  251. anfangen mit weißen Pixeln und dann das durchzählen ist hier so eine Art was ich Pacman Gespenst oder so W ich hier drin noch erkennen die älteren Seen das
  252. vielleicht auch da drin oder irgendwas anderes D sieht man ich 12 weiße Pixel nächste Zeile noch mal drei also macht dann 15 weiße Pixel sechs schwarze dann
  253. noch mal fünf weiße acht schwarze und so weiter und das gibt am Ende über die Lauflängen ne so eine Zahlenfolge die da ganz unten rechts steht einfach ne 15
  254. Komma und so weiter also hier habe ich offenbar eine Möglichkeit sehr viel einzusparen weil es nur zwei mögliche Farbwerte gibt ne und das natürlich gut
  255. wenn man sowas sieht wenn man das erkennt und dann richtig gut ausnutzt ne um eben ähm ja diese speichermonster auch zu
  256. vermeiden äh jetzt keine we jetzt keine Anspielung auf das Gespenst ne aber man kann eben durch durch schlechtes Speichern von von monochrom Grafiken
  257. oder halbwegs monochromfiken sehr viel Speicherplatz verschwenden und das wäre jetzt eben so ein konkretes Beispiel was man auch
  258. schon seit längerer Zeit so macht solche Grafiken eben sehr sparsam äh zu speichern weil sich einfach zwei Werte immer abwechseln D muss ich das nur
  259. einmal sagen was ich jetzt hier gleich abwechselt und legt dann eben los dann gibt es so eine zahlenf okay das wä eine weitere Modifikation der
  260. lauflängencodierung um eine besondere Effizienz für eine bestimmte Art von Grafiken zu erzeugen das versteht wohl jeder denke
  261. ich ne also vielleicht haben einige Schwierigkeiten die heute zum ersten Mal das Wort Pixel gehört haben aber ich glaub so viele gibt's da nicht jetzt ach
  262. so genau war schon nächste üersprungen ne ich habe nämlich gar nicht gedrückt wohl offenbar erwischt ja genau was wir bisher auch betrachtet haben waren eben
  263. Codes auch was wir kennengelernt haben z mit aski sind längenvariable Codes also ne wo jedes Zeichen 7 Bit oder jedes Zeichen ein Bit umfasst z.B oder bei UTF
  264. 32 jedes Zeichen eine Folge von 4er byites einnimmt das ist natürlich auch sinnvoll in vielen Kontexten aber man möchte sich
  265. auch mal offen halten dass es nicht so ist ne das nennen wir dann einen Längen varariablencode also dann hat nicht jedes äh Zeichen nachdem ich es in die
  266. codierungsfunktion gesteckt habe dieselbe Länge sondern die kann sich eben unterscheiden und das bringt aber eine
  267. Problematik mit sich ne das sehen Sie z.B oben rechts wenn ich sowas habe wie aus A wird 0 aus J wird 1 und aus z wird 100 ne dann merken sie das ist z.B nicht
  268. eindeutig ne dann würde aus ZZZ 10 wenn ich die Bitz mal so aussprechen darf ne aber auch aus Jazz würde 10 10
  269. ne oder aus zzja würde 101 also so geht's irgendwie nicht ne also wenn ich das längvariable machen dann muss ich schon noch der Lage sein das auch wieder
  270. zu dekodieren ne das war bei gleich langen Längen kein Problem ne hier wä es auf einmal Problem weil ich kann der eins nicht ansehen ob das die ein ist
  271. oder der Beginn der 100 ist ne und daraus ergibt sich hier eben so eine Mehrdeutigkeit ne das Problem ist nich auch sag mal schnell zu erkennen ne z.B
  272. hat man es auch gelöst für für den Morse code ne also sie wissen es gab eine bedeutende Erfindung im 19 Jahrhundert sozusagen die erste Form der
  273. systematischen Datenübertragung damit Telegraph ne und da hat man eben diesen Code entwickelt später auch für Funknetze verwendet ne und da hat sich
  274. der Erfinder z.B auch überlegt dass es ganz sinnvoll ist dass nicht jedes Zeichen gleich lang ist weil einige kommen ja häufiger vor also das
  275. ist eine sehr wichtige Idee ne die da auch sehr viel gespart hat an Übertragungszeit später im englischen z.B ähnlich wie im Deutschen ist das E
  276. der häufigste Buchstabe deswegen wird e mit dem Zeichen kurzen gibt's lang und kurz also letztlich wie lange man so diesen Taster drückt und da waren jetzt
  277. keine Computer beteiligt immer ein Mensch der mit seinem Zeigefinger das gemacht hat und einmal kurz ist sozusagen das das kürzeste denk
  278. also in Zeiteinheiten das kürzeste überhaupt ne das hat man nürlich fürs e genommen ne oder was auch noch häufig ist ist n das ist d lang kurz O ist
  279. schon vergleichsweise weniger häufig ne da hat man schon lang Lang Lang genommen ne und ja so nach und nach eben diesen Code
  280. aufgebaut ne K konnte jetzt nicht jede Entscheidung D nachvollziehen aber er hat offenbar auch Textfragmente für ausgewertet wo dann dieser Code sich als
  281. gut geeignet dargestellt hat allerdings wenn Sie genau drauf gucken merken Sie hier Moment das ist ja das gleiche wie oben rechts ne aber oben rechts war ja
  282. offenkundig unsinnig der Mors Code hat bestand also wurde damals sehr stark benutzt im Prinzip wird er bis heute benutzt der Anwendungsbereich ist nur
  283. weggefallen aufgrund von vielen digitalen Systemen aber ich GL wer Kapitän ist oder so glaube ich muss auch heute noch morsen können das kann man ja
  284. auch mit mit Scheinwerfern machen also auch mit anderen Übertragungsmöglichkeiten da ist schon noch wichtig ne s wissen dieses SOS ne
  285. also kurz kurz kurz Lang Lang Lang kurz kurz kurz das kommt eben auch daher und das wäre sogar gut wenn das jeder kennt das können Sie auch im Autoscheinwerfer
  286. machen wenn sie irgendwo in Not sind ja und deswegen musste man hier dieses Problem lösen weil einmal kurz kann eben ein E sein
  287. einmal kurz kann auch sein das ist ein i ne also aber es ist ein Unterschied ob es EE oder ein i ist ne wissen Sie wie man das macht da steht schon auf der
  288. Folie dann kann ich auch direkt verraten ich glaub steht nicht da wie löst man das Problem beim morsen die Folie nicht vor Augen aber
  289. sonst sagen Sie es direkt ja dur durch Pausen genau also relativ einfacher Gedanke zwischen bei zwischen zwei Buchstaben macht der Mensch eben eine
  290. kurze Pause übrigens extrem kurz ne also das was man gerade so mit den Muskeln machen kann und später hört ne aber tatsächlich kann Mensch bei regelmäßigen
  291. musern auch sehr kurze Pausen heraushören will jetzt nicht schätzen mal sagen vi Zehntel Sekunden Pausen oder so aber jeden Fall extrem kurz man
  292. sonst denken würde wow das klingt so maschinell aber das können auch Menschen aber müsst jetzt mal profiunker fragen was da so aktuelle Werte sind gibt
  293. wahrscheinlich nicht mehr allzu viele hauptberufliche morser heutzutage dass S die Werte wahrscheinlich auch wieder angewachsen also der Morse code ist eben
  294. kein binärer Code in irgendeiner Hinsicht es sind drei also kurz lang und Pause sonst könnte man hier nicht dekodieren und die
  295. Buchstaben wieder gewinnen das muss man wissen und macht aber auch ansonsten keinen Sinn ne sonst hätte man diesen Unsinn wie oben rechts wo man ja
  296. auf einem Blick sieht das kann ja gar nicht klappen okay also kurz können längenvariabel sein aber dann muss ich stärker drauf achten dass diese
  297. injektivität eben gewährleistet ist also dass ich sie umkehren kann die Funktion und die Originaldaten auch unverfälscht wieder
  298. erhalte das kriegen wir aber hin das steh dazu eignen sich Trennzeichen ne also Trennzeichen ist das was die Pause wäre e Morse code ich we nicht ganz
  299. sicher Wort Pause steht eben nicht da und wenn kein Zeichen der Beginn eines anderen Zeichens ist dann ist offenbar diese injektivität erfüllt ne dann kann
  300. ich das nicht verwechseln dann weiß ich sofort okay hier ist ein Zeichen das ist fertig das kann ich breifix eines ander Zeichens sein ich kann es also
  301. rausschreiben deswegen heißt es auch prfriixfreie Codierung also das ist eine positive Eigenschaft die macht uns das Dekodieren viel einfacher und auch in
  302. dem Fall macht sie es auch eindeutig ne es gibt auch nicht präfixfreie eindeutige Codes aber dann brauche ich eben ja komplexere Strategien beim
  303. dekodieren genau was wir eben beim Mors Code schon gesehen hatten das E ist häufig deswegen hat das E ein kurzes Codewort ne äh das ist natürlich eine
  304. allgemeine Eigenschaft die wir bei Dateien oder bei anderen komprimierungsobjekten eben auch ausnutzen möchten ne das nennt man dann
  305. auch diese entropieeigenschaft ne also manche Dinge sind häufiger oder man sagt die die Wahrscheinlichkeit dass sie auftreten ist geringer ne und andere
  306. sind eben seltener ne und äh das kann ich eben bei einem nichtlängen fixen Code also bei dem Längen varariablencode ausnutzen dann
  307. gebe ich natürlich Dinge die häufiger sind kurz Codewörter ne und das muss wohl effizienter sein als wenn ich umgekehrt machen würde also habe ich
  308. damit schon die Möglichkeit zu komprimieren ne das ist so die Idee wir hatten das bei den Nummernschildern schon gesehen deswegen haben die
  309. Großstädte ein Buchstaben weil die sind sehr häufig diese Nummernschilder ne und dann habe ich auch mehr Platz für die
  310. Unterscheidung der einzelnen Fahrzeuge ne also der Gedanke liegt da sehr nah da würde man vielleicht jetzt gar nicht von Entropie sprechen ne aber das ist
  311. letztlich die die gleiche Konstruktion also häufig vorkommende Nummernschilder haben dann eben einen entsprechend kurzen städtischen Code ne oder oder
  312. kreiscode bis auf diese Ausnahmen die Hamburg und so weiter die unbedingt zwei Buchstaben haben wollten und das ergibt auch direkt komimierungsverfahren ich
  313. kann einfach sagen ich mach das Präfix frei das häufigste Zeichen bekommt das eins bit also geht jetzt wohlgemerkt um Bits nicht um Beit ne das ein Bit das
  314. zweithäufigste Zeichen ne bekommt das 01 diese bit Folge das dritthäufigste Zeichen 001 und so weiter ne und damit hat dann später jedes Zeichen wirklich
  315. eine andere Länge gut beim letzten kann ich das noch machen dass wenn ich damit aufhöre muss ich am Ende keine eins mehr dran schreiben D kann ich auch nur Null
  316. nehmen es bleibt dann Präfix frei das ist hier noch so die extremste Optimierung die man noch machen kann davon abgesehen bis auf diese Nullfolge
  317. haben wirklich alle diese Zeichen dann verschiedene Bitlänge und wenn ich das dann speichere in der Datei muss ich auch später diese Bits da wieder
  318. rausschneiden ne weil die sind jetzt nicht genau auf beitgrenzen das ist also arbeitsaufwendig für CPU oder andere Beteiligte Komponenten aber für manche
  319. Daten ist das schon eine sehr gute Komprimierung die Idee hatten Sie auch schon ne vorhin also vielleicht habe ich so ein Unicode Text wo aber nur ganz
  320. wenige Zeichen vorkommen dann muss ich ja nicht immer 16 Bit daraus schreiben also OTF 16 ist ja häufig wie bei Java quellcod z.B dann kann ich oft nur so
  321. eine Handvoll Bits eben rausschreiben weil das die häufigen Zeichen sind die Vorkommen genau das ne das wäre eben diese entropiecodierung da sehen sie
  322. auch ein Beispiel genau das Wort eliminierte ne da steht dann eins für das E 001 für das L ne jetzt muss ich mal gucken danach kommt 01 für das i und
  323. so weiter das heißt man macht erst eine häufigkeitstabelle und dann kann man diese Bits so rausschreiben und hat ein auch leicht
  324. verständliches leicht programmierbares äh relativ gutes Komprimierungsverfahren es hat hier so einen praktischen Nachteil ich muss die
  325. ganze Datei erstmal auswerten od größeren Teil davon damit das sinnvoll ist und die Häufigkeiten bestimmen ne und muss dem Empfänger also dem also
  326. wenn Datenübertragung ist ne dem Empfänger dann auch diese häufigkeitstabelle geben ne und dann die komprimierte Datei also das heißt ich
  327. muss die Daten zweimal verarbeiten das ist hier eine Eigenschaft die ist nicht op mal ne wundert vielleicht einige weil sie denken wie soll es denn sonst gehen
  328. ich muss erstmal die Daten angucken und dann komprimieren und da kann ich schon verraten nein tatsächlich gibt's eine geniale Erfindung dass das jemand in
  329. einem Schritt geschafft hat ne das lernen wir auch gleich kennen ne aber das ist eben wie gesagt ein häufiges Element von
  330. kompromierungsverfahren dass man die Entropie also die Wahrscheinlichkeit dass ein bestimmtes Symbol eben Auftritt insbesondere wenn es sehr selten
  331. auftritt häufig auftritt dass man das ausnut bei der Erstellung eines längenvariablen Codes wir machen sowas ähnliches auch
  332. einmal eine Übungsaufgabe dass sie es mal durchgespielt haben aber ich glaube das ist jetzt nicht intellektuell herausfordernd eine häufigkeitstabelle
  333. zu machen aber nur dass sie es eben einmal verstehen das auch mal abschätzen können aber dann jetzt auch heute das eigentliche Verfahren sie merken das
  334. habe ich hier auch schon so ein bisschen vorbereitet ne diese Buchstaben LZW kommen wieder vor es gab da eben verschiedene Ideen beim Komprimieren ein
  335. paar haben wir quasi selbst entwickelt fast on the fly entwickelt wie lauflencodierung kommt elich irgendwie jeder drauf schon aufgrund der
  336. natürlichen Sprache dass man irgendwie sagt jetzt 10 mal ein X jetzt 20 x ein Y und so aber es gibt auch aufwendigere Algorithmen und das hier war so gewisser
  337. Durchbruch das ist ein so toller Algorithmus also der wurde so in zwei Hälften erfunden kann man sagen zuerst hatten zwei Erfinder also Lempel und ZiF
  338. ein Algorithmus entwickelt ich glaub so Ende der 70er und welch hat den dann Anfang der 80er ja doch müsste ziemlich genauso
  339. sein noch mal weiterentwickelt also hat den sozusagen noch mal getunt ne und daraus ergab es ein Gesamtverfahren was man heute nach allen drei benennt ne
  340. weil es jetzt hier nicht sinnvoll ist einzelne Erfinder herauszuheben die Anteile sind jetzt alle drei bedeutsam deswegen das Verfahren nach lempelziv
  341. und Welsch und kurz LZW das also ein Komprimierungsverfahren das jetzt erstmal für beliebige Daten also das muss jetzt nicht unbedingt
  342. sowas sein mit mit langen Lauflängen ne oder mit mit anderen Eigenschaften die wir eben herausgestellt hatten wie bei den Piktogramm oder so sondern erstmal
  343. ein Verfahren was sich auf beidfolgen z.B stürzt ne äh das ist eben auch hier ein möglicher Parameter man kann es auch mit statt 8
  344. Bit folgen mit 16 Bit oder anderen machen bevor sie das aber verwirrt äh wir würden es so wird es auch praktisch
  345. meistens gemacht tatsächlich als beitfoll gesehen also liest Bits ein eine Besonderheit ist schreibt aber nicht bites raus also mittelbar
  346. natürlich schon Datei besteht immer aus bites aber die einzelnen codierten Zeichen haben immer die Länge 12 Bit das heißt
  347. also er macht aus einem bite auf jeden Fall auch etwas was dann 12 Bit hat wenn es einzeln codiert wird oder und das ist hier schon mal die erste Idee um sich
  348. diesem Algorithmus zu nähern ne wenn man eine ganze Folge von bit codieren kann dann bekommt die auch 12 Witz ne das heißt also für einf bites lohnt sich das
  349. gar nicht der Algorithmus versucht also wenn wir so ein bisschen für menschlichen versucht also Folgen von bites zu finden und gibt denen dann
  350. Codewörter der Länge 12 Bit wissen wir gibt's gar nicht so viel also 4096 verschiedene Möglichkeiten 12 Bit anzuordnen ne das heißt da kommen die
  351. normalen bit schon mal rein wenn er keine keine Länge keine Folge findet ne aber dann hat er noch mal fast 4000 eben codzeichen für irgendwelche längeren
  352. Folgen es können sich vorstellen wir codieren z.B einen deutschen Text der jetzt irgendwie als sagen wir mal UTF8 vorliegt oder so dann haben wir
  353. natürlich auch solche Wörter die sich wiederholen es gibt z viele Wörter im deutschen die haben drei Buchstaben und sind häufig wie und der die das ne und
  354. die findet z.B dieser Algorithmus auf eine bestimmte Art und Weise und dann würde er für das Wort und oder sogar für space und space was ja be und gar nicht
  355. so selten ist dass vorher und nachher in space kommt ne also für diese fünf Zeichen würde er dann ein Codewort finden ne sodass dann im weiteren
  356. Verlauf immer nur 12 Bit für das deutsche Wort und sogar mit den beiden spaces benutzt wird ne das ist so eine Idee allerdings sie wissen es einfach
  357. Algorithmus der kann nicht denken der der kann kein Deutsch oder der kann nicht Sprachen unterscheiden J fallalls nicht sein Ziel hier der muss das
  358. irgendwie so machen dass das immer funktioniert auch mit Grafikdaten auch mit Quellcodes auch mit Maschinensprache und
  359. erstaunlicherweise ist da was gelungen was äh für viele Arten von Daten sehr gut funktioniert ist ein einfacher Algorithmus ne aber er hat jetzt so eine
  360. Komplexität dass er nicht so einfach ist wie eine lauflängencodierung aber passt auf eine Folie gut dem wollen wir uns jetzt
  361. einmal nähern und dann machen wir es auch gleich mit diesem Beispiel erstmal wie wie funktioniert so ein Algorithmus also speziell jetzt
  362. dieser hier ich hatte das schon gesagt er soll 12 Bit Werte schreiben 8 Bit Werte lesen also alle 8 Bit Werte die sowieso gibt also sprich alle bites
  363. bekommen schon mal auch ihren gleichnahigen 12 bitwerert also dann setzt wir einfach die ersten 4er bit n0 ne und dann ist z.B das große a im ask
  364. da wissen sie das ist irgendwie 001 001 oder so ich habe die Anzahl Null jetzt n geschätzt ne da kann ich ja einfach noch mal vier Nullen davors setzen ist ist
  365. immer noch das große a habe ich 12 Bit da ist noch nichts gewonnen das wird sogar länger um 50% ne aber das kann man ja machen in der Hoffnung dass man
  366. gleich guten Trick hat alles andere zu kürzen aber okay ich kann jedes Zeichen was ich in achtbit darstellen kann auch mit vier führende Nullen dann
  367. zusätzlichen führende Nullen vielleicht mit 12 Bit darstellen das ister Schritt 1 alle Zeichen werden erstmal in so ein Wörterbuch eingetragen ne also h gibt
  368. ein Wörterbuch oder so manchmal Mustertabelle da stehen dann diese späteren Folgen in so wie das deutsche Wort und ne also auch nicht nur drei
  369. Buchstaben er versucht noch viel längere Folgen zu finden dass er irgendwann sowas auch hat wie mit freundlichen Grüßen oder so also ganze Wortgruppen ne
  370. okay dann geht dieser Algorithmus die Datei durch Zeichen für Zeichen ne also wenn Sie so wollen von Anfang bis Ende von links nach rechts ne er holt immer
  371. ein Zeichen guckt ob es in seinem wörtlerbuch in seinem Lexikon steht ne also ob die Zeichenfolge da schon drin steht wenn ja ist gut wenn nicht
  372. schreibt er das raus und addiert im Wörterbuch schon mal eine Folge von zwei Zeichen nämlich das Zeichen das Folgende ist nicht schlimm wenn sie das nicht
  373. sofort verstehen am Beispiel wird's gleich klarer ne und nach jedem Zeichen was er eben raus schreibt hat er einen neuen Eintrag im Wörterbuch hängt also
  374. seh sch C das neue Wort aus Lexikon an merkt sich das letzte Zeichen und geht zurück zu Schritt 2 das ist also eine quasi Endlosschleife die endet aber
  375. dann wenn die Eingabe stockt also wenn er das letzte Zeichen gelesen hat dann endet der Algorithmus hier in natürlicher Weise deswegen stell bis
  376. keine Zeichen mehr vorhanden sind okay aber das muss etwas präzisieren man kriegt vielleicht so eine Grundidee okay er liest Zeichen für Zeichen er baut ein
  377. Wörterbuch dabei auf aber wie dannn jetzt genau ne und da sehen Sie hier wie schon sagt das passt auf eine Folie ist das hier ein Pseudocode also liest sich
  378. so ähnlich vielleicht wie wie Java oder so aber ist jetzt mehr für Menschen gedacht g daacht oder exakt für den Menschen gedacht also links ist codieren
  379. rechts ist decodieren packen es reicht also wenn Sie die die linke Hälfte mal genau betrachten und das mache ich hier auch gleich mit
  380. diesem beispielwerten ne okay also wie geht das noch mal ich habe so eine Tabelle mit allen 256 bites ja das ist erstmal nicht weiter schwierig die muss
  381. ich noch nicht mal speichern das sind ja immer alle Bits hintereinander ne dann fange ich an mit einem leeren String steht der Muster doppelp GLE leeres
  382. Muster und da sehen sie so eine wild Schleife solange noch Zeichen Folgen lese ich das nächste Zeichen und schaue ob es in der Mustertabelle schon
  383. existiert ne ansonsten trage ich es in der Mustertabelle ein und mache weiter wobei das Zeichen noch mal angehängt wird
  384. ne wie das genau geht ich nehme voller den Zettel mit weil man wenn ich michich jetzt einmal Vertu an der Tafel sind alle Folgeschritte falsch das ist jetzt
  385. unser String wollen wir jetzt komprimieren den habe ich im Prinzip übernommen aus Wikipedia aus gutem Grunde ne wenn Sie das nich zu Hause mal
  386. nachrechnen wollen auch vielleicht wenn ich mich jetzt irgendwo vertue gleich der Wikipediaartikel ist so schlecht nicht und da finden Sie genau das
  387. Beispiel ich habe auch ein Link auf so ein Online Codierer sie können beliebige andere Strings auch nehmen aber ist immer gut so ein quasi anliches Beispiel
  388. zu haben und das ist schon seit vielen Jahren unveränderten im Kapitel das nutze ich dann gerne ne okay also das gibt letztlich so Tabelle ne der
  389. gefundene Eintrag schreib's hier einmal relativ ausführlich gefundene Eintrag wie nehmen wir das ja
  390. Ausgabe und rechts in die Tabelle also die hat nur drei Spalten da sind dann die neuen wörterbuchzeichen da schreibe ich jetzt hier neuer
  391. Eintrag haben sie dieselbe Terminologie wie auch in dem Beispielartikel ne okay also ich lese jetzt hier los ich bin jetzt ein Algorithmus ich lese ein L
  392. mein Wörterbuch ist quasi leer also s jetzt erstmal nur alle Zeichen drin von 0 bis 255 alle Beit auch alle askzeichen oder so
  393. ne das heißt okay ich lese ein L und ich gebe dieses l aus in meinem Wörterbuch sind noch keine Zeichenfolgen ne aber jetzt geht's eben direkt schon
  394. los ich gucke denn ich gucke nach was denn gekommen wäre ne also das Wort was ich noch nicht im Wörterbuch im Wörter Wörterbuch ja das Wort was ich noch
  395. nicht im Buch hatte war hier LZ ne also immer das was mir jetzt gerade fehlt schreibe ich einfach ins wordterbuch ohne auch nur ahnen zu
  396. können ob ich das jemals brauche weil klar ein Algorithmus kann jetzt nicht wirklich vorausschauen ich habe ja vorhin schon
  397. verraten wir brauchen am besten Algorithmus der nicht zweimal durch die Daten gehen muss das macht dieser ne deswegen schaut er auch nicht voraus so
  398. dann schreibt der stummf rein ne also das ist der Eintrag LZ im Wörterbuch und und der bekommt das erste freie CoD den Index ne und das ist also
  399. 256 wie gesagt er schreibt 12 Bit Werte das heißt also er hat ein Bit gelesen und anderthalb bit geschrieben also noch ist gar nichts komprimiert aber die
  400. Hoffnung ist natürlich dass dieses Wörterbuch sich auszahlt ne aber vielleicht soll wir das hier noch mal hinschreiben das sind beites also a bit
  401. und das hier sind 12 Bit Werte
  402. und dadurch dass wir eben noch freie 12 Bit Werte haben können wir jetzt LZ festlegen als erstes Zeichen 256 ne weil die anderen haben wir für die
  403. natürlichen bites die wir lesen schon reserviert okay haben wir gemacht jetzt lesen wir ein Z ich gucke erstmal nicht auf den Zettel
  404. sonst können auch gerne stop sagen welchen Fehler mache dann vergleiche ich das mit dem Zettel auch das Z geben wir aus ne weil zw war nicht im
  405. Wörterbuch und das ist jetzt die 257 also hier wird das immer inkrementiert dann merken sie ja das
  406. brauch ich eigentlich auch nicht speichern das Wörterbuch ergibt sich ja ne aber ich schreib es ja einmal deutlich hin damit wir es lesen können
  407. ne ausgegeben wird tatsächlich auch nur das hier ne also ein Wörterbuch wird zu keinem Zeitpunkt ausgegeben ne das heißt beim Codieren beim beim Packen jetzt
  408. stelle ich das Wörterbuch und beim entpacken auch ne also der erstellt es auch on the fly okay jetzt kommt ein W und WL ist nicht im Wörterbuch also kann
  409. ich das W nur ausgeben jetzt merken jetzt habe ich schon 36 Bits verbraucht ne war noch nicht so gut weil ich habe 24 Bits gelesen wenn ich das so umrechne
  410. aber kommt wahrscheinlich noch ne und WL ist im Wörterbuch für 258 gut warum nicht ne so jetzt geht's aber rund jetzt Ken wieder ein L aber
  411. wenn wir vorausschauen sehen wir ah LZ ist schon im Wörterbuch lz7 ist nicht im Wörterbuch aber LZ ist super das heißt ich kann das hier lesen LZ jetzt auf
  412. einmal zwei bites und kann die in einem Zeichen ausgeben nämlich als 256 und jetzt merken Sie auch warum ich hier mehr Bits
  413. brauche weil ich gebe auch hier immer nur ein Zeichen aus aber ich brauche ja offen mal ein Zeichenvorrat für die Wörterbucheinträge ne deswegen also hier
  414. 12 Bit statt 8 Bit das wäre natürlich ein Parameter ich kann vielleicht auch mal sagen nimm doch mal 14 oder nimm 16 hast du zwei bites und je nach Datenart
  415. könnte sich das auch lohnen ne aber wir bleiben jetzt bei einem Beispiel sonst würden sie unnötig verwirrt werden und ins Wörterbuch kommt jetzt das was hier
  416. gefehlt hat das war also lz7 wie gesagt das kommt immer stumpf ins Wörterbuch SST wir an das werden wir
  417. nie wieder brauchen oder so wissen wir hier sowieso nicht ne aber der Algorithmus trifft sonst keine Entscheidungen nicht seine Aufgabe okay
  418. aber jetzt hat sich schon mal ein bisschen gelohnt noch nicht in Summe aber in dem Beispiel haben wir jetzt 16 Bits gelesen und 12 Bits geschrieben
  419. also ein bisschen was gespart okay jetzt haben wir also bis LZ hier gelesen und jetzt kennen wir im 7 und 78 ist noch nicht im Wörterbuch jetzt gucke ich Nour
  420. einmal dass es stimmt ja sieht gut aus wir lesen 7 also gemeint ist sozusagen das ask Zeichen 7 können sich vorstellen das Beit 7
  421. oder87 wie auch immer und dann muss er 78 als Folge ins wörderbuch Schreiben und das wäre dann die
  422. 260 okay danach 8 weil 8 l gibt's noch nicht im Wörterbuch jetzt kommt ist wahrscheinlich der Punkt wo die Hälfte
  423. von ihen etwa Algorithmus drauf hat ne andere überlegen noch was habe ich vorher alles erzählt was war wichtig oder so aber das kommt
  424. ähm es ist auch eine ich will damit nicht drohen aber ich will das fairerweise auch sagen das ist auch eine typische Klausuraufgabe dass man mal was
  425. damit LZW codiert oder dekodiert oder so ist vielleicht nicht so ein super langen String weil ne in der Klausur wollen wir mehr als ein Schema prüfen aber
  426. das das kann man elich ganz gut lernen und ist auch gut so ein paar Verfahren wirklich auch äh mal durchgespielt zu haben um das auch einschätzen können was
  427. machen die mit einer bestimmten Art von Daten okay der neue ein ne Entschuldigung das war falsch schreibt ach der neue Antrag ist
  428. 8L und 261 immer wenn man anfängt zu reden macht man Fehler genau so jetzt hat die a ausgegeben ah jetzt sehen wir LZ kennen wir schon lz7 kennen wir auch
  429. schon er kann jetzt wirklich drei auf einmal lesen lz7 weil lz7 haben wir schon im
  430. Wörterbuch Buch 259 können wir jetzt hier ausgeben jetzt hat sich also mal so richtig gelohnt ne und der neue Antrag ist dann
  431. wo waren wir jetzt bei diesem LZ ne lz77 gesagt wenn ich ein Fehler mache beschweren sie sich sofort bevor es
  432. einer falsch abschreibt einmal gucke ich jetzt wieder weil es ist wie gesagt und danach ist ja auch alles falsch wenn man Fehler macht aber sieht gut aus lz77 und
  433. 262 stimmt auch noch also ich habe mich hier auch nicht verzählt ja 7l hatten wir noch nicht ne hatten wir noch nicht genau so das heißt jetzt
  434. kommt ein mache ich noch 7 die sie wird ausgegeben weil 7 l gab es noch nicht im Wörterbuch ne ich das einmal so hochge hatte irgendwie so ein
  435. déjavu aber es gab's wirklich noch nicht und das wä jetzt 263 okay und das mache ich nach und nach so weiter und jetzt müssen sie sich so ein
  436. bisschen vorstellen in der Realität hätten sie ja auch eine Datei die hat nicht jetzt irgendwie 20 Bytes oder 30 Bytes vielleicht Kilobytes oder sogar
  437. Megabytes dann wird dieses Wörterbuch auch voll und wenn das Z Quellcode war dann sind natürlich irgendwann im Wörterbuch alle Java alle von Ihnen
  438. verwendeten mehr als einmal verwendeten Schlüsselwörter auch drin D sowas wie begin und end oder Case oder ne was sie da alles haben
  439. oder in deutschen Texten wie gesagt dann alle kurzen Wörter auf jeden Fall drin ne der die das und oder nicht ich du er sie essen also all das was in Texten
  440. also quasi unvermeidbar das also häufigerweise vorkommt ne all das wandelt natürlich ins Wörterbuch ne und wenn es dann später wieder benutzt wird
  441. brauche ich jedes Mal nur 12 Bits ne dann für ganze Wörter für ganze Wörter mit Space dann für Wörter hintereinander wie es mit freundlichen Grüßen wenn ich
  442. z.B e-mailarchiv komprimiere dann landet sicherlich sowas wie sehr geehrte Herr sehr geehrte Frau und so weiter also alle Wortgruppen die sich dann in so
  443. eine Archiv unweigerlich wiederholen vielleichtar hundertfach wiederholen alle die wandern ins Wörterbuch und können dann sehr kurz also immer mit 12
  444. Bits mit einem codzeichen ausgegeben werden das ist diese Erfindung und wie gesagt ein tolles komprimierungsverfah en also toll
  445. deswegen weil ne also ich muss n einmal durch den Text durchgehen das ist schon mal gut muss nicht zweimal lesen das ist so bei sehr großen Archiven oder großen
  446. Dateien wäre das schon Problem dann noch mal zurückzuspringen noch mal zu lesen also das ist cool und was auch cool ist ne weiß nicht ob sie so begeistern
  447. können für technische Eigenschaften von algorithmenich kann man es dann vor allem wenn man vorher die kennengelernt hatte wir haben ja nicht nur hier
  448. gelesen wir haben sofort geschrieben das heißt der Algorithmus ist in der Lage nicht nur zu komprimieren sondern beim Lesen der Daten direkt die komprimierten
  449. Daten wieder auszugeben das ist eine schöne Eigenschaft für Daten die ich auch übertrage ne also dann passt ja eine bestimmte Anzahl von bites passten
  450. so ein ippaket das kommt auch noch im letzten Kapitel der Vorlesung Netzwerke dann ne das heißt während ich die Datei lese und komprimiere kann ich auch schon
  451. anfangen sie aufs Netzwerk zu legen und zum Empfänger zu übertragen ich muss da nur einmal durchgehen ich kann sofort rausschreiben
  452. ich muss mir auch nicht merken was ich schon gelesen habe merken muss ich mir natürlich während ich komprimiere das Wörterbuch aber ansonsten ist das so
  453. fire and forget ne also ich schreib die Ausgabe und muss nicht wissen was ich vorher schon alles gelesen habe ne nur die Position in dieser Datei ne und eben
  454. das aktuelle Wörterbuch und wenn die Übertragung zu Ende ist W ich Datei dann geschrieben habe kann ich das Wörterbuch auch Löschen der Empfänger braucht das
  455. nicht weil der Empfänger auch der bekommt dann das hier dann kann er sich auch LZ und zw und so weiter ins Wörterbuch schreiben ne das heißt er
  456. braucht es nicht explizit weil er beim [Musik] Decodieren auch erhält ne also er generiert sich sein Wörterbuch on thefly
  457. ne und wenn man das so zusammenbringt merkt man ja okay das ist wirklich eine gute Eigenschaft ne viele Algorithmen die sich SP spontan ausgedacht hätten
  458. hätten wahrscheinlich nicht alle diese guten Eigenschaften auf einmal ja was passiert W das einfach nur alles zeichenellag genau
  459. also in diesem Fall wäre es so sofern wir jetzt hier keine Modifikation eintragen wenn das Wörterbuch voll ist dann gibt's keine Zeichen mehr dann
  460. haben wir nur noch das Wörterbuch und arbeiten damit weiter jetzt kann man sich durch Modifikation überlegen dass er vielleicht ab einer bestimmten Größe
  461. sagt dann macht er noch ein größeres Wörterbuch vielleicht irgendeine Markierung man kann an jedem Algorithmus feilen aber erstmal in der Grundform
  462. nach 4096 einträggen Schluss ja also aber auch bei deutschen Texten wissen sie da gibt doch sehr viele
  463. Wörter die häufig vorkommen ne und sche sowas wie Grundwortschatz oder so sagt man ja schon 1000 Wörter also bei den meisten Sprachen haben sie dort
  464. schon den Grundwortschatz drin mit so eine Wörterbuch bei aller Vorsicht der Vereinfachung weil noch andere Zeichen dazu kommen wie
  465. Satzteile oder Satzzeichen oder so auch die waren natürlich hier alle ins Wörterbuch ne aber ja das hier so eine Begrenzung
  466. genau also so funktioniert das M auch das machen wir mal als Übung würde ich ihn auch stark empfehlen dass Sie sowohl das Wikipedia Beispiel noch mal
  467. durchgehen wenn sie auch wenn Sie jetzt hier vielleicht Schwierigkeiten hatten das sofort zu verstehen noch mal ganz in Ruhe und ansonsten sich da noch mal
  468. weitere Beispiele vielleicht selbst generieren den Link habe ich schon bei Moodle eingestellt da habe ich jetzt einfach irgendeine Webseite genommen die
  469. auch lz77 macht also sag das deswegen dazu weil manche dieser Webseiten m die kenne ich nicht weiter ne also weiß nicht was da sonst für ein Produkt
  470. oder sonst wie beworben wird deswegen immer Vorsicht mit diesen Links aber zumindestens der LZW komprimierer und dekomprimierer der da abgebildet ist der
  471. macht das echt ganz schön genau das Beispiel hat ich hier noch mal auf der Folie habe ich jetzt vorher angeschrieben die Zeit genutzt
  472. hier sehen Sie noch mal ein Beispiel das schreibe ich jetzt aber nicht an die Tafel das würde langweilig werden hier mal für Noten das S jetzt einfach nur
  473. merken damit kann ich auch also es geht nicht nur um Texte oder Maschinensprache oder Grafiken hier ist mal quasi eine vektorisierte Musik also wirklich als ne
  474. CDE und so weiter also sie kennen sich Durtonleiter oder ähnliches ne und damit das Beispiel einfach gehalten ist ist jetzt aber die Länge sie wissen
  475. normalerweise wenn sieateien haben ist immer ein Ton und die Länge wie lange gespielt wird und dann welches Instrument er
  476. da an der Stelle versucht nachzuarmen die haben uns jetzt hier beschränkt mal einfach auf die auf die Noten selbst ne und dann kennt das jeder Bruder ob oder
  477. fr Jacke ne das ist dann cdec am Anfang und das wird jetzt hier auch so mit diesem Verfahren mal eben komprimiert ne am Anfang gibt's noch keine Ersparnis da
  478. wird das Wörterbuch aufgebaut aber auch in der Musik gibt es eben tatsächlich typische Ton folgen also es gibt auch Dinge die empfinden wir als harmonisch
  479. und andere nicht ne und dementsprechend gibt sich hier auch sogar relativ schnell dann schon die erste Gelegenheit dann auch äh Wörter
  480. aus dem Wörterbuch wirklich zu verwenden und ja einmal ein weiteres Beispiel aber dann sehen Sie hier schon im so ab der Hälfte etwa
  481. ähm kann er schon sehr viele Dinge ausgeben die im Wörterbuch stehen zum Schluss den gibt da fast nur noch Wörterbucheinträge aus also offenbar
  482. scheint sich bei Musik oder jedenfalls bei so ja recht einfache Musik so ein Kinderlied dann sehr schnell etwas zu wiederholen
  483. aber gut das ist ja auch bei Musik ein wichtiger Punkt dass man daund solche sich wiederholen Motive hat ne aber Sie können das Komprimieren sie brauchen
  484. keine Ahnung von diesen Daten zu haben der komprimierer wird auch nie wissen was soll auch mit Wissen anfangen dass das hier Musikdaten sind ne können ja
  485. auch Messwerte sein od irgendwas anderes ne er wird es immer eintragen jetzt steht das schon hinten als Hinweis wie ist das eigentlich mit den Lauflängen ne
  486. weiß ich können sie sich das Verfahren jetzt schon so im Kopf vorstellen wie gut wäre das eigentlich bei unserer Grafik die wir
  487. hat mit diesen vielen gelben Punkten ne die müssen nicht die ganze Grafik vor Augen haben aber ist dieses Verfahren denn auch gut wenn ich sowas habe wie
  488. hunderte von Pixeln in derselben Farbe also wer ich frageer sollte ich lieber für sowas dann doch lieber gucken dass er lauflencodierung macht und für
  489. andere Dinge dann e LZW Macht hätten sie dazu direkt eine Idee
  490. jaol im ein genau würde ein eintragen Wörterbuch erstellen bei jedem neuen Pixel aber das ist jetzt kein Gegenargument weil das macht das
  491. Verfahren sowieso bei jeder Ausgabe wird ein neuer Eintrag im Wörterbuch erstellt das macht ja hier sozusagen stur egal ob das
  492. sinnvoll ist oder nicht ja genau das Wörterbuch wirkt dadurch vielleicht ein bisschen komisch wenn jetzt ganz viele gelbe Pixel oder so hintereinander
  493. kommen ja ansonsten wird es dann funktionieren wird dann wirklich komprimiert werden ja würde funktionieren sagen sie
  494. m genau ich habe dann plötzlich sehr viele Folgen von gelben Pixel im Wörterbuch aber es würde auch funktionieren ne oder meint jemand nee
  495. nee da hat er sich jetzt vertan W jetzt wirklich nur gelbe Pixel kommen dann funktioniert ja doch nicht weil oder so traut sichemand Argument zu
  496. jaich das Wörterbuch wird schnell voll genau also W ist ein Argument aber da möchte ich erinnern der Algorithmus wie gesagt wenn er erstmal hier
  497. 4000 Ausgaben getätigt hat ne dann ist das Wörterbuch sowieso voll ne also das heißt da müsste ich eventuell wenn ich wenn ich jetzt mit großen Grafiken zu
  498. tun habe überlegen ob jetzt vielleicht der Parameter 12 Bit ne der jetzt hier die 496 erzeugt ob der anzupassen wäre ne aber dann haben sie natürlich inoweit
  499. Recht das wäre hier eine Überlegung ob das passt aber jedenfalls beide hatten jetzt erstmal gesagt ansonsten wir aber
  500. funktionieren das Wörterbuch sieht zwar komisch aus aber die Lauflängen ne die treten dann hier eben auch auf und genauso ist es auch aber
  501. das machen wir jetzt nicht mit Zettel und Stift sondern kann ich i noch diesen Simulator mal zeigen habe ich den hier
  502. so ich hoff mal wahrscheinlich ist es WLAN zwisch euch wieder unterbrochen aber ich hat vorhin schon mal verbunden mal gucken so das ist eben ein den habe
  503. ich tatslich so gegoogelt ja den können Sie sich mal angucken sollte diese Seite jetzt aber mal offline gehen so kurz vor der
  504. Klausur und sie kriegen Riesens Schritt also sie finden da auch ein Dutzend andere Treffer der war jetzt besonders gut weil er auch so unsere Schreibweisen
  505. und diese 12 Bit und alles voreingestellt hat ne aber jetzt können wir das hier mal Testen erstmal ob es klappt ich nehme mal eben noch die Folie
  506. mit dem LZW da haben gerade so vor Augen das markiere ich jetzt mal ich weiß nicht ob sie es sehen ne jetzt sehen sie natürlich auch nicht mehr was sie jetzt
  507. nicht sehen ist ich markiere auf der Folie diesen String und versuche in die Zwischenablage zu schrieben a irgendeinem Grund ich hasse
  508. das Grund kann ich nicht bei Doppelklick markieren aber zum Glück ging es so und jetzt bin ich hier in dem Browser ja das hat
  509. geklappt okay nimmt nicht das Wort enter also die Taste Enter sondern ich muss hier Klicken es klappt ohne
  510. Netzwerkverbindung wow so jetzt sehen sie auch compressed also er hat ausgegeben LZW dann 256 dann 78 259 ne genau wie wir auch er schreibt das jetzt
  511. hier nur in eckigen Klammern und eine Zeile und nicht als Tabelle aber das ist der einzige Unterschied also er macht es ansonsten genauso wie wir auch ne und
  512. er sagt uns noch er hat dann von 256 bis 271 das Wörterbuch voll geschrieben ne dann hat man so ein Wert wie groß das Wörterbuch gefunden gewachsen ist bei
  513. der Gelegenheit okay jetzt können wir zu unserem Beispiel zurückkehren jetzt haben wir schwarze und gelbe Pixel ich
  514. kann das ja einfach mal durch kleine GS machen ne jetzt kommen ganz viele gelbe Pixel ich zähle jetzt auch nicht ist jetzt mehr so ein Beispiel sag jetzt
  515. haben wir drei schwarze ein bisschen breiter SSS jetzt kommen wieder ganz viele gelbe wieder drei schwarze und noch mal
  516. ein paar gelbe das wir jetzt nur mal sowas haben was so ungefähr der Struktur entspricht ohne es jetzt gezählt zu haben wollen nur wissen kommt der
  517. allgemein damit zurecht oder ist das jetzt irgendwie so ganz unglücklich ne z.B bei lauflängencodierung haben wir gesehen das wäre unglücklich für die
  518. deutsche Sprache ne weil selten ein Buchstabe sich wiederholt ich meine es gibt solche Wörter wie Al oder so ne mit zwei as aber die muss man schon suchen
  519. ne in so einem langen Text ne wie wär es denn hier umgekehrt so jetzt gucken wir mal und da sehen wir tatsächlich das ist sehr gut gelaufen und zwar hat er direkt
  520. rausgeschrieben 256 257 258 also sieht man auch das ist offenbar diese Folge bis es zu denen schwarzen Pixeln kommt das ist immer eins höher ne weil genau
  521. das passiert im Wörterbuch steht da nämlich GG ne ich was mal mit Zahlen also 2gs 3GS 4 5 6 7 GS 8gs ne also da kommt
  522. immer das nächste Wort wo noch einmal g dahinter geschrieben wird und das kann er dann auch verwenden ne das heißt beim rauschreiben kann er nachdem das erstmal
  523. Wörterbuch steht kann er sofort rauschreiben zwei danach drei danach direkt auf vier ne das heißt mit jedem weiteren Zeichen hat er ein Wort was ein
  524. Beit länger ist das Verfahren ist also tatsächlich für Lauflängen auch sehr gut ne es ist jetzt nicht so gut wie ein reines
  525. lauflängenverfahren weil da guckt er sofort jemand in die Zukunft ne aber so nach und nach wird er sich ja alle Lauflängen ein des Zeichens bis bis 100
  526. in unserem Beispiel oder bis 128 oder 256 oder was wir da eben hatten bei unserer einfachen Grafik die wird er sich alle im Wörterbuch eben holen und
  527. dann schlagartig immer mit einem 12 bitwort ne rausschreiben können ne und daraus ergibt sich hier eben diese besondere Struktur dass er dann immer
  528. das nächste codwort nimmt also immer ein Zeichen mehr unterbringt ne und das wird erst durchbrochen wenn das erste s kommt ne und dann noch mal als das zweite s
  529. kam und wenn W wir jetzt hier noch weiter gemacht hätten nee weiter zeigt das jetzt hier nicht an irgendwann hätte auch zwei Buchstaben S dann im
  530. Wörterbuch gefunden aber soweit sind wir jetzt hier nicht mehr gekommen ne aber das decompressed ist also hier genauso gut gegangen und er hat jetzt auch nur
  531. hier das aufgeschriebenes 287 das kommt jetzt fast ein bisschen wenig vor es kann sein dass er hier nur ein Teil ausgibt weil das jetzt wie gesagt
  532. meessrer die backausgabe ist für jemanden der vielleicht seine Ergebnisse mit Zettel und Stift hier einmal überprüfen möchte ja so gut kN ich das
  533. tun ich habe es auch nicht programmiert war wie gesagt einfach nur eine googleuche nach einem LZW Verfahren ansonsten gefällt mir die Seite also
  534. jetzt dieser dieser einfache eingabemechanismus ganz gut es gibt hier nur einen ganz blöden Nachteil die haben welch falsch geschrieben ne ich bin doch
  535. ziemlich sicher dass lempelzif Welsch als wird Welsch gesprochen aber schreibt D mit ch das bisschen schadeade englischsprachige Seite h man gedacht
  536. die machen eine Fehler vielleicht weniger häufig aber vielleicht hat einer rausgehört und dachte irgendwie an Valis an Wales oder so W people weiß ich nicht
  537. aber das ist jedenfalls ein chipfehler ansonsten funktioniert das wie gesagt hier ganz gut ja das wäre auch schon alles soweit dazu heute
  538. schenke ich ih mal ein paar Minuten zum Schluss hin aber bedenken Sie sie haben auch heute wieder die Möglichkeit Sonderpunkte zu erwischen mit dem Eva
  539. exam Test ne wenn jetzt jemand keinen Rechner hat oder nicht online gehen kann und den zu machen dann bitte jetzt auch gleich noch bei melden schließen wir ein
  540. Labor für Sie auf anssten viel Erfolg und wir sehen uns gleich in der Übung

Zum Nachlesen

DatenkompressionDatenkomprimierung [1] genannt – ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf, Lempel-Ziv-Welch-AlgorithmusDer Lempel-Ziv-Welch-Algorithmus (kurz LZW-Algorithmus oder LZW genannt) ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der … LauflängenkodierungDie Lauflängenkodierung (englisch run-length encoding, kurz RLE), auch die Lauflängencodierung, ist ein einfacher verlustfreier Kompressionsalgorithmus. Huffman-KodierungDie Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of …