Einführung in die Informatik (EI)  3.9 Komprimierungsverfahren
Prof. Dr. Miriam Föller-Nord
https://www.youtube.com/watch?v=LOl_vzmCG_o

Transkript (automatisch erstellt)

0:00 [Musik] hallo und herzlich willkommen zu meiner online vorlesung einführung in die
0:15 informatik kurz heute mit dem thema 3.9 komprimierungsverfahren ich will aber den körper griechen dazu überzeugte zu wenig kapazität
0:34 was jetzt okay ich kann natürlich ein größere koffer nehmen aber das sind nicht zweck der übung war es gibt noch für möglichkeiten
0:41 ich kann versuchen es dann so zu komprimieren das ist rein passt zwei möglichkeiten entweder ich versuche es dann zumachte
0:53 [Musik] effektiver anreisen flachen schöneren einzusortieren
1:04 mit mehr reinpasst so schön zusammen [Musik]
1:18 oder aber möglichkeit ich lasse einfach zurück welt nicht braucht ich selbst am strand
1:32 das alte balken vielleicht auch kultur heute und deo sollte ich vielleicht mitnehmen aber es geht dann verraten sie sind kann ein strandurlaub
1:45 nike relevant und dann hab ich hab heut ist dass ich den haushalt doch noch zu und genau die beiden prinzipien ziehen wir auch bei datenkompression entweder
1:57 ein verfahren um unter zeit ein bisschen mehr geschickter zu komprimieren und zu verpacken oder unnötiges zeug einfach nicht
2:08 und mir dazu werde jetzt mit festplatten da ist es ihr mit koffern immer sind sie zu klein und selbst die größte festplatte die man
2:18 sich neu kauft wird irgendwann voll und so ist natürlich auch mit bandbreiten auch da hat man eigentlich immer zu wenig für die großen datenmengen die man
2:28 übertragen möchte zb in bildern videos und audio dateien also unsere ressourcen sind begrenzt deswegen ist es notwendig diese effektiv auszunutzen
2:40 zum beispiel dadurch dass man die daten komprimiert es gibt zwei grundlegende prinzipien bei der komprimierung das eine ist die
2:50 verlustfreie auf englisch lossless komprimierung und das andere die verlust behaftete lossie komprimierung bei der verlustfreie komprimierung spricht man
3:00 auch von einer recht und ganz reduktion hier geht darum die daten einfach in einer effektiveren art und weise abzuspeichern so dass dadurch weniger
3:09 speicherplatz benötigt wird beispiele für solche verfahren sind das verfahren der hafen code und die lzb kontierung die zweite variante ist sie
3:23 ihrer llevant reduktion da lässt man einfach ihr relevante information weg verfahren die nach diesem prinzip arbeiten sind zum beispiel mpeg also für
3:34 audio- mp3 und das jpeg format für bilder schauen wir uns zuerst einmal die verfahren an die verlustfrei komprimierten können
3:49 das erste verfahren ist lte das steht für run längs in kolding oder auch lauf längen codierung auf deutsch und das prinzip ist das aufeinanderfolgen die
4:00 gleiche symbole über ihre anzahl codiert werden wie kann man sich das vorstellen hier mal ein kleines beispiel das wort
4:07 superman mit vier es zwei und sieben ist geschrieben und ich kann jetzt das aufeinanderfolgen der symbole also hier
4:17 in unserem beispiel der buchstaben über ihre anzahl kotieren dann wird daraus 4 11 217 e 1 m 1 a und 1 in wir haben hier also eine reduktion von 18
4:33 ursprünglich auf 16 nach der komprimierung naja problem an diesem verfahren in dieser form ist wie man sieht dass wenn
4:46 symbole also die buchstaben nur ein mal nacheinander auftreten man durch das komprimierungsverfahren sogar mehr weit erzeugt es gibt eine variante zur
4:59 optimierung die das ganze verbessert die sieht so aus dass nur mehr als drei identisch aufeinanderfolgende bereits über ihre anzahl codiert werden und
5:10 alles andere normal übernommen wird dazu benötigt man dann ein zusätzliches markierung symbol dass erkennbar ist an welcher stelle diese um kodierung und
5:21 komprimierung stattgefunden hat hier wieder unters superman beispiel nach der komprimierung erhalten wir m4 es das m ist unser markierungs symbol für die
5:35 anzahl der buchstaben und es ist jetzt hier der buchstaben die beiden aus werden nicht um codiert das p auch nicht dann erhalten wir am 7
5:45 rm und enden dadurch haben jetzt das 18 13 gemacht na das ist doch schon besser das markierungs symbol sollte günstigerweise nicht in den daten als
5:58 zeichen vorkommen ist das aber der fall ist es auch kein problem damit kommt der algorithmus dann auch klar eingesetzt wird das run längs in kolding
6:09 bei grafiken im bitmap format bei schwarz-weiß grafiken und bei fax formaten weil es sich dafür besonders eignet nämlich für dateien mit langen
6:21 folgen von gleichen zeichen vorteil des verfahrens es ist einfach und es ist schnell der nachteil es ist ungeeignet für
6:29 dateien mit häufig wechselnden bereits das zweite wichtige verfahren ist die hafen codierung prinzip ist hierbei das denn am häufigsten vorkommenden symbolen
6:38 die kürzesten coach zugeordnet werden und den seltensten symbolen die längsten coach ähnlich wie beim wasser alphabet das verfahren läuft in mehreren
6:49 schritten ab der erste schritt ist dass man eine analyse macht welches symbol wie häufig vorkommt in der entsprechenden datei dann erzeugt man
7:00 daraus einen sogenannten ausbalancierten code baum und anhand dieses kurt baums kann man neue codes für die einzelnen symbole erzeugen die dann in summe eine
7:16 deutlich kleinere datei ergeben als das in der ursprungs codierung der fall war machen wir das auch wieder ein beispiel diesmal nur super
7:26 wer sich dafür interessiert wie das verfahren genau funktioniert dem empfehle ich mein video zur hartmann codierung unten in der beschreibung des
7:35 videos steht der link dahin ich will ja bloß das ergebnis vorstellen man kann also diesen string aus 15 zeichen komprimieren auf 3
7:49 das ist auch wirklich eine deutliche und ordentliche komprimierung und ganz ohne datenverlust allerdings muss man jetzt noch dazu sagen dass man diesen code
8:03 baum den man zur codierung erzeugt hat mit übertragen muss damit eine zurück oder eine decodierung in die ursprünglichen daten möglich ist das
8:14 heißt wenn man es genau nimmt hat man halt doch nicht nur in dem beispiel drei bald denn man muss die metadaten also diesen code baum mit übertragen
8:25 das verfahren ist universell einsetzbar funktioniert mit jeder art von datei und es wird auch häufig als zusätzliches verfahren nach verlust behafteter
8:34 komprimierung eingesetzt zum beispiel bei der mp3 codierung vorteil man hat hohe komprimierung faktoren und es ist auch für dateien mit häufig wechselnden
8:47 beides geeignet der nachteil da auch mit bar muss mit übertragen werden das heißt es entsteht ein gewisser overhead das letzte verfahren dass ich meinen
8:59 verlustfreien verfahren vorstellen möchte ist lzb codierung lzb steht für die entwickler dieses verfahrens lamb latif und später kam noch weil statt so
9:10 das prinzip ist dass man aus den daten ein wörterbuch erstellt indem neue bike sequenzen codiert werden sich wiederholende bei sequenzen können so
9:20 also zunehmend verkürzt werden auch hier ein beispiel das nun als ergebnis zeigt auch hier wer sich genauer für das verfahren interessiert
9:32 dem empfehle ich das entsprechende video dazu man kann jetzt hier sehen das aus super super bei der komprimierung neue
9:44 wörterbuch einträge entstanden sind die werden einfach durchnummeriert ab einem gewissen staat wehrt man geht davon aus dass es einfach ein standard alphabet
9:54 gibt wie zum beispiel den ascii codes und neue zeichen werden daneben oberhalb dieser nummerierungen oder dies dann erzeugt und so kann man einige dabei zu
10:07 glänzen durch neue wörterbuch einträge ersetzen also man sieht dass hier nicht immer nur die gleiche aufeinander folgende zeichen verkürzt werden können
10:16 wie das beim algorithmus der fall ist sondern auch andere kombinationen von zeichen in unser beispiel ist das verfahren im übrigen auch nicht
10:29 besonders überzeugend weil ich ja für die nummern oberhalb von 255 2 tbyte brauchen wenn ich davon ausgehen dass das vorher ascii codierung war hatte ich
10:42 noch ein zeichen das heißt ich gewinne eigentlich nur an dieser einen stelle hier etwas wo ich drei b-2 zusammenfassen kann und deswegen kriege
10:56 ich jetzt hier auch nur eine komprimierung von 20 zeichen auf 19 eingesetzt dieses verfahren zum beispiel bei der zib komprimierung von archiven
11:06 oder im grafikformat gf vorteil ist wie für sehr gute komprimierungsverfahren auch wenn wir das jetzt hier in diesem beispiel nicht gerade nachvollziehen
11:15 können die komprimierung ist sehr effizient und es müssen keine zusatz informationen übertragen werden
11:22 nachteil das funktioniert eigentlich nur bei großen dateien effektiv deswegen ist das in unserem beispiel eben nicht so gut verifizierbar
11:36 dass ein überblick über verfahren die verlustfrei arbeiten und nur noch ein blick auf verfahren die mit ihrer eleganz reduktion arbeiten und damit
11:48 aber verlust behaftet wie zum beispiel mp3 oder jpeg das prinzip ist dass man signal anteile weglässt die die menschlichen sinne aufgrund ihres
12:02 begrenzten auflösungsvermögen nicht wahrnehmen können bleiben wir mal bei mp3 audiodateien hier wird der psycho akustischen effekt
12:12 ausgenutzt das ist zum einen der frequenzgang also welche frequenzen mit welcher intensität das menschliche ohr überhaupt wahrnehmen
12:23 kann die sogenannte ruhe hörschwelle und es geht um verdeckung effekte das heißt um die unschärfe des gehörs
12:31 wenn frequenz anteile besonders laut oder auch besonders leise sind frequenzen oder töne die das ohr dann sowieso nicht wahrnehmen kann kann ich
12:43 ohne subjektiven merklichen qualitätsverlust dann auch einfach weglassen und durch das weglassen von informationen wird natürlich im
12:54 endeffekt die datei kleiner eingesetzt werden diese verlust behafteten verfahren insbesondere für audio video und bilder
13:05 der vorteil ist es sind sehr hohe kompression faktoren möglich der nachteil ist es ist ein hoher rechenaufwand und bei einer starken
13:17 komprimierung kommt zu einem deutlichen qualitätsverlust ganz wichtig zu wissen information gehen unwiederbringlich durch die komprimierung verloren die
13:27 lassen sich also im nachhinein nicht mehr herstellen die ein kleiner blick auf das grundlegende prinzip basieren
13:34 dargestellt ist ist die hörschwelle des menschlichen ohrs das heißt nach rechts sind die hörbare frequenzen aufgetragen das sind umgangssprachlich die tonhöhen
13:48 die das ohr wahrnehmen kann und nach oben wie laut die entsprechenden tonhöhen sein müssen damit das ohr die überhaupt wahrnimmt
14:01 die einheit um diesen pegel diese lautstärke anzugeben ist das dezibel man sieht ja ganz gut dass das ohr bei unterschiedlichen frequenzen
14:12 unterschiedlich empfindlich ist zusätzlich zu dieser hörschwelle kommt aber hinzu dass wenn an einer frequenz an einer tonhöhe ein sehr lauter ton
14:27 auftritt ist zu einer verschiebung dieser hörschwelle um diesen lauten ton herumkommt das nennt man einen verdeckt das heißt das ohr wird um diesen ton
14:40 herum dann zu diesem zeitpunkt unempfindlicher bedeutet das wenn wir hier andere frequenzen gleichzeitig zu diesem lauten ton haben diese unterhalb
14:55 der hörschwelle neben schwache töne in der unmittelbaren nachbarschaft laute töne werden also zu diesem zeitpunkt nicht wahrgenommen
15:04 damit sind sie irrelevant und damit kann man sie aus den daten entfernen und das ist das prinzip wie es zur kompression und zur datenreduktion kommt die
15:15 aufwändig dieses verfahren bei mp3 ist soll einfach die nächste spitze noch einmal andeuten es sieht nämlich mehrere schritte notwendig um eine solche
15:24 komprimierung durchzuführen das ganze hier kommt das eingangssignal läuft erstmal durch nicht so genannte filter bank des weiteren wird eine fast fourier
15:34 transformation durchgeführt es wird das psycho akustische modell mit eingerechnet und geht dann in die modifizierte diskrete cosinus
15:48 transformation bevor es dann über einen konfigurierbaren quantifizieren und eine half men codierung zu einem ausgangssignal codiert wird soweit man
16:01 ein kleiner einblick in komprimierungsverfahren wer ein bisschen tiefer in die materie einsteigen will von verlustfreien
16:08 komprimierungsverfahren den lege ich noch mal meine videos zu hla hoffmann code und lz weg regierung ans herz damit sind wir am ende dieser
16:17 zusammenfassung über kontrollieren verfahren angekommen