WEBVTT 00:06.340 --> 00:07.720 Grundbegriffe der Informatik. 00:07.820 --> 00:08.540 Schönen guten Tag. 00:11.000 --> 00:13.520 Herzlich willkommen zur nächsten Vorlesung. 00:14.320 --> 00:16.160 Wir sind immer noch im achten Kapitel. 00:17.260 --> 00:20.580 Das anfing mit Herrn Leibniz. 00:21.500 --> 00:25.940 Heute, vor 302 Jahren, ist Herr Leibniz gestorben. 00:34.130 --> 00:38.570 Und somit das letzte, was wir uns am vergangenen Freitag angeguckt 00:38.570 --> 00:42.650 haben, waren so Hin- und Herübersetzungen von Zahldarstellungen, zum 00:42.650 --> 00:45.850 Beispiel von hexadezimal nach binär und umgekehrt. 00:46.690 --> 00:51.590 Und der Witz bei diesen Übersetzungen ist, dass das gerade das 00:51.590 --> 00:52.610 Wesentliche sein soll. 00:53.790 --> 01:00.250 Für beide Repräsentationen, wir haben eine Bedeutung definiert und 01:00.250 --> 01:02.650 Übersetzungen sollen halt bitte Bedeutung erhalten. 01:03.230 --> 01:07.950 Also wenn ich aus einer hexadezimalen Repräsentation eine binäre 01:07.950 --> 01:11.350 Repräsentation mache, dann möchte ich das natürlich im Allgemeinen, 01:11.410 --> 01:15.030 wenn ich einfach so übersetze, so, dass die repräsentierte Zahl die 01:15.030 --> 01:15.810 gleiche bleibt. 01:16.670 --> 01:24.530 Das heißt, im Allgemeinen, bei Zahlen ist es noch besonders schön, 01:24.850 --> 01:28.730 jede Bitfolge oder jede Folge von Zeichen repräsentiert eine Zahl. 01:29.310 --> 01:32.330 Im Allgemeinen, bei sowas wie Java-Programmen oder was auch immer, 01:32.490 --> 01:34.630 nicht alles ist ein legales Java-Programm. 01:34.630 --> 01:37.810 Also was man dann übersetzen will, sind nicht alle Wörter über 01:37.810 --> 01:41.910 irgendeinem Alphabet A, sondern nur so eine formale Sprache LA, die 01:41.910 --> 01:44.370 eben eine Teilmenge ist von A-Stern. 01:48.470 --> 01:52.630 Und der Zielbereich sind dann eben auch nicht beliebige Zeichenfolgen, 01:54.750 --> 01:58.670 sondern sinnvolle, syntaktisch korrekte, was weiß ich, Programme in 01:58.670 --> 02:01.810 einer anderen Programmiersprache, meinetwegen, wenn Sie von Java nach 02:01.810 --> 02:03.670 C oder was auch immer übersetzen wollen. 02:03.670 --> 02:12.050 Und Sie haben eben für beide Mengen von Gebilden, für beide Wörter aus 02:12.050 --> 02:18.970 LA und für Wörter aus LA und LB so eine gleiche Menge von Bedeutungen. 02:19.870 --> 02:23.470 Und jedes Wort aus LA hat eine Bedeutung, jedes Wort aus LB. 02:24.270 --> 02:27.510 Und von einer Übersetzung verlangt man dann eben, dass, wenn ich ein 02:27.510 --> 02:31.690 Wort nehme, erst übersetze und dann gucke, was ist in dem Zielbereich 02:31.690 --> 02:36.030 dessen Bedeutung, dann soll da bitte das Gleiche rauskommen wie beim 02:36.030 --> 02:36.430 Original. 02:37.630 --> 02:40.610 Also die Bedeutung des Originalwortes ist gleich der Bedeutung des 02:40.610 --> 02:41.710 übersetzten Wortes. 02:42.530 --> 02:44.290 So was wollen wir Übersetzung nennen. 02:44.630 --> 02:47.390 Und die Leute meinen dann manchmal solche Diagramme mit so einem 02:47.390 --> 02:50.850 kleinen Kringel innen drin, was bedeutet, egal welchen Weg ich gehe, 02:51.510 --> 02:55.370 welche Komposition von Funktionen, es kommt immer das Gleiche raus. 02:56.570 --> 02:57.050 Gut. 02:59.310 --> 03:02.970 Und dass das bei dieser Übersetzung, die wir da hingeschrieben haben, 03:03.130 --> 03:04.810 funktioniert, das ist völlig banal. 03:07.430 --> 03:09.890 Ich würde es noch nicht mal nachrechnen nennen. 03:10.010 --> 03:14.510 Man setzt einfach ein, Dinge, Definitionen, einmal eine Eigenschaft, 03:14.630 --> 03:16.170 die wir gesehen haben und schon steht es da. 03:17.410 --> 03:17.510 Ja. 03:18.370 --> 03:20.570 So, ich glaube, soweit waren wir ungefähr gekommen. 03:22.050 --> 03:26.570 Und dass man, naja, Zahldarstellungen übersetzen will, kann ja mal 03:26.570 --> 03:26.990 sein. 03:31.290 --> 03:37.310 Allerdings häufig dann vielleicht eher nicht von Hexadezimal nach 03:37.310 --> 03:39.590 Binärdarstellung, sondern eher umgekehrt. 03:41.010 --> 03:45.430 Weil, naja, wenn Sie so eine Zahl wirklich als Bitstring 03:45.430 --> 03:47.810 repräsentieren, dann ist der sehr schnell, sehr lang und 03:47.810 --> 03:48.630 unübersichtlich. 03:49.430 --> 03:54.150 Und wenn Sie erlauben, eben sozusagen mehr Ziffern zu haben, wo eine 03:54.150 --> 03:57.070 Ziffer mehrere verschiedene Bedeutungen haben kann, dann wird das 03:57.070 --> 03:57.810 Ganze kürzer. 03:59.150 --> 04:05.230 Also manchmal ist es schön, dass man durch Übersetzung das Ganze 04:05.230 --> 04:06.130 lesbarer macht. 04:06.450 --> 04:10.670 Zum Beispiel, das ist nicht immer identisch, aber manchmal, wenn es 04:10.670 --> 04:13.610 kürzer wird, ist es halt leichter zu erfassen, besser zu lesen. 04:15.790 --> 04:18.350 A3 ist irgendwie leichter als dieses Ding da. 04:20.110 --> 04:23.070 Oben drüber steht schon ein anderer Grund, weshalb man manchmal 04:23.070 --> 04:24.250 Übersetzungen machen muss. 04:26.230 --> 04:29.030 Also zum Beispiel früher, wenn Sie E-Mails verschickt haben, da 04:29.030 --> 04:32.970 durften eben nur bestimmte Zeichen vorkommen in einer E-Mail und keine 04:32.970 --> 04:33.350 anderen. 04:34.110 --> 04:36.850 Und dann müssen Sie vielleicht eben Dinge aus einem großen Zeichensatz 04:36.850 --> 04:41.550 in einen kleinen übersetzen, damit Sie eine legale Repräsentation 04:41.550 --> 04:44.030 haben, mit der Sie irgendetwas machen können und dann irgendwann 04:44.030 --> 04:46.110 machen Sie es wieder rückgängig, haben wieder das Original. 04:49.210 --> 04:51.750 Also das sind plausible Dinge. 04:52.270 --> 04:55.410 Dann manchmal sozusagen genau das Gegenteil von Lesbarkeit, nämlich 04:55.410 --> 04:58.590 Verschlüsselung, zumindest keine Lesbarkeit für Außenstehende. 04:59.610 --> 05:04.110 Sowas sehen Sie dann ausführlich in Vorlesungen über Kryptografie und 05:04.110 --> 05:04.470 Sicherheit. 05:09.970 --> 05:13.710 Das Erste ist, man kann etwas verschlüsseln, sodass jemand nicht ohne 05:13.710 --> 05:18.010 weiteres oder mit nach heutigem Kenntnisstand also nur unvertretbar 05:18.010 --> 05:21.010 hohem Aufwand herausfinden kann, was ist hier verschlüsselt worden. 05:21.790 --> 05:27.670 Noch lustiger oder interessanter finde ich ja, dass man das soweit 05:27.670 --> 05:30.050 treiben kann mit der Verschlüsselung, dass Sie mit den verschlüsselten 05:30.050 --> 05:32.550 Dingen, also stellen Sie sich vor, Sie wollen Zahlen verschlüsseln, 05:32.830 --> 05:34.450 dass man mit den verschlüsselten Dingen immer noch ein bisschen Zeit 05:34.450 --> 05:34.450 hat. 05:34.450 --> 05:35.390 Und noch rechnen kann. 05:37.250 --> 05:42.190 Ohne, dass jeweils herauskommt, was waren die Originalwerte. 05:42.770 --> 05:43.510 Richtig cool. 05:46.750 --> 05:51.630 Dann da oben bei diesem Beispiel zwischen Binär und Hexadezimal sieht 05:51.630 --> 05:53.570 man, die Hexadezimaldarstellung ist kürzer. 05:53.670 --> 05:57.050 Das liegt daran, dass man mehr Symbole, mehr einzelne Zeichen, Ziffern 05:57.050 --> 05:57.810 zur Verfügung hat. 05:58.790 --> 06:01.870 Manchmal kriegt man es auch hin, und das werden wir uns gleich im 06:01.870 --> 06:05.350 letzten Abschnitt bei Huffman Codierung im Detail angucken, dass man 06:05.350 --> 06:10.270 ohne das Alphabet größer zu machen, jedenfalls manche Wörter so 06:10.270 --> 06:12.470 übersetzen kann, dass sie kleiner werden, kürzer. 06:12.750 --> 06:14.190 Das ist dann also Kompression. 06:16.390 --> 06:20.310 Das kann nicht für, wenn Sie das Alphabet festhalten, das kann nicht 06:20.310 --> 06:21.850 für alle Wörter funktionieren. 06:22.890 --> 06:26.650 So viele kurze Wörter gibt es gar nicht, um alle langen Wörter 06:26.650 --> 06:30.510 adäquat, ohne Informationsverlust zu repräsentieren. 06:30.930 --> 06:35.430 Aber wenn man weiß, was man kleiner kriegen will, und man sich 06:35.430 --> 06:39.110 aussuchen kann, wie man es kodiert, dann geht das, was Sie bei Huffman 06:39.110 --> 06:39.830 Codierung sehen. 06:40.970 --> 06:45.870 Und manchmal tatsächlich will man Dinge gar nicht kürzer machen, 06:46.010 --> 06:48.550 sondern ist bereit, Wörter ein bisschen länger zu machen. 06:51.390 --> 06:55.610 Weil Sie dann, wenn Sie sich vorstellen, Sie haben eine Bitfolge und 06:55.610 --> 06:58.270 übertragen die und unterwegs kann was kaputt gehen. 06:58.790 --> 07:03.250 Also denken Sie an so Sonden wie, wie hieß die, New Horizon, die da 07:03.250 --> 07:06.170 irgendwie inzwischen, ich weiß nicht, wie viele Milliarden Kilometer 07:06.170 --> 07:09.190 weg ist, und dann immer noch so ein bisschen was sendet. 07:09.630 --> 07:13.350 Und es kommt auch noch was auf der Erde an, aber natürlich nicht mehr 07:13.350 --> 07:15.690 alles eins zu eins genau fehlerfrei. 07:16.450 --> 07:21.430 Und dann baut man das Ding natürlich so, dass man bei dem, was auf der 07:21.430 --> 07:25.230 Erde ankommt, was jetzt vielleicht an ein paar Stellen falsch ist, 07:25.910 --> 07:29.950 zumindest erkennen kann, dass irgendwo Fehler aufgetreten sind und 07:29.950 --> 07:33.590 vielleicht sogar, wenn es nicht zu viele Fehler sind, Fehler 07:33.590 --> 07:34.510 korrigieren kann. 07:35.390 --> 07:41.050 Also eine Primitivmethode ist, Sie übertragen halt jedes Zeichen 07:41.050 --> 07:41.570 dreimal. 07:42.470 --> 07:46.430 Dann beim Empfänger nimmt er immer drei und guckt, unterstellen wir 07:46.430 --> 07:48.870 mal, es sind nur Nullen und Eins und entscheidet sich immer das, was 07:48.870 --> 07:50.130 in der Mehrheit da ist. 07:51.810 --> 07:53.330 Aber das ist eine plumpe Methode. 07:53.490 --> 07:55.890 Es gibt weitaus geschickteres und wenn Sie mal eine Vorlesung über 07:55.890 --> 07:59.510 Codierungstheorie zum Beispiel hören, da werden Sie sehen, was man da 07:59.510 --> 08:00.470 alles anstellen kann. 08:01.310 --> 08:04.270 Und das ist übrigens auch eine Stelle, wo zum Beispiel lineare Algebra 08:04.270 --> 08:06.990 wieder auftaucht, nur um das mal so am Rand zu erwähnen. 08:08.430 --> 08:09.290 Aber nicht nur da. 08:10.710 --> 08:14.750 So, also Übersetzungen sind durchaus manchmal sinnvoll und dass man 08:14.750 --> 08:19.710 das tatsächlich bei Kompressionen einsetzen kann, und zwar so, dass 08:19.710 --> 08:23.610 man hinterher von dem kurzen, übersetzten Ding wieder zurückkommt zum 08:23.610 --> 08:27.430 Original, ohne Informationsverlust, das gucken wir uns dann gleich 08:27.430 --> 08:27.850 noch an. 08:34.200 --> 08:38.380 Genau, also das ist nicht immer, aber manchmal das, was man möchte, 08:38.800 --> 08:41.820 wenn man etwas übersetzt hat, man weiß noch, was war das Original. 08:43.300 --> 08:44.360 Das muss nicht so sein. 08:44.480 --> 08:47.340 Also wenn Sie ein Java-Programm nehmen und überall da, wo zwei 08:47.340 --> 08:52.400 außerhalb von String-Konstanten, da wo der Benutzer, der 08:52.400 --> 08:55.460 Programmierer, zweimal Leertaste gedrückt hat, wenn Sie da von den 08:55.460 --> 08:59.040 zwei Spaces, von den zwei Leerzeichen eins entfernen, die Bedeutung 08:59.040 --> 08:59.900 ändert es ja nicht. 09:00.460 --> 09:02.740 Aber dann haben Sie was gemacht, da kommen Sie nicht mehr zurück. 09:02.980 --> 09:04.960 Also das ist manchmal auch sinnvoll. 09:04.960 --> 09:10.820 Aber gerade bei Verschlüsselung oder Kompression, da möchten Sie 09:10.820 --> 09:13.280 zurückkommen zum Original eins zu eins. 09:13.940 --> 09:16.200 Jedenfalls bei manchen Kompressionsverfahren. 09:17.240 --> 09:22.780 Auch wenn Sie schon mal auf dem Rechner Bilder gesehen haben, in so 09:22.780 --> 09:30.760 einem Format, das heißt JPEG, das kann man auch so machen, dass 09:30.760 --> 09:32.260 Information verloren geht. 09:33.520 --> 09:37.380 Aber wenn Sie den Himmel fotografiert haben, alles ist mehr oder 09:37.380 --> 09:41.820 weniger blau, da werden zum Beispiel salopp gesprochen so kleine 09:41.820 --> 09:43.820 Unterschiede im Blau, die werden einfach weggemacht. 09:44.660 --> 09:45.180 Einheitsblau. 09:45.880 --> 09:47.060 So plump ist es nicht. 09:47.360 --> 09:53.880 Aber was uns interessiert ist, Übersetzungen sind injektiv, das heißt, 09:54.260 --> 09:57.740 wenn Sie etwas Übersetztes haben, dann kann das nur von einem Original 09:57.740 --> 09:59.020 stammen und nicht von verschiedenen. 09:59.020 --> 10:00.260 Injektive Abbildung. 10:00.860 --> 10:03.240 Verschiedene Originale haben verschiedene Bilder, verschiedene 10:03.240 --> 10:03.940 Übersetzungen. 10:05.860 --> 10:08.340 So, und so Übersetzungen mit so einer injektiven Abbildung, die wollen 10:08.340 --> 10:12.100 wir Kodierungen nennen und die Funktionswerte, die kodierten 10:12.100 --> 10:14.880 Originale, die heißen dann auch Kodwörter und die Menge aller 10:14.880 --> 10:16.520 Kodwörter heißt dann manchmal auch Code. 10:19.900 --> 10:22.880 Und ich bin, glaube ich, auf meinen Folien auch nicht ganz sauber mit 10:22.880 --> 10:24.800 den Formulierungen, aber das ist die Idee. 10:26.140 --> 10:30.140 So, und da ist die Frage, wie legt man denn so eine Übersetzung fest? 10:30.360 --> 10:36.620 Sie wollen jetzt meinetwegen jedes Java-Programm übersetzen in ein 10:37.380 --> 10:40.400 Assembler -Programm oder C oder Haskell oder irgendwie was. 10:40.860 --> 10:43.800 Da müssen Sie für unendlich viele Wörter festlegen, wie das übersetzt 10:43.800 --> 10:44.380 werden soll. 10:45.720 --> 10:50.700 Und wenn man eines will in der Informatik, bitte ein Rahmen übers Bett 10:50.700 --> 10:53.880 hängen, dann ist das, dass alles endlich beschreibbar ist. 10:54.900 --> 10:58.380 Also Sie müssen jetzt eine endliche Beschreibung finden, die Ihnen 10:58.380 --> 11:01.640 sagt, für jedes von unendlich vielen Wörtern, das Sie übersetzen 11:01.640 --> 11:02.880 wollen, wie geht das denn? 11:03.220 --> 11:04.240 Und was kommt dann raus? 11:07.240 --> 11:11.440 Und zwei harmlose Fälle, es gibt kompliziertere natürlich, sind 11:11.440 --> 11:13.600 sogenannte Homomorphismen und Blockkodierungen. 11:14.280 --> 11:16.400 Und das wollen wir uns jetzt so ein bisschen angucken. 11:16.400 --> 11:19.980 Und zum Beispiel die Huffman-Kodierung, das wird einfach ein 11:19.980 --> 11:21.100 Homomorphismus sein. 11:22.900 --> 11:26.160 Und das kann man dann so ein bisschen aufbohren zu Blockkodierungen 11:26.160 --> 11:28.940 und dann kriegt man auch tatsächlich ein Kompressionsverfahren. 11:30.480 --> 11:31.940 Was sind Homomorphismen? 11:33.900 --> 11:39.740 Also das sind Abbildungen von Menge aller Wörter über einem Alphabet 11:39.740 --> 11:43.920 in Menge aller Wörter über irgendeinem potenziell anderen Alphabet, 11:44.080 --> 11:45.280 kann natürlich auch das Gleiche sein. 11:47.280 --> 11:50.560 Und von einem Homomorphismus jetzt hier in diesem Zusammenhang 11:50.560 --> 11:55.240 verlangt man was Ähnliches, wie Sie vielleicht in lineare Algebra bei 11:55.240 --> 11:59.680 Homomorphismus verlangt haben, nämlich Verträglichkeit mit einer 11:59.680 --> 12:03.760 Operation auf den Objekten und die natürliche Operation, die wir bei 12:03.760 --> 12:07.320 Wörtern aus A-Stern und B-Stern haben, ist Konkatenation. 12:08.340 --> 12:11.920 Und ein Homomorphismus ist dann also so eine Abbildung, die diese 12:11.920 --> 12:16.720 Eigenschaft hat, egal für jedes Wort W1 und jedes Wort W2 aus A-Stern. 12:18.340 --> 12:22.780 Ob Sie die erst Konkatenieren, W1, W2 und dann das längere Wort mit 12:22.780 --> 12:27.620 dem Homomorphismus abbilden, H von W1, W2 oder ob Sie die beiden 12:27.620 --> 12:31.240 Faktoren W1, W2 getrennt abbilden mit dem Homomorphismus und die 12:31.240 --> 12:34.740 Funktionswerte Konkatenieren, es kommt das Gleiche raus. 12:36.600 --> 12:37.880 Das ist ein Homomorphismus. 12:44.040 --> 12:48.900 Stellen Sie sich vor, wir haben in dem Alphabet A klein a und klein b 12:48.900 --> 12:53.460 und im Alphabet B 0 und 1 und stellen Sie sich vor, es ist festgelegt, 12:53.620 --> 12:58.540 jedenfalls H von klein a ist 1,0 und H von klein b ist 0,0,1. 13:01.540 --> 13:05.320 Wenn das tatsächlich ein Homomorphismus ist, dann muss also diese 13:05.320 --> 13:06.180 Regel hier gelten. 13:07.020 --> 13:11.060 In der Definition von Homomorphismus und das heißt, der Homomorphismus 13:11.060 --> 13:15.500 muss BAB abbilden, auch wenn Sie jetzt das Wort zum Beispiel nach dem 13:15.500 --> 13:20.560 zweiten Symbol zerhacken und sagen W1 ist BA W2 ist B, dann muss das 13:20.560 --> 13:25.800 also gleich H von BA konkateniert mit H von B sein und H von BA muss H 13:25.800 --> 13:27.800 von B konkateniert mit H von A sein. 13:28.800 --> 13:32.800 Und dann haben wir das runtergeprügelt auf Bilder einzelner Symbole 13:32.800 --> 13:36.060 und da haben wir gesagt, wie das aussieht und da kommt halt irgendein 13:36.060 --> 13:36.660 Wort raus. 13:40.340 --> 13:44.400 Und dann wäre also aber dadurch, dass offensichtlich dadurch, dass wir 13:44.400 --> 13:47.520 die Bilder von klein a und klein b, also von den einzelnen Symbolen 13:47.520 --> 13:51.300 festgelegt haben, haben wir irgendwie alles weitere auch festgelegt, 13:51.400 --> 13:56.400 weil man die Abbildung, das Bild von längeren Wörtern eben mit dieser 13:56.400 --> 13:59.500 Regel H von W1 W2 ist H W1 mal H W2. 13:59.500 --> 14:03.260 Können Sie einmal das Wort zerhacken und dann wissen Sie, was 14:03.260 --> 14:03.800 rauskommt. 14:04.320 --> 14:07.500 Das ergibt sich dann automatisch für längere Wörter. 14:12.120 --> 14:17.220 So nebenbei, falls Sie das irgendwo mal lesen, ein Homomorphismus 14:17.220 --> 14:21.440 heißt epsilonfrei, wenn die Bilder der einzelnen Symbole, also hier H 14:21.440 --> 14:25.500 von A und H von B, wenn keins von diesen Bildern das leere Wort ist. 14:27.700 --> 14:30.500 Das ist nicht verboten, also im Allgemeinen man darf das machen. 14:30.600 --> 14:33.640 Sie können auch alle Symbole aufs leere Wort abbilden, dann egal 14:33.640 --> 14:36.180 welches Wort, alles wird aufs leere Wort abgebildet. 14:36.720 --> 14:38.960 Das ist der genaue Gegenteil von Injektiv. 14:39.120 --> 14:40.560 Immer kommt das leere Wort raus. 14:40.680 --> 14:42.380 Das will man selten haben. 14:45.520 --> 14:50.140 Wenn Sie so einen Homomorphismus haben, es gilt also immer H von W1 W2 14:50.140 --> 14:55.960 ist H von W1 mal H von W2, also konkateniert, dann was ist das Bild 14:55.960 --> 14:57.100 des leeren Wortes? 14:57.220 --> 15:01.240 Das leere Wort ist ja, können Sie auch sagen zweimal das leere Wort 15:01.240 --> 15:05.280 hintereinander und dann können Sie diese Regel hier anwenden für W1 15:05.280 --> 15:09.160 gleich W2 gleich leeres Wort, dann steht da, das ist H von Epsilon 15:09.160 --> 15:14.660 konkateniert mit H von Epsilon und dann steht also H von Epsilon ist H 15:14.660 --> 15:16.560 von Epsilon konkateniert mit H von Epsilon. 15:16.740 --> 15:20.480 Wenn Sie sich dann die Wortlängen angucken, dann sehen Sie, H von 15:20.480 --> 15:24.700 Epsilon muss offensichtlich Länge 0 haben und das heißt, das leere 15:24.700 --> 15:26.700 Wort wird immer aufs leere Wort abgebildet. 15:26.860 --> 15:30.420 Also das fällt da automatisch für alle Homomorphismen gleich mit raus. 15:30.840 --> 15:33.320 Also das leere Wort wird immer aufs leere Wort abgebildet. 15:37.560 --> 15:41.500 Wir haben gerade schon gesehen, also wenn man für einzelne Symbole, da 15:41.500 --> 15:44.380 im Beispiel war das klein a und klein b, wenn wir die einzelnen 15:44.380 --> 15:47.440 Symbole festlegen, was sind die Bilder, dann für längere Wörter, es 15:47.440 --> 15:50.560 ergibt sich automatisch, da haben Sie keine Wahl mehr. 15:52.040 --> 15:57.020 Also etwas allgemeiner, wenn Sie zwei Homomorphismen haben, H von A 15:57.020 --> 16:02.380 -Stern nach B-Stern und G von A-Stern nach B-Stern, dann, wenn für 16:02.380 --> 16:06.680 einzelne Symbole diese beiden Abbildungen das Gleiche tun, dann für 16:06.680 --> 16:09.140 alle längeren Wörter, sie müssen auch das Gleiche tun. 16:10.220 --> 16:11.760 Da kommt man nicht mehr drum rum. 16:12.620 --> 16:16.440 Also wenn für jedes X nur aus A schon gilt, dass H von X gleich G von 16:16.440 --> 16:22.280 X ist, dann für alle Wörter, egal wie lang oder kurz sie sind, immer H 16:22.280 --> 16:24.220 von W wird gleich G von W sein. 16:25.340 --> 16:26.660 Und wie beweist man das? 16:26.900 --> 16:30.960 Für alle Wörter, man macht wieder einmal eine vollständige Induktion 16:33.260 --> 16:36.200 und man sagt dann, man macht eine vollständige Induktion über die 16:36.200 --> 16:36.780 Wortlänge. 16:37.920 --> 16:43.780 Das heißt, genau genommen, man zeigt für jedes N aus N-Null, die 16:43.780 --> 16:46.180 Behauptung gilt für alle Wörter der Länge N. 16:48.220 --> 16:51.520 Und dann ist also der Induktionsanfang, die Behauptung gilt für alle 16:51.520 --> 16:52.640 Wörter der Länge Null. 16:53.520 --> 16:55.500 Ja, da gibt es nur eins, das ist das leere Wort. 16:56.120 --> 17:00.920 Also der Induktionsanfang ist jetzt für das leere Wort, das zu 17:00.920 --> 17:01.460 überprüfen. 17:01.560 --> 17:05.920 Also hier diese Aussage, für jedes W aus A-Stern, es gilt H von B 17:05.920 --> 17:06.780 gleich G von W. 17:09.420 --> 17:12.860 Erster Fall, weil W hat die Länge Null, dann ist das das leere Wort. 17:13.200 --> 17:16.120 Dann H von Epsilon, haben wir uns gerade überlegt, wenn es ein 17:16.120 --> 17:17.700 Homomorphismus ist, ist es immer Epsilon. 17:18.300 --> 17:21.240 Und G von Epsilon, wenn G auch ein Homomorphismus ist, ist es auch 17:21.240 --> 17:21.660 Epsilon. 17:21.940 --> 17:23.000 Also ist das das Gleiche. 17:24.680 --> 17:26.540 Und dann kommt der Induktionsschritt. 17:29.720 --> 17:33.580 Wenn es für jedes Wort, für alle Wörter der Länge N gilt, dann gilt es 17:33.580 --> 17:35.500 auch für alle Wörter der Länge N plus 1. 17:38.240 --> 17:40.380 Also Induktionsvoraussetzung, das steht jetzt da auch gar nicht mehr 17:40.380 --> 17:41.560 so explizit. 17:41.700 --> 17:47.640 Sie merken so langsam, wir werden ein bisschen lockerer, aber das 17:47.640 --> 17:51.020 Wichtige ist, in Ihrem Kopf müssen Sie noch das Präzise haben. 17:51.540 --> 17:53.620 Man schreibt nur nicht mehr ganz so viel hin. 17:55.060 --> 17:57.220 Ich weiß nicht, ob Sie es gemerkt haben, wir sind inzwischen in der 17:57.220 --> 18:01.440 fünften Woche des Semesters, das heißt am Freitag ein Drittel des 18:01.440 --> 18:03.620 Semesters ist schon wieder vorbei, der Vorlesungszeit. 18:04.960 --> 18:10.080 Und Sie kriegen heute das fünfte Aufgabenblatt und da es nur 13 gibt, 18:11.300 --> 18:12.180 wenn das 13. 18:12.440 --> 18:13.220 geben Sie in der 14. 18:13.440 --> 18:14.400 Woche ab und in der 15. 18:14.620 --> 18:16.540 kriegen Sie es zurück und dann ist Vorlesungszeit vorbei. 18:17.240 --> 18:19.240 Also Sie haben auch schon ein Drittel der Übungsblätter hinter sich, 18:19.340 --> 18:19.880 mehr oder weniger. 18:22.460 --> 18:24.940 Und deswegen fangen wir dann auch irgendwann an, so ein bisschen über 18:24.940 --> 18:28.520 Prüfungen und Klausuren zu erzählen, so organisatorisches und 18:28.520 --> 18:29.500 inhaltliches und so. 18:31.440 --> 18:33.640 So, also wir sind jetzt ein bisschen großzügiger. 18:34.000 --> 18:36.620 Induktionsschritt von Länge n nach Länge n plus 1. 18:40.140 --> 18:40.580 Induktionsvoraussetzungen. 18:41.420 --> 18:44.720 Wir nehmen mal an, für ein n für alle Wörter der Länge n die 18:44.720 --> 18:45.520 Behauptung gilt. 18:45.720 --> 18:49.660 h von w ist gleich g von b für alle w aus a hoch n. 18:52.900 --> 18:54.420 Für alle Wörter der Länge n. 18:54.480 --> 18:56.980 Und jetzt müssen wir zeigen, es gilt auch für alle Wörter der Länge n 18:56.980 --> 18:57.560 plus 1. 18:58.460 --> 19:01.240 Und wie sehen Wörter der Länge n plus 1 aus? 19:02.140 --> 19:05.040 Das können Sie zum Beispiel sich so vorstellen, dass Sie eben ein Wort 19:05.040 --> 19:08.200 der Länge n haben und dann noch ein zusätzliches Symbol hintendran. 19:09.560 --> 19:16.180 So, also wir reden jetzt über Wörter der Form w der Länge n und ein 19:16.180 --> 19:17.380 Symbol x hintendran. 19:17.480 --> 19:22.840 Und wir müssen jetzt zeigen, unter der Induktionsvoraussetzung h von w 19:22.840 --> 19:27.140 ist gleich g von w, dann gilt auch h von wx ist gleich g von wx. 19:29.020 --> 19:31.740 Und bis jetzt hat man eigentlich noch gar nichts getan, außer sich 19:31.740 --> 19:34.100 noch mal klar zu machen, was eigentlich zu tun ist. 19:34.440 --> 19:38.080 Und jetzt ist die Stelle, wo man es tun muss, überhaupt das erste Mal. 19:38.580 --> 19:41.720 Und Sie werden gleich sehen, es ist wieder ganz einfach. 19:44.360 --> 19:47.500 Also man muss zeigen, h von wx ist gleich g von wx. 19:47.680 --> 19:49.740 Da fängt man halt zum Beispiel mit der linken Seite an. 19:49.780 --> 19:51.740 h von wx, was kann man da groß tun? 19:52.280 --> 19:54.180 Man weiß, h ist ein Homomorphismus. 19:54.380 --> 19:57.920 Okay, also dann h von wx ist h von w mal h von x. 19:59.580 --> 20:02.420 Dann ist man schon an der Stelle, wo man die Induktionsvoraussetzung 20:02.420 --> 20:03.200 anwenden kann. 20:03.340 --> 20:06.120 h von w ist gleich g von w für jedes w in der Länge n. 20:08.300 --> 20:10.360 Dann steht ja g von w mal h von x. 20:10.440 --> 20:12.740 Dann haben wir ja die Voraussetzung für einzelne Symbole. 20:12.980 --> 20:14.760 g und h tun das Gleiche. 20:15.260 --> 20:18.680 Also statt h von x einzelnes Symbol kann man auch g von x schreiben. 20:19.120 --> 20:21.720 Und dann verwendet man auch, dass g auch ein Homomorphismus ist, 20:21.720 --> 20:25.320 sozusagen rückwärts, und dann steht da ist gleich gwx und schon ist 20:25.320 --> 20:25.820 man fertig. 20:27.080 --> 20:30.540 Also man benutzt, dass h ein Homomorphismus ist, dass g ein 20:30.540 --> 20:33.920 Homomorphismus ist, die Induktionsvoraussetzung und die explizite 20:33.920 --> 20:37.660 Voraussetzung in dem Lemma, für einzelne Symbole machen die 20:37.660 --> 20:39.780 Abbildungen das Gleiche. 20:40.980 --> 20:42.260 So, und fertig ist man. 20:46.360 --> 20:51.960 Und das heißt mit anderen Worten, also wenn Sie für einzelne Symbole 20:51.960 --> 20:54.840 Funktionswerte festlegen, dann ist für alles ein Funktionswert 20:54.840 --> 20:55.440 festgelegt. 20:55.760 --> 21:00.460 Also wenn Sie eine Abbildung f haben, die ist einmal nur von a, für 21:00.460 --> 21:04.660 jedes einzelne Symbol irgendein Wort aus irgendeiner Menge b Sternen 21:04.660 --> 21:08.740 festlegt, dann können Sie das ergänzen, sozusagen zu einem 21:08.740 --> 21:13.740 Homomorphismus, der also jetzt für jedes Wort irgendwas vorschreibt. 21:14.380 --> 21:18.340 Und diese Ergänzung, diese in Anführungszeichen größere Funktion 21:18.340 --> 21:19.780 schreibe ich f Stern, Stern. 21:22.460 --> 21:24.220 Können Sie auch sonst irgendwie hinschreiben. 21:25.020 --> 21:28.400 Indem Sie sagen, also gut, das Bild des leeren Wortes ist das leere 21:28.400 --> 21:34.100 Wort und für jedes w und jedes aus a Stern und jedes x aus a f von bx 21:34.100 --> 21:38.560 f Stern, Stern von bx ist f Stern, Stern von w, konkretisiert mit f 21:38.560 --> 21:38.960 von x. 21:40.040 --> 21:42.620 Wenn man das so macht, dann kann man sich erstmal wieder überlegen, 21:42.620 --> 21:47.100 aha, das ist überhaupt sinnvoll für alle Wörter, ist etwas eindeutig 21:47.100 --> 21:52.360 schön definiert, ein Funktionswert und Behauptung, das ist dann 21:52.360 --> 21:54.080 tatsächlich ein Homomorphismus. 21:55.260 --> 21:58.520 Explizit, wenn Sie sich nur als zweiten Faktor ein einzelnes Symbol 21:58.520 --> 22:02.760 angucken, steht es hier ja schon in der Definition und wenn der zweite 22:02.760 --> 22:05.640 Faktor mehr ist als ein einzelnes Symbol, dann muss man halt noch ein 22:05.640 --> 22:06.480 bisschen was beweisen. 22:06.800 --> 22:08.800 Vollständige Induktion, Schema F. 22:09.880 --> 22:14.180 Also, wenn Sie für jedes Symbol was festlegen, dann liegt das sofort 22:14.180 --> 22:17.680 und zwar übrigens eindeutig, wie wir gerade gesehen haben, ein 22:17.680 --> 22:20.420 Homomorphismus fest, der für einzelne Symbole das gleiche tut. 22:21.760 --> 22:23.260 So, gut. 22:25.480 --> 22:29.740 Jetzt kommen wir gleich zu Präfixfreien Codes und da taucht das Wort 22:29.740 --> 22:32.760 Präfix auf, also Präfix ist ein Präfix von Präfixfrei. 22:35.160 --> 22:38.840 Also, wenn Sie ein Wort w haben, ein anderes Wort v heißt ein Präfix, 22:38.920 --> 22:40.320 wenn das ein Anfangsstück ist. 22:41.520 --> 22:45.420 Das heißt, v ist ein Präfix von w, wenn Sie ein u hinten dran kleben 22:45.420 --> 22:47.400 können, sodass vu gleich w ist. 22:48.420 --> 22:51.860 Und in so einer Situation heißt dann u auch ein Suffix von w. 22:52.020 --> 22:54.900 Also ein Suffix ist etwas, wo Sie das vorne dran kleben können, sodass 22:54.900 --> 22:56.120 sich das Wort w ergibt. 22:58.060 --> 23:00.000 So, Beispiele habe ich hier hingeschrieben. 23:00.460 --> 23:04.060 Das leere Wort ist Präfix von allem und Suffix von allem. 23:05.220 --> 23:08.120 Trivial, Sie können immer das Wort dahinter vorschreiben und Sie 23:08.120 --> 23:08.800 kriegen das Wort. 23:09.980 --> 23:15.560 Und beliebige Anfangsstücke vorne und hinten, also Anfangsstücke vorne 23:15.560 --> 23:19.760 heißen Präfix, Endstücke hinten heißen Suffix. 23:20.100 --> 23:24.840 Und das heißt übrigens im Deutschen das Präfix und das Suffix und 23:24.840 --> 23:25.280 nicht der. 23:27.100 --> 23:29.500 Also ein Präfix ist so ein Anfangsstück. 23:30.120 --> 23:37.520 Und dann gucken wir uns ganz spezielle Codes an, warum, werden wir 23:37.520 --> 23:41.400 dann gleich sehen, nämlich sogenannte Präfixfreie Codes. 23:41.560 --> 23:44.700 Also wir haben einen Homomorphismus von A-Stern nach B-Stern. 23:46.420 --> 23:51.040 Und was uns jetzt interessiert, ist dieser Fall, verschiedene Wörter 23:51.040 --> 23:52.120 haben verschiedene Bilder. 23:52.400 --> 23:55.200 Man kommt zurück zum Original, wenn man unbedingt will. 23:56.280 --> 23:59.100 Wie man das zum Beispiel bei Verschlüsselung ganz bestimmt will. 23:59.880 --> 24:03.220 Und wenn Sie irgendeinen normalen geschriebenen, getippten Text 24:03.220 --> 24:05.680 komprimieren, dann wollen Sie da wahrscheinlich auch zurück zum 24:05.680 --> 24:06.100 Original. 24:07.940 --> 24:14.120 Ob so ein Homomorphismus injektiv ist, das ist jetzt nicht so ganz 24:14.120 --> 24:17.500 einfach zu sehen, im Allgemeinen. 24:18.300 --> 24:23.100 Aber es gibt eben den einen Spezialfall, der ist schön und das ist 24:23.100 --> 24:28.740 der, dass ein sogenannter Präfixfreier Homomorphismus ist. 24:31.820 --> 24:37.620 Und ein Homomorphismus Homomorphismus heißt präfixfrei, wenn es Ihnen 24:37.620 --> 24:42.920 nicht passiert, dass Sie für zwei Symbole Codewörter festgelegt haben, 24:43.000 --> 24:44.980 wo das eine Präfix vom anderen ist. 24:46.700 --> 24:52.820 Also wenn Sie sich H von X1 und H von X2 angucken, wenn X1 und X2 24:52.820 --> 24:57.460 voneinander verschieden sind, dann ist H von X1 kein Präfix von H von 24:57.460 --> 24:57.960 X2. 24:58.320 --> 24:59.280 Oder auch nicht umgekehrt. 24:59.980 --> 25:05.120 Oder anders gesagt, wenn H von X1 Präfix von H von X2 ist, dann muss 25:05.120 --> 25:06.600 X1 gleich X2 sein. 25:07.800 --> 25:12.220 Und dann haben Sie gleich nicht Präfix, sondern ist das gleiche Wort. 25:14.100 --> 25:19.980 Also wenn Sie H von 0 festlegen, 100 und H von 1, 1010, dann ist das 25:19.980 --> 25:20.620 in Ordnung. 25:22.380 --> 25:26.280 Denn 100 ist offensichtlich nicht Anfangsstück von 1010. 25:26.900 --> 25:29.580 An der dritten Stelle unterscheiden sich die Wörter. 25:30.180 --> 25:31.380 Und umgekehrt auch nicht. 25:31.480 --> 25:34.760 Ein Wort der Länge 4 kann nicht Anfangsstück eines Wortes der Länge 3 25:34.760 --> 25:35.140 sein. 25:36.160 --> 25:36.680 Unmöglich. 25:39.680 --> 25:45.160 Und wenn zwei Wörter gleich lang sind, dann heißt eins Präfix vom 25:45.160 --> 25:47.240 anderen, sie sind gleich. 25:47.740 --> 25:51.120 Der Fall, wo man nachdenken muss, ist, die Länge ist unterschiedlich. 25:51.960 --> 25:56.740 Und was eben verboten ist, wäre sowas wie H von 0 ist 10 und H von 1 25:56.740 --> 25:59.140 fängt auch mit 10 an. 25:59.600 --> 26:01.100 1010 oder was auch immer. 26:01.920 --> 26:02.920 Das ist verboten. 26:06.340 --> 26:10.140 So, und wenn Sie sowas haben, so einen präfixfreien Homomorphismus, 26:11.380 --> 26:15.560 dann ist das tatsächlich sofort injektiv und Sie haben keine Probleme, 26:15.700 --> 26:17.900 etwas Kodiertes wieder zu dekodieren. 26:18.780 --> 26:20.060 Das werden wir uns gleich überlegen. 26:20.140 --> 26:21.320 Das ist dann ganz einfach. 26:22.420 --> 26:23.840 Offensichtlich, mehr oder weniger. 26:25.940 --> 26:27.740 Und das möchte man gerne haben. 26:27.940 --> 26:33.460 Also wenn Sie etwas kodieren, zerschlüsseln, komprimieren, was auch 26:33.460 --> 26:38.940 immer, dann möchten Sie, dass erstens diese Operation schnell geht und 26:38.940 --> 26:41.740 zweitens die umgekehrte Operation soll bitte auch schnell gehen. 26:41.860 --> 26:46.100 Also Sie möchten nicht etwas, was Sie in einer Sekunde komprimieren, 26:46.200 --> 26:48.940 da möchten Sie nicht beim Dekomprimieren einen Tag warten müssen. 26:49.460 --> 26:51.280 Es soll auch einfach sein alles. 26:51.920 --> 26:54.340 Und bei präfixfreien Codes ist alles einfach. 26:54.500 --> 26:56.920 Also nicht nur, Sie kommen zurück, es ist auch einfach. 26:58.400 --> 26:58.480 So. 27:00.940 --> 27:05.220 Ein Problem haben wir allerdings, wenn Sie so einen Homomorphismus 27:05.220 --> 27:11.460 haben, von A-Stern nach B-Stern, der mag ja injektiv sein, aber er 27:11.460 --> 27:13.500 wird im Allgemeinen nicht sujektiv sein. 27:13.640 --> 27:18.680 Also es wird Wörter geben in B-Stern, die kommen nicht als Codewort 27:18.680 --> 27:19.080 vor. 27:20.260 --> 27:21.180 Kann ja sein. 27:21.900 --> 27:27.260 Also zum Beispiel, wenn Sie alle Symbole kodieren durch Wörter gerader 27:27.260 --> 27:31.320 Länge, dann sind auch die Bilder von längeren Wörtern, Wörter gerader 27:31.320 --> 27:35.880 Länge und dann werden Sie kein Wort ungerader Länge sehen als 27:35.880 --> 27:36.860 Codewort. 27:38.100 --> 27:42.000 Also so Homomorphismen sind im Allgemeinen nicht sujektiv, aber diese 27:42.000 --> 27:44.820 Nicht -Codewörter interessieren ja auch nicht, wenn man zurück will. 27:46.860 --> 27:51.480 Also wir wollen dann im Allgemeinen so eine Abbildung U haben, zurück. 27:53.820 --> 27:57.980 Aber von B-Stern nach A-Stern ist doof. 27:59.420 --> 28:00.360 Das geht nicht immer. 28:00.720 --> 28:03.860 Also machen wir für den Rückweg erlauben wir ein zusätzliches Symbol. 28:05.560 --> 28:07.940 Ich lese das jetzt mal einfach als undefiniert. 28:10.920 --> 28:15.640 Und wenn Sie mit der Abbildung zurück, wenn Sie die anwenden auf 28:15.640 --> 28:19.080 etwas, was gar nicht Kodierung eines Originalworts ist, dann sollte 28:19.080 --> 28:20.600 einfach irgendwas rauskommen. 28:20.700 --> 28:22.740 Hauptsache irgendwo steht undefiniert. 28:23.740 --> 28:25.600 Einfach damit wir es bequem haben. 28:26.540 --> 28:29.380 Also die Abbildung zurück geht von B-Stern nach A-Vereinigt 28:29.380 --> 28:30.380 undefiniert -Stern. 28:33.320 --> 28:37.800 Und jetzt nehmen Sie mal als Beispiel diesen Homomorphismus von A, B, 28:37.940 --> 28:39.640 C -Stern nach 0,1-Sterne. 28:40.740 --> 28:45.400 H von A ist 1, H von B ist 0,1 und H von C ist 0,0,1. 28:46.720 --> 28:52.560 So wenn Sie sich das angucken, dann sehen Sie H von A, die 1, ist 28:52.560 --> 28:55.160 nicht Präfix von H von B und H von C. 28:55.760 --> 28:56.920 Die fangen beide mit 0 an. 28:58.880 --> 29:03.360 Und H von B, das 0,1 ist auch nicht Präfix von 0,0,1. 29:04.020 --> 29:05.480 Fängt ja mit 0,0 an. 29:07.800 --> 29:11.280 Und die Wörter sind auch alle unterschiedlich lang und ein längeres 29:11.280 --> 29:13.380 kann sowieso nicht Präfix eines kürzeren sein. 29:13.500 --> 29:19.040 Das heißt, kein Codewort, also für diese drei von H von A, H von B, H 29:19.040 --> 29:22.060 von C, keins ist Anfangsstück eines anderen. 29:22.760 --> 29:25.900 Also das ist tatsächlich Präfixfrei. 29:25.900 --> 29:27.900 Das ist der Fall, den wir angucken wollen. 29:28.780 --> 29:30.580 Nur der Fall interessiert uns noch. 29:31.820 --> 29:35.100 Und wir werden auch gleich bei der Dekodierung an einer Stelle massiv 29:35.100 --> 29:37.400 ausnutzen, dass das Ding Präfixfrei ist. 29:39.420 --> 29:42.700 So und jetzt wollen wir also eine Abbildung in die umgekehrte Richtung 29:42.700 --> 29:47.140 von 0,1 Stern nach dem A, B, C und zusätzlich dieses undefiniert 29:47.140 --> 29:47.820 Zeichen Stern. 29:48.800 --> 29:54.840 Und was wir halt gerne möchten, also wenn Sie C mit dem Homomorphismus 29:54.840 --> 29:56.540 abbilden, kommt 0,0,1 raus. 29:56.660 --> 29:59.540 Das heißt, mit der Abbildung U, wenn man die auf 0,0,1 anwendet, 29:59.920 --> 30:01.260 sollte bitte C rauskommen. 30:04.320 --> 30:09.040 Wenn Sie den Homomorphismus auf BB anwenden, dann kommt da 0,1,0,1 30:09.040 --> 30:09.360 raus. 30:09.500 --> 30:13.360 Das heißt, Abbildung U angewendet auf 0,1,0,1 sollte BB liefern. 30:15.840 --> 30:22.120 Und wenn Sie diese Abbildung U auf eine einzelne 0 anwenden, dieses 30:22.120 --> 30:27.100 Wort der Länge 1, dann sollte da undefiniert oder sowas rauskommen, 30:27.240 --> 30:33.060 denn egal was Sie tun, Sie werden mit dem Homomorphismus egal welches 30:33.060 --> 30:35.940 Wort Sie abbilden, nie bei einer einzelnen 0 landen. 30:37.040 --> 30:41.060 Also wenn Sie nur Bs und Cs haben, dann sind Sie, sobald Sie 30:41.060 --> 30:45.460 mindestens ein B oder C haben, sind Sie länger als Länge 1 und wenn 30:45.460 --> 30:49.440 Sie Länge 1 haben wollen, dann können Sie nur ein A abbilden und das 30:49.440 --> 30:50.800 liefert aber eine 1 und keine 0. 30:52.720 --> 30:59.400 Und das Lehrewort kann es auch nicht sein, denn auf das Lehrewort wird 30:59.400 --> 31:01.340 nur das Lehrewort abgebildet und nichts anderes. 31:02.940 --> 31:09.200 Also so ein U wollen wir jetzt haben und zwar am Ende sozusagen für 31:09.200 --> 31:10.920 jedes präfixfreie H. 31:12.360 --> 31:15.180 Jetzt gucken wir uns aber erst mal eben dieses Beispiel an. 31:16.200 --> 31:19.920 Was würde man denn tun, wenn man da irgendwas kriegt und wird jetzt 31:19.920 --> 31:23.400 gefragt, von welchem Wort sind wir denn hierhin gekommen? 31:27.580 --> 31:32.220 Also stellen Sie sich vor, Sie haben 100101 als Codewort. 31:32.900 --> 31:35.560 Das kriegen Sie, wenn Sie ACB abbilden. 31:35.920 --> 31:39.400 Aus A wird 1, aus C wird 001, aus B wird 01. 31:40.240 --> 31:42.760 Und jetzt die Abbildung U soll das rückwärts machen. 31:42.940 --> 31:44.760 Na ja, was würden Sie denn tun? 31:46.920 --> 31:47.880 Sie gucken... 31:47.880 --> 31:51.240 Also wir unterstellen mal, das ist ein Codewort. 31:52.520 --> 31:55.660 Falls die Unterstellung falsch ist, sollten wir das irgendwann merken. 31:56.500 --> 31:59.460 Aber tun wir mal so, als wäre das ein Codewort. 32:00.240 --> 32:02.220 Dann, was sehen wir denn? 32:02.280 --> 32:03.640 Hier vorne sehen wir eine 1. 32:06.080 --> 32:12.640 Jedenfalls irgendein Anfangsstück von 100101 muss ja das Codewort des 32:12.640 --> 32:13.820 ersten Symbols sein. 32:13.820 --> 32:17.760 Also H von A oder H von B oder H von C. 32:18.800 --> 32:21.560 Und das erste Symbol sollte eine 1 sein. 32:22.320 --> 32:25.900 Da gibt es aber nur eine Möglichkeit, nämlich wenn im Originalwort das 32:25.900 --> 32:28.660 erste ein A war, dann kriegen wir direkt eine 1. 32:32.410 --> 32:33.210 Und deswegen... 32:33.210 --> 32:39.290 Es gibt, und jetzt Präfixfreiheit, es kann jetzt nicht sein, dass Sie 32:39.290 --> 32:44.390 noch sowas längeres finden, 10100 irgendwas, was auch ein Codewort 32:44.390 --> 32:44.630 ist. 32:44.790 --> 32:46.190 Denn 1 ist ja schon ein Codewort. 32:47.410 --> 32:50.050 Und der Code ist präfixfrei. 32:51.130 --> 32:53.710 Also kann es nichts längeres geben, was auch noch ein Codewort ist, 32:53.750 --> 32:54.710 was mit 1 anfängt. 32:55.710 --> 33:00.050 Deswegen kann man einfach sagen, wenn das Wort, das wir dekodieren 33:00.050 --> 33:03.430 wollen, mit einer 1 anfängt, dann wissen wir das erste Symbol des 33:03.430 --> 33:04.710 Originals, das ist ein A. 33:05.410 --> 33:09.410 Und was wir dann noch dekodieren müssen mit U ist der Rest der Suffix 33:09.410 --> 33:10.310 hinter der 1. 33:11.090 --> 33:14.110 Also aus der 1 rückwärts wissen wir, das kam von einem A. 33:14.250 --> 33:17.170 Und dann müssen wir noch zurückgehen für das 00101. 33:19.950 --> 33:22.090 So, das fängt jetzt mal nicht mit einer 1 an. 33:22.370 --> 33:27.090 Also das nächste Stückchen unterstellt, es ist überhaupt ein Codewort, 33:27.730 --> 33:29.270 kann nicht von einem A kommen. 33:29.870 --> 33:30.750 Na ja, was kann denn noch sein? 33:32.670 --> 33:36.850 Wenn das nächste von einem B käme, müsste es mit 01 anfangen. 33:36.850 --> 33:42.270 Wenn es von einem C käme mit 001 und da steht 001, nicht 01. 33:43.110 --> 33:46.270 Also die nächsten drei Symbole, das kommt von dem C. 33:46.910 --> 33:49.330 Schreiben wir das auch schon mal hin und dann müssen wir noch den Rest 33:49.330 --> 33:52.010 codieren, der dahinter steht, das ist dieses Suffix 01. 33:52.690 --> 33:56.730 Und 01 ist auch ein Codewort, das muss von einem B kommen. 33:56.850 --> 33:59.190 Schreiben wir das auch noch hin und dann bleibt noch zu dekodieren das 33:59.190 --> 33:59.790 leere Wort. 34:00.510 --> 34:02.890 Und das leere Wort kommt immer vom leeren Wort und wir sind fertig. 34:02.890 --> 34:04.370 Da ist eine Frage. 34:11.760 --> 34:16.520 Also die Frage ist jetzt hier beim zweiten Schritt, woher weiß ich, 34:16.820 --> 34:21.420 dass ich jetzt hier hinter dem A ein C hinschreiben darf und nicht 34:21.420 --> 34:23.640 eine 0 und dann ein B. 34:23.760 --> 34:25.540 01 ist ja Codierung von B. 34:26.260 --> 34:29.000 Das liegt daran, dass wir die 0 gar nicht im Original haben. 34:30.440 --> 34:33.980 Also wir können am Anfang haben wir nur ein Wort aus A´s, B´s und C´s. 34:34.100 --> 34:35.200 Da stehen keine Nullen. 34:35.780 --> 34:38.040 Deswegen, wenn wir jetzt dekodieren, es kann nicht sein, dass wir hier 34:38.040 --> 34:39.260 eine 0 hinschreiben dürfen. 34:39.980 --> 34:40.920 Haben wir gar nicht. 34:43.840 --> 34:45.660 Achso, dass die 0 verkehrt ist. 34:46.800 --> 34:49.820 Also wir unterstellen, solange es geht, alles ist in Ordnung. 34:50.940 --> 34:51.540 Ja, so. 34:53.780 --> 34:59.000 Ansonsten könnte es natürlich auch sein, dass man tatsächlich von B, 34:59.040 --> 35:02.500 B, B, C, C, C, A, A kam und alles ist verkehrt oder irgendwie so. 35:05.020 --> 35:08.580 Also man unterstellt schon, es ist möglichst gut gegangen. 35:09.660 --> 35:12.000 Also was wir hier gemacht haben, ist sozusagen diese 35:12.000 --> 35:13.000 Fallunterscheidung. 35:13.140 --> 35:16.920 Man hat immer geguckt, bei dem, was man dekodieren muss, ist das nur 35:16.920 --> 35:17.880 noch das leere Wort. 35:18.400 --> 35:22.960 Fängt das mit dem Codewort für ein A an, fängt das mit dem Codewort 35:22.960 --> 35:27.760 für ein B an, fängt das mit dem Codewort für ein C an und weil der 35:27.760 --> 35:33.380 Codeprefix frei ist, kann es nicht sein, dass das, was wir noch 35:33.380 --> 35:37.860 dekodieren wollen, sowohl mit dem Codewort für ein A als auch für ein 35:37.860 --> 35:40.820 Zeichen als auch mit dem Codewort für ein anderes Zeichen anfängt. 35:41.700 --> 35:45.820 Da wäre eins Präfix vom anderen, vielleicht sogar gleich und das ist 35:45.820 --> 35:46.420 ja verboten. 35:48.060 --> 35:50.460 Deswegen hat das alles so gut funktioniert. 35:51.040 --> 35:55.240 Es war immer klar, egal, was hier vorne steht, bei dem, was wir noch 35:55.240 --> 36:00.720 dekodieren müssen, also wenn überhaupt, von welchem Zeichen kommt das 36:00.720 --> 36:00.960 denn? 36:01.600 --> 36:06.940 Und es kann natürlich passieren, dass eben, Sie da was haben, ein 36:06.940 --> 36:10.120 Anfangsstück, das kann von keinem Codewort kommen. 36:12.780 --> 36:13.300 Ja. 36:14.280 --> 36:18.120 Dann ist eben was kaputt, dann hat man etwas, was kein Codewort war. 36:19.360 --> 36:23.060 Und dann sagen wir einfach, okay, undefiniert, hör mal auf, alles 36:23.060 --> 36:23.540 kaputt. 36:24.460 --> 36:28.900 An der ersten Stelle, wo etwas falsch ist, wo man merkt, also 36:28.900 --> 36:31.300 spätestens hier ist jetzt etwas falsch. 36:35.600 --> 36:38.520 Das ist übrigens auch was bei der Übersetzung, sagen wir mal, von Java 36:38.520 --> 36:44.180 -Programmen, wenn Sie das durch den Compiler jagen, Sie möchten nicht, 36:44.320 --> 36:48.540 dass der Compiler nur an der ersten Stelle, wo etwas nicht mehr passt, 36:48.600 --> 36:52.860 sagt, aber hier ist jetzt was allerspätestens verkehrt und dann 36:52.860 --> 36:57.680 einfach aufhört und sagt, reparieren Sie erst mal das. 36:58.560 --> 37:01.880 Sie möchten, dass der Compiler weitermacht und die restlichen 5000 37:01.880 --> 37:07.060 Zeilen auch noch anguckt und das irgendwie halbwegs vernünftig tut, 37:07.200 --> 37:11.960 also sich sozusagen dann irgendeine Unterstellung sozusagen macht, na 37:11.960 --> 37:15.440 ja, vielleicht fehlt hier ja nur ein Semikolon oder irgendwas ganz 37:15.440 --> 37:16.040 Kleines. 37:16.400 --> 37:20.540 Jetzt tun wir mal so als stünde das da und machen mal weiter und 37:20.540 --> 37:22.140 schauen mal, ob es gut weitergeht. 37:22.700 --> 37:27.220 Das ist der schwierige Teil von Übersetzerbau, also bei dem Teil, wo 37:27.220 --> 37:28.320 man Übersetzung macht. 37:37.440 --> 37:41.220 Also dadurch, dass das Ding präfixfrei ist, ist Dekodierung ganz 37:41.220 --> 37:45.240 einfach und für präfixfreie Homomorphismen können Sie sozusagen 37:45.240 --> 37:48.180 generisch hier so hinschreiben, wie man die Umkehrabbildung 37:48.180 --> 37:52.020 veranstaltet, wenn Sie beim leeren Wort sind, hören Sie einfach auf, 37:52.120 --> 37:57.120 ist das leere Wort und wenn Sie noch nicht beim leeren Wort sind und 37:57.120 --> 38:05.520 es gibt ein Symbol des X aus dem Originalalphabet, dessen Codewort H 38:05.520 --> 38:11.320 von X, das Anfangsstück ist von W, dann sagen Sie, okay, ja, da 38:11.320 --> 38:14.800 dekodieren wir das mal zu einem X und das wir noch dekodieren müssen, 38:14.860 --> 38:18.700 ist der Rest dahinter und weil das Ding präfixfrei ist, kann das nur 38:18.700 --> 38:21.540 für genau ein Symbol passieren, nicht für verschiedene. 38:22.180 --> 38:25.900 Es kann nicht verschiedene Symbole geben und die Codewörter sind beide 38:25.900 --> 38:28.040 Anfangsstück von dem W. 38:28.580 --> 38:32.740 Das ist genau das, was Präfixfreiheit verhindert und deswegen ist das 38:33.920 --> 38:38.040 ganz wohl definiert, wie man sagt, es ist immer genau klar, was ist zu 38:38.040 --> 38:38.300 tun. 38:40.140 --> 38:43.200 Und dass das so einfach ist, liegt an der Präfixfreiheit. 38:43.200 --> 38:45.380 Ich weiß nicht, wie oft ich das betonen sollte. 38:46.440 --> 38:49.860 Das heißt nicht, dass präfixfreie Codes die einzigen sind, wo man 38:49.860 --> 38:50.560 zurückkommt. 38:52.180 --> 38:58.020 Es gibt auch nicht präfixfreie Codes, die man dekodieren kann, 38:58.860 --> 39:02.880 vielleicht sogar schön, also relativ einfach, aber es gibt auch 39:02.880 --> 39:07.280 Beispiele, die sind zwar injektiv, aber es ist ausgesprochen 39:07.280 --> 39:09.080 unangenehm, das zu dekodieren. 39:10.360 --> 39:14.660 Wir hatten da mal in einem früheren Jahr eine Aufgabe, wo man das mal 39:14.660 --> 39:15.460 rauskriegen sollte. 39:15.620 --> 39:17.160 Das kann richtig hässlich werden. 39:18.320 --> 39:18.540 Gut. 39:20.800 --> 39:23.700 Also jetzt wissen Sie, was präfixfreie Codes sind und dass man die 39:23.700 --> 39:25.140 leicht dekodieren kann. 39:25.920 --> 39:28.280 Und ein Beispiel kennen Sie wahrscheinlich, haben Sie schon mal 39:28.280 --> 39:31.160 gesehen von so einem präfixfreien Ding, nämlich UTF-8. 39:31.720 --> 39:34.360 Wer hat schon mal UTF-8 jedenfalls gelesen? 39:35.620 --> 39:36.020 Okay. 39:36.700 --> 39:37.980 Wer weiß, was das ist? 39:38.360 --> 39:40.160 Ach na ja, so ein bisschen was habe ich ja in der Vorlesung schon 39:40.160 --> 39:40.480 erzählt. 39:41.320 --> 39:44.420 Nee, ich habe über Unicode erzählt, nicht über UTF-8. 39:44.600 --> 39:48.280 Ich habe über Unicode erzählt, ein großes Alphabet und jedes Zeichen 39:48.280 --> 39:48.880 hatte eine Nummer. 39:50.500 --> 39:54.940 So, und UTF-8 ist jetzt eine Festlegung, diese Nummern für die 39:54.940 --> 39:56.820 Zeichen, wie schreiben wir sie denn hin? 39:58.320 --> 40:04.320 Und das macht man eben nicht, indem man für alle die Code Points, die 40:04.320 --> 40:08.600 Nummern aller Zeichen als gleich lange Binärzahlen oder etwas kodiert. 40:09.800 --> 40:14.560 Wenn die Beobachtung ist, also meinetwegen jetzt hier im europäischen 40:14.560 --> 40:19.360 Raum, ein Großteil der Zeichen stammt aus dem Bereich, der auch bei 40:19.360 --> 40:25.560 ASCII ist, hat Nummern zwischen 0 und 127 und wenn Sie da jedes Mal 4 40:25.560 --> 40:30.160 oder 6 Byte investieren, um ein kleines A oder ein großes X zu 40:30.160 --> 40:33.440 kodieren, dann ist das so ein bisschen verschwenderisch. 40:34.480 --> 40:40.280 Und UTF-8 ist so, dass diese Zeichen ganz kurze Kodierungen haben. 40:41.420 --> 40:45.200 Und nur wenn Sie so etwas, wie das Beispiel, das gleich kommt, das 40:45.200 --> 40:48.180 Integralzeichen haben, dann sind das ein paar Byte mehr. 40:49.380 --> 40:59.340 Also, UTF-8 ist jetzt, können wir sagen, ein Homomorphismus von alle 40:59.340 --> 41:03.920 Wörter aus allen Zeichen, die im Unicode-Alphabet vorkommen, das sind 41:03.920 --> 41:11.040 also irgendwie 100 und ein paar Tausend, nach Bitstrings-Wörter über 41:11.040 --> 41:12.440 dem Alphabet 0,1. 41:16.010 --> 41:19.870 Und das ist ein Homomorphismus, das heißt, wenn Sie mehrere Unicode 41:19.870 --> 41:22.230 -Zeichen hintereinander haben, wie kodieren Sie das? 41:22.330 --> 41:23.550 Na ja, jedes Zeichen für sich. 41:23.550 --> 41:24.850 Homomorphismus eben. 41:24.970 --> 41:25.970 Jedes Zeichen einzeln. 41:26.310 --> 41:28.110 Egal, was links und rechts davon steht. 41:29.650 --> 41:33.170 Und Sie werden gleich sehen, UTF-8 ist tatsächlich ein präfixfreier 41:33.170 --> 41:37.110 Homomorphismus und deswegen kann man so leicht zurück, dass das, was 41:37.110 --> 41:37.510 man will. 41:39.590 --> 41:46.170 So, und hier ist aus einem RFC sozusagen der wesentliche Teil nochmal 41:46.170 --> 41:46.850 hingeschrieben. 41:48.190 --> 41:50.730 Also, die Zeichen im Unicode haben ja alle Nummern. 41:52.270 --> 42:00.510 Und die Nummern, sind hier vier Bereiche von nicht-negativen ganzen 42:00.510 --> 42:04.170 Zahlen hingeschrieben und die Zahlen sind hexadezimal repräsentiert. 42:04.990 --> 42:10.530 Also, der erste Bereich ist von 0 bis 127, ja, 7f ist 127. 42:12.090 --> 42:17.750 Der nächste Bereich ist dann von 128 bis 7ff, das habe ich jetzt nicht 42:17.750 --> 42:18.870 mehr im Kopf, was das ist. 42:20.350 --> 42:30.550 Der nächste Bereich dann von 0800 bis ffff und der nächste Bereich 42:30.550 --> 42:40.070 fängt dann hier ein zweiter an bei 0001 bis dahin und dann ist vorbei. 42:40.750 --> 42:45.370 Also, bis jetzt sind nur in Anführungszeichen so viele Zeichen im 42:45.370 --> 42:47.910 Unicode, dass man keine größeren Zahlen braucht. 42:49.950 --> 42:56.990 So, und je nachdem, in welchem Bereich der Codepoint die Nummer eines 42:56.990 --> 43:00.670 Unicode -Zeichens ist, wird das auf die eine oder andere Weise 43:00.670 --> 43:03.710 abgebildet auf eine Folge von Nullen und Einsen. 43:04.770 --> 43:09.530 Und wenn das in dem Bereich von 0 bis 127 ist, hier der erste Bereich, 43:10.570 --> 43:16.770 dann die Codierung als Folge von Nullen und Einsen sind so acht Bits 43:16.770 --> 43:21.070 und das erste ist auf jeden Fall eine Null und dann kommen noch sieben 43:21.070 --> 43:23.530 dahinter und das ist einfach Binärdarstellung der Zahl. 43:26.350 --> 43:29.750 Und weil die Zahl so klein ist, 127 reichen da die sieben Stellen 43:29.750 --> 43:30.250 dahinter. 43:31.970 --> 43:37.750 Wenn die Zahl im nächsten Bereich ist ein bisschen größer, dann macht 43:37.750 --> 43:43.730 man daraus zwei Bytes und das erste Byte fängt auf jeden Fall mit 1, 43:43.730 --> 43:47.570 1, 0 an und dann kommen noch ein paar Nullen und Einsen dahinter und 43:47.570 --> 43:50.250 das zweite Byte fängt auf jeden Fall mit 1, 0 an. 43:51.230 --> 43:55.010 Und für den dritten Bereich macht man drei Bytes daraus und das erste 43:55.010 --> 44:00.510 Byte fängt mit 1, 1, 1, 0 an und die nächsten beiden mit 1, 0 und 1, 0 44:00.510 --> 44:06.150 und für den vierten Bereich, die erste Folge fängt mit 1, 1, 1, 1, 0 44:06.150 --> 44:09.530 an und die nächsten drei mit 1, 0, 1, 0, 1, 0 und insgesamt sind es 44:09.530 --> 44:10.990 vier Bytes. 44:12.530 --> 44:18.710 So, wenn Sie sich das angucken, denken Sie mal drüber und diese zwei, 44:19.050 --> 44:21.810 drei, vier Wörter untereinander geschrieben, das müssen Sie sich 44:21.810 --> 44:25.810 hintereinander vorstellen, das ist ein Wort, die Kodierung eines 44:25.810 --> 44:28.070 Zeichens, wenn die Nummer des Zeichens so groß ist. 44:29.890 --> 44:34.190 Und wenn Sie sich das so angucken, machen Sie sich mal klar, dass das 44:34.190 --> 44:35.410 Präfix frei ist. 44:36.890 --> 44:41.990 Also man muss ja wieder nur gucken, machen Sie das auch nochmal klar, 44:42.350 --> 44:46.230 sind kürzere vielleicht Anfangsstück von längeren Kodierungen, aber 44:46.230 --> 44:49.750 diese ganz kurzen hier, wo sie nur eine Bitfolge von acht Bits haben, 44:50.050 --> 44:53.130 die sind nie Anfangsstück von was Längerem, denn hier, da haben wir 44:53.130 --> 44:57.110 vorne eine 0, wenn es nur ein Byte ist und in allen anderen Fällen, 44:57.230 --> 45:00.050 das erste ist eine 1, das kann man deutlich unterscheiden, kein 45:00.050 --> 45:00.530 Präfix. 45:02.550 --> 45:08.290 Und die anderen drei Fälle, 2 Bytes, 3 Bytes, 4 Bytes, da sehen Sie, 45:09.810 --> 45:13.950 das erste Byte fängt mit unterschiedlich vielen Einsen und einer Null 45:13.950 --> 45:18.270 dahinter an und die Anzahl Einsen sagt einem auch gleich, wie viele 45:18.270 --> 45:19.430 Bytes sind es denn insgesamt. 45:19.670 --> 45:23.150 Also hier bei 1, 1, 0 haben wir hier zwei Einsen, insgesamt sind es 45:23.150 --> 45:23.810 zwei Bytes. 45:24.310 --> 45:27.710 Hier bei 1, 1, 1, 0 haben wir drei Einsen, insgesamt sind es drei 45:27.710 --> 45:31.730 Bytes und hier bei 1, 1, 1, 0 sind es vier Einsen, insgesamt sind es 45:31.730 --> 45:32.870 vier Bytes. 45:33.830 --> 45:36.910 Und das eine fängt mit drei Einsen und einer Null an, das andere fängt 45:36.910 --> 45:38.630 mit vier Einsen und einer Null an. 45:39.550 --> 45:42.810 1, 1, 1, 0 ist nicht Anfangsstück von 1, 1, 1, 1, 0. 45:43.550 --> 45:49.610 Also das ist wirklich präfixfrei und was man im Wesentlichen macht, 45:49.730 --> 45:52.990 ist man nimmt die Zahl, codiert sie, macht Binärdarstellung und 45:52.990 --> 45:55.930 schreibt dann die Bits an die Stellen, wo hier nur XXX steht. 45:57.730 --> 46:00.010 Und wenn Sie verschiedene Bitfolgen haben, kriegen Sie natürlich auch 46:00.010 --> 46:00.910 verschiedene Codierungen. 46:03.690 --> 46:08.590 Also Beispiel Integralzeichen, das ist irgendwo Unicode, der Code 46:08.590 --> 46:16.150 Point hexadezimal ist 2222B und da stellt man fest, wenn man in die 46:16.150 --> 46:18.130 Tabelle von eben guckt, das ist der dritte Fall. 46:20.090 --> 46:26.930 Also das ist offensichtlich kleiner als FFFF und ist aber größer als 46:28.130 --> 46:28.750 07FF. 46:29.350 --> 46:36.890 Also dieser Fall schlägt zu und das heißt, die UTF-8-Codierung besteht 46:36.890 --> 46:40.190 aus drei Bytes und die Anfangsstücke dieser drei Bytes liegen sowieso 46:40.190 --> 46:40.610 fest. 46:42.530 --> 46:48.250 Und um den Rest aufzufüllen, muss man diese Zahl nehmen, 2222B und das 46:48.250 --> 46:49.690 abbilden nach Binär. 46:50.370 --> 46:53.170 Oder anders gesagt, Sie können den Homomorphismus nehmen, der aus 46:53.170 --> 46:55.290 jeder Hexadezimal Ziffer 4 Bits macht. 46:56.590 --> 46:59.070 222 B. 47:00.150 --> 47:02.370 Dann haben Sie hier 12 Bits. 47:03.350 --> 47:04.070 Nein, Quatsch. 47:04.570 --> 47:05.050 16. 47:05.970 --> 47:07.950 Wer zählen kann, ist klein Vorteil. 47:08.670 --> 47:09.410 16 Bits. 47:09.770 --> 47:12.910 Und hier bei den drei Bytes, was hinten noch frei ist, das sind auch 47:12.910 --> 47:16.770 genau 16 kleine X, wo man diese 16 Bits jetzt reinkleben muss. 47:17.630 --> 47:21.350 Und da schreiben Sie die einfach hintereinander hin und teilen sie 47:21.350 --> 47:24.850 dann so auf, teilen vorne 4 Bits ab und dann 6 und dann 6. 47:25.110 --> 47:28.350 Also 4 Bits und 6 Bits und 6 Bits, sagen das so. 47:28.830 --> 47:32.990 Und die ersten 4 Bits kleben Sie hinter das 11110 und die nächsten 6 47:32.990 --> 47:35.850 hinter das 10 und die letzten 6 hinter das andere 10. 47:36.590 --> 47:41.690 Und dann haben Sie hier drei Folgen von jeweils 8 Bits und das ist die 47:41.690 --> 47:44.010 UTF -8-Codierung des Integralzeichens. 47:47.510 --> 47:48.890 So funktioniert das. 47:49.770 --> 47:53.490 Und wenn Sie jetzt so was haben und müssen zurück zum Original, ist 47:53.490 --> 47:54.190 kein Problem. 47:54.710 --> 47:58.470 Sie sehen das erste Byte, Sie sehen da stehen drei Einsen, dann wissen 47:58.470 --> 48:00.690 Sie, ah, ich muss drei von den Dingern nehmen. 48:01.670 --> 48:05.990 Dann machen Sie hier vorne das 1110 weg und bei dem nächsten das 10 48:05.990 --> 48:06.770 und das 10. 48:07.350 --> 48:11.810 Übrig bleiben 16 Bits, schieben die zusammen und dann haben Sie die 48:11.810 --> 48:14.110 Binärdarstellung der Nummer des Unicode-Zeichens. 48:14.550 --> 48:16.630 Und dann können Sie in Ihrem Font nachgucken, was das ist. 48:19.770 --> 48:21.530 So, das ist UTF-8. 48:23.150 --> 48:25.950 Beispiel eines präfixfreien Homomorphismus. 48:37.540 --> 48:42.500 Und da übersetzt man, ja, von Unicode-Zeichen nach Nullen und Einsen 48:42.500 --> 48:43.020 und zurück. 48:50.090 --> 48:54.050 Also, die Frage war nochmal, warum steht hier vorne immer 1 0? 48:55.930 --> 49:02.490 Also, immer dieses Anfangsstück ein paar Einsen und dann eine 0 von 49:02.490 --> 49:05.710 dem ersten Byte, das sagt einem, wie viele Bytes muss ich insgesamt 49:05.710 --> 49:06.150 angucken? 49:07.910 --> 49:15.230 Und zweitens und daran erkenne ich also immer die ersten und die 49:15.230 --> 49:20.570 dahinter haben immer 1 0 und wenn jetzt zum Beispiel mal irgendwas 49:20.570 --> 49:27.890 kaputt geht, dann ist das hier auch noch so also meinetwegen hier das 49:27.890 --> 49:31.970 erste ist 1 1 1 0 und das nächste fängt aber mit 1 1 an. 49:32.530 --> 49:36.370 Dann merkt man auch, es ist irgendwas verkehrt und dann kann man 49:36.370 --> 49:38.670 sagen, okay, jetzt schmeiße ich mal nur so ein bisschen weg und dann 49:38.670 --> 49:40.410 tue ich mal so, als wäre der Rest wieder in Ordnung. 49:40.810 --> 49:43.030 Aber man sieht immer klar, wo ist man? 49:43.090 --> 49:45.850 Ist man bei dem ersten Byte oder bei einem weiter dahinter? 49:48.050 --> 49:50.770 Weil die sich auch so schön in der Anzahl Einsen unterscheiden. 49:51.490 --> 49:54.250 Beziehungsweise, wie gesagt, also die Bytes, die mit einer 0 vorne 49:54.250 --> 49:56.130 anfangen, das sind die, da muss ich nur 1 nehmen. 49:57.870 --> 49:58.270 Gut. 50:02.630 --> 50:06.090 Also, und Homomorphismen sind also wirklich was völlig Natürliches. 50:06.170 --> 50:09.330 Einfach jedes Zeichen ersetzen durch ein Wort, irgendwie abbilden in 50:09.330 --> 50:11.150 einem anderen Bereich, dann kommt man auch wieder zurück. 50:11.970 --> 50:15.070 Da muss man irgendwann gar nicht mehr groß drüber reden, das macht man 50:15.070 --> 50:16.250 sozusagen automatisch. 50:17.050 --> 50:17.190 So. 50:20.710 --> 50:24.410 Und damit kommen wir zu Huffman-Codierung. 50:28.310 --> 50:30.550 Und das heißt also zum Beispiel 50:35.230 --> 50:40.490 zu etwas, was jedenfalls Bestandteil ist von manchen 50:40.490 --> 50:41.930 Kompressionsverfahren. 50:42.670 --> 50:44.830 Wirklich, um Dateien kleiner zu machen. 50:45.990 --> 50:49.130 Also aus vielen Bits wenige Bits zu machen, so dass man wieder 50:49.130 --> 50:49.810 zurückkommt. 50:51.490 --> 50:56.170 Nochmal, es kann nicht sein, dass Sie aus allen langen Wörtern immer 50:56.170 --> 50:59.870 echt kürzere Wörter machen, über dem gleichen Alphabet, ohne 51:00.470 --> 51:00.970 Informationsverlust. 51:01.070 --> 51:01.890 Das kann nicht klappen. 51:02.450 --> 51:04.990 Also es gibt manchmal so Scherzkekse, ich weiß nicht, ob es sie immer 51:04.990 --> 51:08.770 noch gibt, die verkaufen einem so Programme und sagen, das kann alle 51:08.770 --> 51:10.830 Dateien komprimieren. 51:11.110 --> 51:11.410 Alle. 51:12.210 --> 51:13.330 Echt kleiner machen. 51:14.230 --> 51:15.630 Das ist gelogen, ja. 51:16.230 --> 51:17.510 Aus mathematischen Gründen. 51:17.650 --> 51:18.810 Es ist unmöglich. 51:19.170 --> 51:21.210 Man kann nicht alles verlustfrei komprimieren. 51:22.430 --> 51:23.550 Aber manches. 51:24.570 --> 51:25.610 Und das reicht einem ja. 51:26.010 --> 51:28.790 Man will ja nicht alles Mögliche komprimieren, man will ja nur zum 51:28.790 --> 51:30.870 Beispiel deutsche Texte komprimieren oder so etwas. 51:31.610 --> 51:37.410 So, und bei Huffman-Kodierung ist es so, da hat man ein konkretes 51:37.410 --> 51:41.270 Wort, also das kann lang sein, stellen Sie sich vor, eine Textdatei, 51:41.390 --> 51:45.650 die Sie angefertigt haben oder was auch immer, ein Wort W über 51:45.650 --> 51:56.270 irgendeinem Alphabet A und dann konkret zu diesem Wort konstruiert man 51:56.270 --> 52:02.210 einen Homomorphismus, so dass dieser Homomorphismus jedenfalls für 52:02.210 --> 52:08.330 dieses eine Wort etwas Gutes tut, salopp gesprochen. 52:08.930 --> 52:12.470 Also man macht einen Homomorphismus, der ist insbesondere Epsilon 52:12.470 --> 52:15.370 -frei, also es wird nichts gelöscht, Sie kommen auch wirklich wieder 52:15.370 --> 52:19.690 zurück zum Original und diesen Homomorphismus wendet man dann halt 52:19.690 --> 52:24.110 auch auf das Wort an, um das es geht, für das Ding konstruiert worden 52:24.110 --> 52:24.410 ist. 52:25.830 --> 52:32.910 Und die Idee ist, in dem Wort, das man da gegeben hat, man guckt, dass 52:32.910 --> 52:38.450 man die Symbole, die oft vorkommen, durch kurze Wörter repräsentiert 52:38.450 --> 52:42.790 und die Symbole, die selten vorkommen, durch längere Wörter und das 52:42.790 --> 52:48.190 wird so gemacht, dass das Ganze Präfix-frei ist und noch mit einem 52:48.190 --> 52:51.410 kleinen Trick, den wir ganz am Ende angucken, führt es dann 52:51.410 --> 52:54.930 tatsächlich dazu, dass sogar der Homomorphismus aus einem langen Wort 52:54.930 --> 52:59.250 ein kurzes Wort machen kann, obwohl man das Alphabet nicht größer 52:59.250 --> 52:59.490 macht. 52:59.990 --> 53:02.410 Also das Zielalphabet ist immer nur 0,1. 53:05.270 --> 53:07.650 Kleiner geht's nicht sinnvoll. 53:08.790 --> 53:10.010 Das ist der Plan. 53:11.610 --> 53:12.750 Wie geht das? 53:13.130 --> 53:16.670 Da sind wir jetzt, weiß ich nicht, wie weit Sie im Programmieren so 53:16.670 --> 53:19.710 sind, aber jetzt hier zum ersten Mal bei einem etwas größeren 53:19.710 --> 53:24.070 Algorithmus, jetzt nicht im Sinne von, ich schreibe Ihnen ein Java 53:24.070 --> 53:29.210 -Programm hin, das Huffman-Codierung für ein Wort ausrechnet. 53:30.110 --> 53:32.550 Das wäre unangenehm, viel zu schreiben. 53:32.710 --> 53:34.570 Also Sie werden sehen, wir haben das auf einem höheren Niveau, aber 53:34.570 --> 53:38.650 achten Sie darauf, auch hier hoffentlich, ich beschreibe alles ganz 53:38.650 --> 53:42.930 präzise und Sie können es dann auch in der Hausaufgabe genauso gut 53:42.930 --> 53:44.410 nachmachen an einem anderen Beispiel. 53:45.730 --> 53:52.330 Also, wir haben irgendein Alphabet A und wir haben irgendein Wort W 53:52.330 --> 53:53.990 aus A-Stern. 53:56.190 --> 54:00.470 Und das Erste, was man tut, ist, man zählt, wie oft kommt jedes Symbol 54:00.470 --> 54:02.810 vor in diesem Wort. 54:03.930 --> 54:10.610 Und für jedes Symbol X bezeichnen wir mal mit Nx von W die Anzahl der 54:10.610 --> 54:13.470 Stellen, wo das Symbol X in dem Wort W vorkommt. 54:16.350 --> 54:22.290 Und der Einfachheit halber, wir gehen mal davon aus, für Symbole, die 54:22.290 --> 54:25.290 nicht vorkommen in dem Wort, muss man sich nichts überlegen. 54:25.470 --> 54:28.810 Also stellen wir uns einfach auf den Standpunkt, alle Symbole aus A 54:28.810 --> 54:29.710 kommen vor. 54:30.330 --> 54:32.710 Also alle Nx von W sind echt größer Null. 54:34.230 --> 54:37.990 Und was man dann macht ist, als erstes man konstruiert etwas, was 54:37.990 --> 54:39.630 Informatiker einen Baum nennen. 54:40.550 --> 54:44.730 Da ist häufig die Wurzel oben und die Blätter sind unten, wenn man es 54:44.730 --> 54:45.190 hinmalt. 54:47.410 --> 54:50.630 Und es gibt sowas wie Zweige. 54:53.190 --> 54:57.350 Die bestehen aus Kanten und dann werden die noch irgendwie verziert 54:57.350 --> 54:58.510 mit Nullen und Einsen. 54:58.630 --> 55:01.290 Und dann kann man aus diesem Gebilde ablesen, was ist die Codierung 55:01.290 --> 55:04.370 jedes einzelnen Symbols, was in dem Wort vorkommt. 55:05.030 --> 55:07.710 Und dann hat man sein Homomorphismus. 55:10.970 --> 55:11.390 Beispiel. 55:12.030 --> 55:15.530 Hier oben ist ein Wort hingeschrieben, da kommen die Symbole A, B, C, 55:15.690 --> 55:16.590 D, E und F vor. 55:17.770 --> 55:18.490 Unterschiedlich oft. 55:19.570 --> 55:23.290 Und was am Ende rauskommen wird, ist dieses Gebilde hier, also sowas 55:23.290 --> 55:25.070 nennt man dann einen Baum. 55:25.190 --> 55:27.270 Da oben die Spitze, das heißt Wurzel. 55:27.890 --> 55:31.230 Da unten die Stellen, wo irgendwas steht und wo es nach unten nicht 55:31.230 --> 55:33.070 mehr weitergeht, die Dinger heißen Blätter. 55:33.070 --> 55:39.110 Und diese geraden Striche, die irgendwie zwei Knoten, sagt man, auf 55:39.110 --> 55:41.430 unterschiedlichen Ebenen verbinden, die nennt man Kanten. 55:42.170 --> 55:45.490 Das werden wir allgemeiner in dem Kapitel über gerichtete und 55:45.490 --> 55:47.870 ungerichtete Graphen uns noch mehr angucken. 55:48.770 --> 55:50.830 Also das ist das Gebilde, das am Ende rauskommt. 55:52.390 --> 55:56.590 Und da sieht man an den Blättern, da stehen unter anderem die Symbole 55:56.590 --> 55:59.110 A, B, C, D, E und F. 56:00.610 --> 56:04.510 Und an den Kanten stehen Nullen und Einsen und dann stehen da noch 56:04.510 --> 56:05.970 irgendwelche anderen Zahlen. 56:06.650 --> 56:08.310 Bei den Blättern sind das einfach die Häufigkeiten. 56:09.070 --> 56:13.710 Also wenn da 2, B steht, heißt das in dem Ausgangswort hier, taucht 56:13.710 --> 56:14.890 zweimal ein B auf. 56:15.010 --> 56:18.530 Einmal da vorne das vierte und da hinten das viertletzte. 56:19.930 --> 56:24.290 Und wenn man das hat, dann kann man da ablesen für jedes A, B, C, D, E 56:24.290 --> 56:25.850 und F, was ist die Kodierung. 56:25.850 --> 56:31.990 Und da sehen Sie, also wie das geht, sehen wir gleich, aber E und F 56:33.470 --> 56:36.930 werden durch Wörter der Länge 2 kodiert, 0, 1 und 1, 1. 56:38.750 --> 56:41.790 Und tatsächlich E und F sind die Buchstaben, die hier am häufigsten 56:41.790 --> 56:42.670 vorkommen in dem Wort. 56:44.070 --> 56:48.870 Und die anderen in diesem Beispiel durch Wörter der Länge 3. 56:49.570 --> 56:54.110 Im Allgemeinen, die können stark unterschiedlich lang sein, diese 56:54.110 --> 56:54.750 Kodwörter. 56:54.990 --> 56:57.450 Da können auch viele verschiedene Längen auftreten. 57:00.530 --> 57:04.870 Hier halt nur 2 und 3, aber das kann auch von 1 bis 10 gehen oder wie 57:04.870 --> 57:05.190 auch immer. 57:05.310 --> 57:08.390 Kommt drauf an, wie viele verschiedene Symbole man hat und wie 57:08.390 --> 57:10.190 unterschiedlich die Häufigkeiten sind. 57:12.070 --> 57:12.170 So. 57:14.890 --> 57:17.010 Wie konstruiert man diesen Huffmanbaum? 57:21.250 --> 57:23.190 Man fängt an so. 57:25.130 --> 57:27.990 Also man baut den Baum von unten nach oben sozusagen. 57:28.290 --> 57:32.050 Er wächst jetzt von den Blättern zur Wurzel sozusagen. 57:32.210 --> 57:35.010 Also wir konstruieren ihn von den Blättern zur Wurzel. 57:35.770 --> 57:37.390 Und was schreiben wir als Blätter hin? 57:39.430 --> 57:41.930 Die Symbole, die in dem Wort vorkommen. 57:42.090 --> 57:44.450 Also hier A, B, C, D, E und F. 57:44.930 --> 57:48.290 Und zu jedem Symbol schreiben wir dazu, wie oft kommt es im 57:48.290 --> 57:49.390 Ausgangswort vor. 57:49.950 --> 57:54.790 Also 2 A´s, 2 B´s, 3 C´s, 3 D´s, 5 E´s und 7 F´s. 57:55.150 --> 57:56.270 So ist das bei dem Wort. 57:57.590 --> 58:02.710 Dass ich die jetzt genau so hingemalt habe auf der Folie liegt daran, 58:02.850 --> 58:04.570 dass hinterher das Bild vernünftig aussieht. 58:04.650 --> 58:08.290 Das weiß man im Allgemeinen ohne Übung nicht so richtig. 58:08.430 --> 58:11.190 Dann schreibt man die halt in irgendeiner Reihenfolge nebeneinander 58:11.190 --> 58:12.350 und muss dann halt mal gucken. 58:13.230 --> 58:16.490 Und wenn hinterher das Bild etwas komisch wird, dann malt man es halt 58:16.490 --> 58:18.950 nochmal und sortiert die Blätter ein bisschen anders. 58:20.050 --> 58:20.650 Gut. 58:22.330 --> 58:27.330 Also man schreibt sich die Symbole hin mit ihren Häufigkeiten und 58:27.330 --> 58:31.770 solange es noch mindestens 2 und nennen wir diese Dinger schon mal 58:31.770 --> 58:32.430 Knoten. 58:33.150 --> 58:35.070 Blätter sind insbesondere Knoten. 58:35.570 --> 58:39.770 Und solange es noch mindestens 2 Knoten gibt, von denen keine Kanten 58:39.770 --> 58:44.150 nach oben gehen, hier haben wir noch 6 davon, macht man immer wieder 58:44.150 --> 58:45.530 das gleiche. 58:46.910 --> 58:49.750 Also hier stehen ja bei jedem Knoten eine Häufigkeit. 58:50.230 --> 58:53.650 Dann weiter oben werden auch Zahlen stehen, das sind auch immer 58:53.650 --> 58:54.190 Häufigkeiten. 58:54.450 --> 58:55.650 Also Häufigkeiten haben wir immer. 58:56.890 --> 59:00.650 Und was man dann immer macht, von allen Knoten, wo noch keine Kanten 59:00.650 --> 59:03.370 nach oben gehen, da stehen überall Häufigkeiten. 59:04.070 --> 59:08.290 Und dann sucht man sich 2 Knoten mit möglichst kleinen Häufigkeiten. 59:11.090 --> 59:14.690 Unter denen, wo es noch nach oben weitergehen kann, wo noch was fehlt. 59:15.430 --> 59:19.270 Also hier haben wir jetzt 2, 2, 3, 3, 5 und 7 als Häufigkeiten. 59:19.950 --> 59:24.230 Wenn Sie da 2 suchen, die möglichst klein sind, finden Sie die 2 und 59:24.230 --> 59:24.710 die 2. 59:25.610 --> 59:26.890 Ja, das sind die beiden kleinsten. 59:28.610 --> 59:32.370 Und dann nimmt man diese beiden Knoten, wo möglichst kleine 59:32.370 --> 59:33.290 Häufigkeiten sind. 59:33.830 --> 59:36.570 In dem Beispiel ist das hier eindeutig. 59:36.730 --> 59:38.090 Das ist halt ein erstes Beispiel. 59:38.230 --> 59:39.450 Das soll alles einfach sein. 59:39.550 --> 59:43.450 Im Allgemeinen könnte natürlich sein, dass Sie 3 mit Häufigkeit 2 59:43.450 --> 59:43.630 haben. 59:43.690 --> 59:44.730 Dann können Sie sich 2 aussuchen. 59:46.410 --> 59:50.870 Aber hier, also A und B, das sind die Knoten da mit den kleinsten 59:50.870 --> 59:51.510 Häufigkeiten. 59:52.050 --> 59:54.350 Und dann fasst man die sozusagen zusammen. 59:56.470 --> 59:59.770 Und sagt, okay, also 2 plus 2 ist 4. 01:00:00.330 --> 01:00:03.590 Dann male ich jetzt da oben drüber einen Knoten und schreibe da die 01:00:03.590 --> 01:00:05.110 Summe der Häufigkeiten hin. 01:00:05.390 --> 01:00:09.650 Also hier 4 und male Kanten von der 4 zu dem einen und von der 4 zu 01:00:09.650 --> 01:00:12.610 dem anderen Knoten, dessen Häufigkeiten ich da addiert habe. 01:00:14.350 --> 01:00:17.990 Und damit sind die beiden Knoten mit Häufigkeiten 2, so für A und B 01:00:17.990 --> 01:00:18.710 erledigt. 01:00:19.290 --> 01:00:23.790 Dann haben wir hier 9 Knoten 4 und da haben wir noch 2 mit 3 und 5 und 01:00:23.790 --> 01:00:24.090 7. 01:00:26.090 --> 01:00:30.650 Und jetzt gibt es immer noch mindestens 2, nämlich sogar 5 Knoten, wo 01:00:30.650 --> 01:00:33.090 es nach oben nicht weiter geht, wo Kanten fehlen. 01:00:33.690 --> 01:00:34.950 Und dann macht man das gleiche wieder. 01:00:35.130 --> 01:00:38.630 Unter allen diesen Knoten sucht man sich 2 mit möglichst kleinen 01:00:38.630 --> 01:00:39.410 Häufigkeiten. 01:00:40.290 --> 01:00:43.170 Also hier haben wir jetzt 4, 5, 3, 3 und 7. 01:00:44.030 --> 01:00:47.110 Die 2 mit den möglichst kleinen Häufigkeiten sind die beiden Dreier. 01:00:48.750 --> 01:00:51.550 Und dann machen wir als nächstes das gleiche, was wir eben gemacht 01:00:51.550 --> 01:00:52.110 haben, mit denen. 01:00:52.310 --> 01:00:57.550 Also sozusagen wir nehmen diese beiden Dreier und addieren die zu 01:00:57.550 --> 01:01:02.370 einer 6 mal den Knoten mit der 6 oben drüber und 2 Kanten zu den 01:01:02.370 --> 01:01:05.330 Knoten, deren Häufigkeiten wir addiert haben. 01:01:06.070 --> 01:01:09.450 Damit sind diese beiden Blätter für C und D mit den Häufigkeiten 3 01:01:09.450 --> 01:01:10.230 auch erledigt. 01:01:11.970 --> 01:01:17.710 Und da man immer aus 2 Knoten einen macht, es wird immer ein Knoten 01:01:17.710 --> 01:01:20.730 weniger, wo es noch nicht nach oben geht. 01:01:21.510 --> 01:01:23.650 Deswegen irgendwann wird man auch fertig sein. 01:01:23.910 --> 01:01:26.030 Es werden immer weniger Knoten, für die man was tun muss. 01:01:26.910 --> 01:01:30.030 Also jetzt haben wir hier noch 4 Knoten, wo es nach oben nicht weiter 01:01:30.030 --> 01:01:30.270 geht. 01:01:30.370 --> 01:01:33.010 Die haben die Häufigkeiten 4, 5, 6 und 7 steht da. 01:01:34.070 --> 01:01:35.430 Und jetzt wieder das gleiche. 01:01:35.470 --> 01:01:38.350 Sie suchen sich 2 von diesen Knoten mit möglichst kleinen 01:01:38.350 --> 01:01:39.190 Häufigkeiten. 01:01:39.750 --> 01:01:41.130 Na ja, 4, 5, 6 und 7. 01:01:41.210 --> 01:01:43.070 Die beiden kleinsten sind 4 und 5. 01:01:44.050 --> 01:01:45.730 Und da fassen Sie diese beiden zusammen. 01:01:45.870 --> 01:01:47.950 Malen einen Knoten oben drüber mit der Summe. 01:01:48.090 --> 01:01:51.370 Also 4 plus 5 gibt 9 und Kanten zu 4 und zu 5. 01:01:52.450 --> 01:01:55.710 Damit sind diese beiden Knoten erledigt und es sind noch 3 übrig mit 01:01:55.710 --> 01:01:57.570 den Häufigkeiten 9, 6 und 7. 01:01:58.830 --> 01:02:01.850 Wieder, Sie suchen sich 2 von diesen Knoten mit möglichst kleinen 01:02:01.850 --> 01:02:02.550 Häufigkeiten. 01:02:02.690 --> 01:02:03.850 Das sind die 6 und die 7. 01:02:04.490 --> 01:02:07.930 Addiert gibt 13 ein neuer Knoten oben drüber. 01:02:09.270 --> 01:02:10.570 Das sind 6 und 7 erledigt. 01:02:10.670 --> 01:02:11.930 Haben wir noch 9 und 13. 01:02:12.990 --> 01:02:15.810 Da suchen sich wieder 2 mit möglichst kleinen Häufigkeiten. 01:02:15.950 --> 01:02:18.470 Ja, das ist das letzte Mal, dass man überhaupt noch 2 hat. 01:02:18.910 --> 01:02:21.110 Das sind dann auch natürlich die 2 kleinsten. 01:02:21.710 --> 01:02:23.310 9 und 13 gibt 22. 01:02:24.130 --> 01:02:27.050 Malen Sie das oben drüber mit Kanten zu 9 und zu 13. 01:02:28.970 --> 01:02:31.270 Und jetzt hat man nur noch einen oben. 01:02:31.630 --> 01:02:33.950 Jetzt kann man nichts mehr zusammenfassen, jetzt ist man fertig. 01:02:34.870 --> 01:02:37.410 Und dieses Ding da oben heißt dann auch die Wurzel von dem Baum. 01:02:37.710 --> 01:02:38.870 Das ist jetzt hier nicht so wichtig. 01:02:39.670 --> 01:02:40.790 Also das heißt so. 01:02:41.890 --> 01:02:43.310 Hat man hier so ein Gebilde. 01:02:44.790 --> 01:02:49.630 Also immer suchen Sie sich 2 Knoten mit möglichst kleinen 01:02:49.630 --> 01:02:50.550 Häufigkeiten. 01:02:51.910 --> 01:02:55.190 Addieren die Häufigkeiten, malen Knoten oben drüber mit Kanten zu den 01:02:55.190 --> 01:02:57.370 beiden Knoten, die Sie jetzt da zusammenfassen. 01:02:59.550 --> 01:02:59.710 So. 01:03:02.190 --> 01:03:06.690 Und dann malt man noch an diese ganzen Kanten immer Nullen und Einsen. 01:03:06.830 --> 01:03:11.590 Zum Beispiel so alle Kanten, die nach links führen, schreiben Sie eine 01:03:11.590 --> 01:03:15.070 Null dran und an alle Kanten, die nach rechts führen, malen Sie eine 01:03:15.070 --> 01:03:15.690 Eins dran. 01:03:17.330 --> 01:03:19.250 Und dann haben wir diesen Huffman Baum. 01:03:23.940 --> 01:03:28.500 Und jetzt kann man auch ganz einfach ablesen, was ist die Kodierung 01:03:28.500 --> 01:03:30.140 eines einzelnen Symbols. 01:03:31.140 --> 01:03:33.660 Wenn Sie zum Beispiel wissen wollen, was ist die Kodierung von dem 01:03:33.660 --> 01:03:37.720 kleinen c, dann müssen Sie einfach den Weg gucken, den kürzesten, 01:03:37.860 --> 01:03:40.520 immer nach unten, von der Wurzel zum c. 01:03:40.520 --> 01:03:43.860 Also wenn Sie zum c wollen von der Wurzel aus, dann müssen Sie einmal 01:03:43.860 --> 01:03:45.480 nach rechts und zweimal nach links gehen. 01:03:46.240 --> 01:03:49.640 Und dann steht an den Kanten erst eine Eins und dann eine Null und 01:03:49.640 --> 01:03:50.200 dann eine Null. 01:03:51.340 --> 01:03:55.300 Und deswegen die Huffman-Kodierung von dem kleinen c ist 1 0 0. 01:03:55.440 --> 01:03:59.460 Von oben nach unten 1 0 0, die Symbole drei nachhin geschrieben. 01:04:01.420 --> 01:04:05.780 Und das können Sie mit allen machen, was Kodierung von einem a, von 01:04:05.780 --> 01:04:09.320 der Wurzel zum a, immer nach links 0 0 0. 01:04:10.180 --> 01:04:13.620 Kodierung von dem b 0 0 1. 01:04:14.640 --> 01:04:22.180 Kodierung von dem c hatten wir gerade d 1 0 1, e 0 1, f 1 1. 01:04:23.440 --> 01:04:25.560 So kriegen Sie die Kodierung von jedem Symbol. 01:04:25.740 --> 01:04:28.860 Sie gehen von der Wurzel auf dem kürzesten Weg immer nach unten bis zu 01:04:28.860 --> 01:04:33.160 dem Blatt, wo das Symbol steht, dessen Kodierung Sie bestimmen wollen. 01:04:33.640 --> 01:04:36.740 Und die Kantenbeschriftungen von links nach rechts hingeschrieben ist 01:04:36.740 --> 01:04:37.380 die Kodierung. 01:04:38.780 --> 01:04:43.300 So, auf diese Art und Weise kriegt man für jedes Symbol ein Kodwort 01:04:43.300 --> 01:04:44.720 aus Nullen und Einsen. 01:04:46.720 --> 01:04:50.240 Und wenn für jedes Symbol ein Kodwort festgelegt ist, dann, wenn es 01:04:50.240 --> 01:04:53.200 ein Homomorphismus ist für jedes längere Wort, naja, einfach jedes 01:04:53.200 --> 01:04:54.380 Symbol einzeln kodieren. 01:04:54.540 --> 01:04:56.540 Ja, ist der ganze Homomorphismus festgelegt. 01:04:57.780 --> 01:05:03.380 Und der Homomorphismus, der hier herausgekommen ist, ist präfixfrei. 01:05:05.000 --> 01:05:08.700 Kein Kodwort ist Anfangsstück eines längeren Kodwortes. 01:05:12.400 --> 01:05:13.420 Warum ist das so? 01:05:14.740 --> 01:05:18.180 Na, versuchen Sie sich mal vorzustellen, wie das sein müsste, damit 01:05:18.180 --> 01:05:21.720 ein Kodwort Präfix eines anderen Kodwortes ist. 01:05:22.460 --> 01:05:25.340 Da hätten Sie also so ein kürzeres Kodwort, das ist Präfix von einem 01:05:25.340 --> 01:05:25.760 längeren. 01:05:26.200 --> 01:05:28.360 Das kürzere Kodwort, wie kriegen Sie das? 01:05:28.700 --> 01:05:31.740 Sie gehen von der Wurzel zu dem Symbol. 01:05:32.380 --> 01:05:34.900 Und das, was Sie da aufsammeln an Nullen und Einsen, das ist die 01:05:34.900 --> 01:05:36.000 Kodierung von dem Symbol. 01:05:37.640 --> 01:05:43.080 Wenn das jetzt Präfix von einem anderen Kodwort sein sollte, dann 01:05:43.080 --> 01:05:46.320 müssten Sie ja diesen gleichen Weg gehen und dann noch weiter zu dem 01:05:46.320 --> 01:05:50.480 Symbol weiter nach unten, um die längere Kodierung des anderen Symbols 01:05:50.480 --> 01:05:50.980 zu kriegen. 01:05:53.680 --> 01:05:59.860 Das heißt, Sie würden das Präfix gehen und zu einem Symbol kommen, für 01:05:59.860 --> 01:06:03.960 das Sie eine Kodierung haben und von da aus noch weiter nach unten zu 01:06:03.960 --> 01:06:04.880 einem anderen Symbol. 01:06:06.100 --> 01:06:10.680 Also von einem Knoten, der für ein Symbol aus dem ursprünglichen Wort 01:06:10.680 --> 01:06:12.960 steht, nach unten zu einem anderen Symbol. 01:06:13.780 --> 01:06:18.600 Und das haben wir nie, denn wir bauen ja, die Symbole sind ganz unten, 01:06:18.720 --> 01:06:20.080 von da geht es nur nach oben. 01:06:20.180 --> 01:06:23.960 Wir kommen nie von Symbolen nach unten zu anderen Symbolen. 01:06:24.380 --> 01:06:26.680 Und deswegen muss das präfixfrei sein. 01:06:28.060 --> 01:06:32.920 Und wenn Sie sich das angucken, das ist so, also 01 taucht hier nie 01:06:32.920 --> 01:06:37.200 als Anfangsstück auf, 11 auch nicht, präfixfrei. 01:06:39.520 --> 01:06:43.900 Und da, wo die Kodwörter gleich lang sind, sie sind paarweise 01:06:43.900 --> 01:06:44.800 verschieden. 01:06:44.840 --> 01:06:46.100 Das muss man natürlich auch noch testen. 01:06:47.200 --> 01:06:51.200 Das sind vier verschiedene Kodwörter, die der Länge 3 und die 2 der 01:06:51.200 --> 01:06:53.100 Länge 2 sind auch verschieden. 01:06:53.900 --> 01:06:58.800 Das Ding ist präfixfrei und deswegen ist es total simpel zu dekodieren 01:06:58.800 --> 01:06:59.520 hinterher wieder. 01:06:59.860 --> 01:07:03.300 Wenn Sie ein Kodwort haben, Sie gehen einfach von links drüber, Sie 01:07:03.300 --> 01:07:06.360 müssen wieder nur einmal von links nach rechts drüber gehen, immer 01:07:06.360 --> 01:07:09.980 gucken, wo ist das nächste Kodwort, dekodieren, wo ist das nächste 01:07:09.980 --> 01:07:12.520 Kodwort, dekodieren, wo ist das nächste Kodwort, dekodieren. 01:07:13.760 --> 01:07:17.360 Sie müssen nur einmal durchgehend die Datei lesen, sozusagen, wenn es 01:07:17.360 --> 01:07:19.680 eine Textdatei ist, beim Dekomprimieren. 01:07:20.800 --> 01:07:23.400 Das ist dann noch ein bisschen komplizierter als Huffman-Kodierung, 01:07:23.500 --> 01:07:24.920 aber im Prinzip sowas. 01:07:25.700 --> 01:07:27.040 Ganz einfach. 01:07:29.980 --> 01:07:30.260 Gut. 01:07:34.160 --> 01:07:42.080 Allerdings, wenn Sie sich das so angucken, also offensichtlich jedes 01:07:42.080 --> 01:07:46.100 einzelne Symbol wird ersetzt durch ein Kodwort, das länger ist. 01:07:48.980 --> 01:07:50.580 Wie man deutlich sieht. 01:07:50.780 --> 01:07:53.180 Die ursprünglichen Symbole haben Länge 1. 01:07:54.260 --> 01:07:56.520 Und die Kodwörter haben Länge 2 oder 3. 01:07:57.620 --> 01:08:00.680 Wenn Sie dieses Wort hier oben, das habe ich mir jetzt erspart, 01:08:01.520 --> 01:08:04.820 abbilden, mit dem Homomorphismus kodieren, dann wird es halt viel 01:08:04.820 --> 01:08:05.040 länger. 01:08:05.200 --> 01:08:06.300 Zwei - bis dreimal so lang. 01:08:06.380 --> 01:08:10.180 Sie müssen dann für jedes A 000 hinschreiben, für jedes B 001. 01:08:11.780 --> 01:08:14.840 Dann kommt halt eine lange Kette von 0 und 1 raus. 01:08:17.180 --> 01:08:17.620 Banal. 01:08:17.800 --> 01:08:20.340 Aber offensichtlich wird das Ding länger. 01:08:22.940 --> 01:08:24.060 Und nicht kürzer. 01:08:24.180 --> 01:08:26.140 Ich habe aber gesagt, Huffman-Kodierung benutzt man in 01:08:26.140 --> 01:08:27.200 Kompressionsverfahren. 01:08:28.160 --> 01:08:29.760 Also da gibt es noch irgendwo einen kleinen Trick. 01:08:31.460 --> 01:08:33.020 Den gucken wir uns jetzt noch an. 01:08:38.720 --> 01:08:41.180 Und vorher noch ein paar allgemeine Bemerkungen. 01:08:41.320 --> 01:08:45.720 Zum Ersten, ich habe es gerade bei dem Beispiel schon gesagt, das war 01:08:45.720 --> 01:08:48.820 so konstruiert, immer die beiden Knoten mit den kleinsten 01:08:48.820 --> 01:08:50.580 Häuflichkeiten, das war immer eindeutig. 01:08:51.660 --> 01:08:53.740 Im Allgemeinen ist das nicht so. 01:08:54.120 --> 01:08:56.600 Stellen Sie sich vor, am Anfang alle Symbole sind gleich häufig. 01:08:57.380 --> 01:08:58.820 Welche zwei nehmen Sie denn? 01:08:59.420 --> 01:09:00.080 Ist egal. 01:09:00.900 --> 01:09:03.020 Also Sie kriegen dann natürlich, je nachdem, was Sie nehmen, 01:09:03.360 --> 01:09:06.400 unterschiedliche Huffman-Bäume raus und unterschiedliche 01:09:06.400 --> 01:09:07.320 Homomorphismen. 01:09:08.120 --> 01:09:10.000 Aber die sind alle gleich gut. 01:09:10.000 --> 01:09:15.160 Und die Kodierung des Wortes wird immer gleich lang sein. 01:09:19.240 --> 01:09:23.440 Außerdem habe ich immer so getan, als wäre es ganz natürlich von zwei 01:09:23.440 --> 01:09:26.040 Knoten, welchen male ich links hin, welchen male ich rechts hin. 01:09:26.120 --> 01:09:30.480 Schreibe ich jetzt das A mit Häufigkeit 2 links vom B mit Häufigkeit 2 01:09:30.480 --> 01:09:33.420 oder rechts davon, hätte ich ja auch anders machen können. 01:09:34.080 --> 01:09:39.080 Und dann hätte ich immer noch die beiden verschmolzen, aber dann wären 01:09:39.080 --> 01:09:41.760 die Beschriftungen an den Kanten genau andersrum gewesen, hätten Sie 01:09:41.760 --> 01:09:43.920 auch andere Kodierungen rausgekriegt. 01:09:44.940 --> 01:09:47.600 Formal auch anders, aber genauso gut. 01:09:47.640 --> 01:09:50.300 Die Kodierung des Gesamtwortes bleibt genauso lang. 01:09:51.520 --> 01:09:54.860 Und auch dieses, wir malen an die Kanten nach links eine 0 und wir 01:09:54.860 --> 01:09:58.000 malen an die Kanten nach rechts eine 1, ist eine willkürliche 01:09:58.000 --> 01:09:58.680 Festlegung. 01:09:58.980 --> 01:10:02.320 Solange Sie nur an jeder Stelle einmal eine 1 und einmal eine 0 01:10:02.320 --> 01:10:06.360 nehmen, immer, Sie kriegen sowas wie eine Huffman-Kodierung. 01:10:09.460 --> 01:10:13.000 Und egal, wie Sie es machen, alle Kodierungen, die rauskommen, sind 01:10:13.000 --> 01:10:16.980 gleich gut und die sind auch in einem gewissen Sinne bei dieser 01:10:16.980 --> 01:10:20.040 Konstruktion, der Homomorphismus, der rauskommt, ist so gut, besser 01:10:20.040 --> 01:10:20.940 geht nichts. 01:10:22.400 --> 01:10:25.520 Nämlich, also man kann beweisen, das ersparen wir uns hier, das ist 01:10:25.520 --> 01:10:26.260 ein bisschen Arbeit, 01:10:29.440 --> 01:10:36.340 wenn Sie ein Wort nehmen und Sie gucken jetzt alle präfixfreien 01:10:36.340 --> 01:10:38.860 Kodierungen an und was machen die aus diesem einem Wort? 01:10:38.980 --> 01:10:40.220 Alle, die es überhaupt gibt. 01:10:41.300 --> 01:10:45.460 Von dem Alphabet, für das wir uns interessieren, nach 0, 1 Stern. 01:10:49.120 --> 01:10:55.960 Unter allen präfixfreien Kodierungen, Sie werden keine finden, die für 01:10:55.960 --> 01:10:59.940 dieses eine Wort etwas Kürzeres liefert als die Huffman-Kodierung. 01:11:00.800 --> 01:11:04.020 Unter allen präfixfreien Kodierungen, Huffman-Kodierungen liefert 01:11:04.020 --> 01:11:05.460 Ihnen die kürzesten Kodwörter. 01:11:05.880 --> 01:11:09.140 Also für das eine Wort, für das die Kodierung konstruiert worden ist. 01:11:12.140 --> 01:11:14.240 Also in einem gewissen Sinne sind die optimal. 01:11:14.560 --> 01:11:17.900 Kürzer geht es nicht, wenn Sie präfixfrei bleiben wollen. 01:11:19.220 --> 01:11:22.020 Und Sie können sich vorstellen, vielleicht, also das zu beweisen, 01:11:22.200 --> 01:11:25.220 könnte ein bisschen Arbeit sein, denn irgendwie muss man argumentieren 01:11:25.220 --> 01:11:27.560 über alle präfixfreien Kodierungen. 01:11:28.680 --> 01:11:30.120 Das sind unendlich viele. 01:11:30.820 --> 01:11:34.020 Das klingt so, als wäre es vielleicht nicht so ganz einfach. 01:11:34.140 --> 01:11:35.840 Und ja, es ist ein bisschen Arbeit. 01:11:37.380 --> 01:11:37.600 Gut. 01:11:39.500 --> 01:11:42.280 Ja, und wie macht man das, damit dann die Kodierungen hinterher 01:11:42.280 --> 01:11:45.740 tatsächlich kürzer sind als die Originalwörter, obwohl das Alphabet 01:11:45.740 --> 01:11:47.120 womöglich viel kleiner ist? 01:11:48.340 --> 01:11:49.100 Nur 0, 1. 01:11:52.120 --> 01:11:53.200 Na, hier ist der Trick. 01:11:55.840 --> 01:11:58.720 Das kriegen Sie dann auch nochmal in der Übung gezeigt. 01:12:01.260 --> 01:12:06.260 Sie gucken nicht mehr, also wir abstrahieren jetzt sozusagen ein 01:12:06.260 --> 01:12:06.620 bisschen. 01:12:08.600 --> 01:12:11.220 Und wenn Sie so ein Wort haben, Sie gucken jetzt nicht mehr einzelne 01:12:11.220 --> 01:12:14.860 Symbole und zählen die Häufigkeiten für einzelne Symbole und machen 01:12:14.860 --> 01:12:19.060 Ihre Tabelle und konstruieren Ihren Baum, sondern Sie nehmen kleine 01:12:19.060 --> 01:12:25.080 Teilwörter, kleine Blöcke, sagen wir mal der Länge B, also 2 oder wie 01:12:25.080 --> 01:12:28.520 viel auch immer und dann zerhacken Sie das Wort in lauter Schnipsel 01:12:28.520 --> 01:12:32.400 der Länge 2 oder 3 oder wie viel auch immer, gleicher Länge. 01:12:33.680 --> 01:12:37.780 Wenn es am Ende nicht ganz aufgeht in der Praxis, man klebt halt noch 01:12:37.780 --> 01:12:39.220 ein bisschen was dran, damit es passt. 01:12:40.300 --> 01:12:43.780 Aber stellen wir uns vor, es passt mit der Länge und dann gucken Sie 01:12:43.780 --> 01:12:47.640 sich diese Blöcke der Länge 2 oder 3 an und zählen die Häufigkeiten 01:12:47.640 --> 01:12:48.020 davon. 01:12:48.200 --> 01:12:49.840 Wie oft kommt AAA vor? 01:12:49.960 --> 01:12:51.600 Wie oft kommt ABA vor? 01:12:51.880 --> 01:12:53.820 Wie oft kommt CBB vor? 01:12:54.760 --> 01:12:58.500 Und behandeln diese kleinen Blöcke jetzt so, als wären es einzelne 01:12:58.500 --> 01:13:00.880 Symbole und machen dafür Huffman-Codierung. 01:13:02.900 --> 01:13:08.140 Und wenn Ihr Wort schön ist, dann kann es tatsächlich passieren, dass 01:13:08.140 --> 01:13:13.540 die Codewörter für die Blöcke, weil gar nicht so viele... also 01:13:13.540 --> 01:13:17.040 prinzipiell gibt es natürlich potenziell da viel mehr so Blöcke der 01:13:17.040 --> 01:13:20.460 Länge 2 oder 3 als einzelne Symbole, aber vielleicht haben Sie Glück 01:13:20.460 --> 01:13:23.560 und von den Blöcken kommen gar nicht so viele vor, die denkbar sind in 01:13:23.560 --> 01:13:24.080 Ihrem Wort. 01:13:24.660 --> 01:13:27.340 Dann haben Sie noch relativ wenig Blöcke und wenn Sie dann Huffman 01:13:27.340 --> 01:13:30.920 -Codierung machen, dann sind tatsächlich die Codewörter für die Blöcke 01:13:30.920 --> 01:13:36.860 nie länger und manchmal kürzer als die Originalblöcke. 01:13:38.500 --> 01:13:41.540 Und wenn Sie dann das Ganze codieren und dann aus jedem Block, Sie 01:13:41.540 --> 01:13:43.880 machen ein Codewort, ja, nicht mehr aus einzelnen Symbolen, aus 01:13:43.880 --> 01:13:47.700 Blöcken, dann kann es tatsächlich sein, dass Ihr Codewort kürzer ist 01:13:47.700 --> 01:13:48.320 als das Original. 01:13:49.440 --> 01:13:52.460 Und das ist das, was in den Kompressionsverfahren unter anderem 01:13:53.240 --> 01:13:54.060 gemacht wird. 01:13:57.900 --> 01:13:58.360 So, Preisfrage. 01:14:01.840 --> 01:14:04.260 Also, so kann ich... 01:14:05.200 --> 01:14:05.860 Ach so. 01:14:07.600 --> 01:14:10.680 Warum kann man, wenn ich jetzt eine Textdatei nehme und ich 01:14:10.680 --> 01:14:13.820 komprimiere die, sagen wir mal mit Huffman-Codierung mit Block... Ach 01:14:13.820 --> 01:14:15.140 so, was heißt dann Block-Codierung? 01:14:16.020 --> 01:14:19.160 Man bildet dann nicht mehr einzelne Symbole nach B-Stern ab, sondern 01:14:19.160 --> 01:14:25.600 immer so Blöcke von B-Symbolen und fasst das Originalwort auf als 01:14:25.600 --> 01:14:26.420 Folge von Blöcken. 01:14:28.260 --> 01:14:32.400 Nehme ich eine Textdatei, mache ich das, kriege ich was, was kürzer 01:14:32.400 --> 01:14:32.680 ist? 01:14:34.540 --> 01:14:36.360 Ja, jetzt könnte ich das Gleiche doch wieder machen. 01:14:38.540 --> 01:14:40.280 Dann würde ich ja noch kürzer werden. 01:14:40.960 --> 01:14:43.440 Noch kürzer, noch kürzer, noch kürzer, noch kürzer. 01:14:43.880 --> 01:14:45.060 Das kann nicht sein, ja. 01:14:46.460 --> 01:14:47.500 Wo ist der Haken? 01:14:49.400 --> 01:14:53.180 Also, zum einen irgendwann, ich habe gerade schon gesagt, wenn Sie 01:14:53.180 --> 01:14:56.400 Glück haben von den vielen denkbaren verschiedenen Blöcken, es kommen 01:14:56.400 --> 01:14:57.980 gar nicht so viele in Ihrem Wort vor. 01:14:58.980 --> 01:15:01.960 Aber wenn Sie jetzt einmal komprimiert haben und da wieder Blöcke 01:15:01.960 --> 01:15:04.960 angucken, da kommen vielleicht, das sind jetzt Blöcke aus Nullen und 01:15:04.960 --> 01:15:08.440 Einsen, aber da kommen jetzt vielleicht sehr viele verschiedene vor 01:15:08.440 --> 01:15:12.640 und dann liefert Ihnen Huffman-Kodierung überhaupt nichts mehr. 01:15:14.360 --> 01:15:15.120 Das ist das eine. 01:15:15.440 --> 01:15:19.360 Das andere in der Praxis, wenn Sie in der Datei nehmen, komprimieren 01:15:19.360 --> 01:15:22.180 und das, was rauskommt, nochmal komprimieren und nochmal komprimieren, 01:15:22.640 --> 01:15:24.800 dann merken Sie, irgendwann werden die Dateien wieder länger. 01:15:27.040 --> 01:15:28.200 Und woran liegt das? 01:15:29.560 --> 01:15:32.780 Naja, also in der Praxis, wenn Sie eine Datei komprimieren, wenn da 01:15:32.780 --> 01:15:36.300 sowas wie Huffman-Kodierung drinsteckt, dann müssen Sie natürlich auch 01:15:36.300 --> 01:15:40.240 mit reinschreiben, diese Tabelle, was sind denn die einzelnen 01:15:40.240 --> 01:15:42.440 Kodwörter, damit man wieder dekodieren kann. 01:15:43.860 --> 01:15:46.520 Und die Tabelle wird einfach irgendwann zu groß. 01:15:49.920 --> 01:15:50.180 Gut. 01:15:51.560 --> 01:15:54.740 Also Blockkodierung ist der Trick, um tatsächlich zu kürzeren Wörtern 01:15:54.740 --> 01:16:00.380 zu kommen, wenn das Wort hinreichend nett ist, also wenn zum Beispiel 01:16:00.380 --> 01:16:05.300 da ständig steht ABC, ABC, ABC, ABC, ABC, ABC, ABC. 01:16:06.060 --> 01:16:11.020 Da kodieren Sie halt ABC durch eine 1 und schwupp ist die Länge nur 01:16:11.020 --> 01:16:11.560 noch ein Drittel. 01:16:11.840 --> 01:16:14.380 Wenn da keine anderen Blöcke vorkommen, alles ganz einfach. 01:16:17.870 --> 01:16:18.130 So. 01:16:19.290 --> 01:16:22.890 Das ist Huffman-Kodierung, also das liefert Ihnen einen Präfixfreien 01:16:22.890 --> 01:16:28.030 Code und der ist sogar so kurz, kürzer geht es nicht für Präfixfreie 01:16:28.030 --> 01:16:28.430 Codes. 01:16:29.670 --> 01:16:33.110 Und Präfixfreie Codes sind schön, weil sie einfach zu dekodieren sind. 01:16:33.470 --> 01:16:36.410 Sie müssen nur einmal von links nach rechts drüber gehen und dann, 01:16:36.770 --> 01:16:43.310 wenn Sie ein Codewort haben, sehen Sie immer als Anfangsstück ein und 01:16:43.310 --> 01:16:46.990 auch nur ein Codewort eines einzelnen Symbols und dann wissen Sie, wie 01:16:46.990 --> 01:16:49.270 Sie das dekodieren müssen und dann machen Sie mit dem Rest weiter. 01:16:50.730 --> 01:16:52.350 Das ist ganz, ganz einfach. 01:16:57.090 --> 01:17:00.070 Und also das, was ich Ihnen beschrieben habe, ich habe es ja gesagt, 01:17:00.210 --> 01:17:01.570 es ist... 01:17:01.570 --> 01:17:03.890 Ich habe das, glaube ich, einen Algorithmus genannt. 01:17:04.910 --> 01:17:06.990 Das war jetzt noch nicht so ganz präzise. 01:17:07.070 --> 01:17:09.190 Ich habe an einigen Stellen gesagt, ob Sie das links oder rechts 01:17:09.190 --> 01:17:11.590 hinmalen, ob Sie da 0 oder 1 dran schreiben, wenn Sie mehrere 01:17:11.590 --> 01:17:15.010 Möglichkeiten haben, mit gleicher Häufigkeit, welche zwei Sie nehmen, 01:17:15.070 --> 01:17:15.570 ist egal. 01:17:17.670 --> 01:17:21.810 In Java können Sie natürlich nicht hinschreiben, wenn da mehrere 01:17:21.810 --> 01:17:24.910 Knoten sind mit gleicher Häufigkeit, nimm einfach irgendwelche. 01:17:25.430 --> 01:17:29.490 Das wird man dann halt einfach festlegen und egal, was man festlegt, 01:17:29.590 --> 01:17:32.170 es kommt halt immer ein gleich guter Huffman-Code raus. 01:17:34.110 --> 01:17:34.550 Gut. 01:17:37.010 --> 01:17:40.750 Damit sind wir am Ende dieses Kapitels und 01:17:45.130 --> 01:17:47.810 abgesehen von Huffman-Codierung, was wir also gesehen haben, ist 01:17:47.810 --> 01:17:53.170 Zahlrepräsentation, Binär, Zweierkomplement und solche Dinge und das 01:17:53.170 --> 01:17:57.070 werden wir dann auch brauchen, wenn wir uns den prinzipiellen Aufbau 01:17:57.070 --> 01:17:58.410 einer CPU angucken. 01:18:00.430 --> 01:18:04.650 Und bevor wir uns eine ganze CPU, einen ganzen Prozessor angucken, 01:18:06.030 --> 01:18:09.030 reden wir mal kurz noch ein bisschen über Speicher. 01:18:10.470 --> 01:18:12.670 Nicht viel, das ist ein ganz kurzes Ding. 01:18:13.450 --> 01:18:16.110 Sie sehen ja nur 18 Folien und die erste ist die da. 01:18:20.510 --> 01:18:26.390 Aber um uns schon mal vielleicht so ein bisschen darauf vorzubereiten 01:18:26.390 --> 01:18:30.450 und nebenbei halt wieder noch zwei, drei andere Sachen zu üben und zu 01:18:30.450 --> 01:18:32.810 erwähnen, die irgendwie wichtig sind. 01:18:33.650 --> 01:18:38.270 Das erste, diese Worte, die habe ich auch schon x-mal benutzt, ja, Bit 01:18:38.270 --> 01:18:38.970 und Byte. 01:18:39.670 --> 01:18:44.410 Da ist heutzutage mehr oder weniger klar, was man meint, aber das war 01:18:44.410 --> 01:18:45.090 nicht immer so. 01:18:45.630 --> 01:18:47.730 Also, was ist ein Bit? 01:18:48.990 --> 01:18:52.950 Also für uns in dieser Vorlesung einfach ein Bit, das ist immer eins 01:18:52.950 --> 01:18:54.670 von den zwei Zeichen, 0 oder 1. 01:18:56.290 --> 01:18:59.610 Aber das ist durchaus nicht die einzige Bedeutung von einem Bit. 01:19:00.310 --> 01:19:05.830 Es gibt auch andere, sinnvolle, aber die Dinger heißen halt auch Bits 01:19:05.830 --> 01:19:09.490 und wenn Sie im dritten Semester Theoretische Grundlagen der 01:19:09.490 --> 01:19:13.070 Informatik hören, dann werden Sie da eine andere Bedeutung 01:19:13.070 --> 01:19:13.710 kennenlernen. 01:19:17.640 --> 01:19:20.480 Aber für uns einfach 0 oder 1, ja, eins von den Zeichen. 01:19:20.720 --> 01:19:21.720 Was ist ein Byte? 01:19:22.020 --> 01:19:25.660 Na, heutzutage sind sich da eigentlich alle einig, das sind einfach 8 01:19:25.660 --> 01:19:25.940 Bits. 01:19:27.060 --> 01:19:31.360 8 und nicht mehr und nicht weniger, das ist heute das Übliche. 01:19:32.100 --> 01:19:33.760 Aber das war nicht immer so. 01:19:33.860 --> 01:19:37.400 Es gab eine Zeit, da hat man Maschinen gebaut, da haben die Hersteller 01:19:37.400 --> 01:19:40.580 von Bytes geredet und ein Byte hatte nur 6 Bit oder so etwas. 01:19:41.260 --> 01:19:43.380 Also die Bedeutung hat sich da einfach auch gewandelt. 01:19:44.480 --> 01:19:49.060 Also wenn Sie in Manuals von alten Rechnern so von vor 40, 50 Jahren 01:19:49.060 --> 01:19:52.540 lesen und Sie lesen einen Byte, interpretieren Sie da nicht zu viel 01:19:52.540 --> 01:19:52.940 hinein. 01:19:54.320 --> 01:19:57.660 Und deswegen, also manche Leute sagen dann auch lieber Oktett und die 01:19:57.660 --> 01:19:59.280 Franzosen sagen sowieso Oktett. 01:20:00.940 --> 01:20:03.940 Aber das finden Sie auch in vielen RFCs. 01:20:03.980 --> 01:20:07.040 Die sagen nicht Byte, die sagen Oktett und da steckt dieses 01:20:07.940 --> 01:20:11.660 lateinische, griechische, ich weiß nicht was, beides Wort für 8 drin. 01:20:14.640 --> 01:20:18.900 Und dann gibt es Abkürzungen für Bit und Byte und Oktett für Bit. 01:20:21.520 --> 01:20:24.760 Sinnvollerweise ist irgendwie üblich, wirklich BIT hinzuschreiben. 01:20:27.100 --> 01:20:30.660 Manche Leute benutzen die Abkürzung ein kleines b, aber das ist 01:20:30.660 --> 01:20:34.620 offiziell schon die Abkürzung für eine Flächeneinheit, von der Sie 01:20:34.620 --> 01:20:37.420 wahrscheinlich genauso wenig gehört haben wie ich, bevor ich zum 01:20:37.420 --> 01:20:38.980 ersten Mal darauf gestoßen wurde. 01:20:40.620 --> 01:20:43.300 Sie können ja mal nachgucken, wie groß ein Bahn ist. 01:20:44.660 --> 01:20:48.540 Für Byte nimmt man dann doch ein großes b, obwohl das auch schon eine 01:20:48.540 --> 01:20:49.820 andere Bedeutung hat. 01:20:51.640 --> 01:20:54.920 Vielleicht haben Sie schon mal irgendwo die Abkürzung klein d, groß b 01:20:54.920 --> 01:20:56.420 für Dezibel gelesen. 01:20:57.740 --> 01:20:59.120 Also das ist mehrdeutig. 01:20:59.560 --> 01:21:04.620 Und wenn Sie irgendwo ein kleines o lesen, dann steht das für Oktett 01:21:04.620 --> 01:21:06.400 und ist so gut wie Byte. 01:21:11.000 --> 01:21:15.860 Hier ist ein Bild von einem Stück Speicher, so wie man Speicher vor 01:21:15.860 --> 01:21:18.360 ein paar Jahrzehnten gebaut hat. 01:21:20.020 --> 01:21:21.980 Also das ist schon... 01:21:22.820 --> 01:21:25.540 Also vor noch längerer Zeit hat man ja noch ganz andere Speicher 01:21:25.540 --> 01:21:25.800 gebaut. 01:21:26.120 --> 01:21:29.140 Aber hier, da sehen Sie ja vielleicht diese kleinen schwarzen Krümel 01:21:29.140 --> 01:21:31.260 in der Mitte, so in diesem Rechteck angeordnet. 01:21:31.260 --> 01:21:37.040 Das sind kleine Ringe aus eisenhaltigem Material. 01:21:37.480 --> 01:21:38.020 Ringe mit Loch. 01:21:38.760 --> 01:21:42.140 Und das sind dann so vertikal und horizontal und so sind Fäden 01:21:42.140 --> 01:21:43.400 durch... 01:21:43.400 --> 01:21:46.260 Drähte durchgefädelt durch diese kleinen Eisenringe. 01:21:47.680 --> 01:21:51.320 Und das ist so regelmäßig angeordnet und das ist halt magnetisierbar. 01:21:52.100 --> 01:21:55.080 Und je nachdem, ob die Magnetisierung in der einen oder in der anderen 01:21:55.080 --> 01:21:58.140 Richtung ist, konnte man in einem so kleinen Eisenring eine 0 oder 1 01:21:58.140 --> 01:21:58.680 speichern. 01:22:02.120 --> 01:22:05.600 Und man konnte dann, wenn Sie geschickt Strom durch die richtigen 01:22:05.600 --> 01:22:10.520 Drähte schicken, können Sie auf einem Draht sehen, war da eine 0 oder 01:22:10.520 --> 01:22:11.700 eine 1 gespeichert. 01:22:11.860 --> 01:22:14.400 Allerdings haben Sie beim Lesen dieses Bit kaputt gemacht. 01:22:15.240 --> 01:22:17.560 Deswegen jedes Mal, wenn man ein Bit gelesen hat, musste man es 01:22:17.560 --> 01:22:20.500 hinterher auch schnell wieder reinschreiben, damit es drin blieb. 01:22:21.120 --> 01:22:22.440 Also das war so früher. 01:22:23.780 --> 01:22:26.460 Also jeder kleine Eisenring ja ein Bit. 01:22:27.020 --> 01:22:29.440 Also da können Sie fast noch zählen, wie viele das sind. 01:22:29.540 --> 01:22:31.720 Das sind ein paar Dutzend oder paar Hundert. 01:22:32.500 --> 01:22:39.240 Und ungefähr genauso groß ist ungefähr die kleine SSD, die ich auf 01:22:39.240 --> 01:22:43.500 meinem neuen Mainboard habe, nur dass da irgendwie 512 Gigabyte oder 01:22:43.500 --> 01:22:44.380 sowas drauf sind. 01:22:44.520 --> 01:22:45.880 Also um Längen mehr. 01:22:46.380 --> 01:22:48.960 Also Hauptspeicher hat irgendwie so viele Bytes. 01:22:49.060 --> 01:22:51.780 Große Festplatten haben irgendwie so viele Bytes. 01:22:51.980 --> 01:22:54.820 Und Sie merken schon, kein normaler Mensch schreibt diese Zahlen so 01:22:54.820 --> 01:22:58.340 hin, weil es so mühsam ist, nachzuprüfen, wie groß ist die Zahl denn 01:22:58.340 --> 01:22:58.840 jetzt eigentlich. 01:22:59.040 --> 01:23:01.840 Ist das jetzt hier ein Mega, ein Giga, ein Terabyte? 01:23:03.820 --> 01:23:09.080 Also man benutzt solche Präfixe, um Sachen kompakter auszudrücken. 01:23:11.640 --> 01:23:12.900 Das kennen Sie alle. 01:23:13.520 --> 01:23:17.940 Und für so 10 hoch 3, 6, 9 und 10 hoch minus 3, minus 6, die 01:23:17.940 --> 01:23:22.120 Abkürzungen, die Präfixe kennen Sie alle, so Milli und Mikro und Kilo 01:23:22.120 --> 01:23:24.020 haben Sie alle tausendmal gesehen. 01:23:25.220 --> 01:23:26.260 Kilomal sozusagen. 01:23:28.700 --> 01:23:33.360 Sie können ja mal ausrechnen, wie lang ein Atoparsec ist, nur mal so 01:23:33.360 --> 01:23:34.080 spaßhalber. 01:23:34.980 --> 01:23:36.120 Eine schöne Längeneinheit. 01:23:37.340 --> 01:23:41.600 Ato steht da oben, 10 hoch minus 18, Parsec müssen Sie nachlesen, wie 01:23:41.600 --> 01:23:42.580 lang das ungefähr ist. 01:23:43.680 --> 01:23:48.480 Also es gibt diese Abkürzungen und die stehen also für 1000 hoch 1, 01:23:48.640 --> 01:23:50.960 1000 hoch 2000 hoch 3 und so weiter. 01:23:52.980 --> 01:23:55.100 Mikro, Nano, Pico, Femto, Ato. 01:24:00.260 --> 01:24:05.000 Bei den kleinen Einheiten, da können Sie zum einen mal gucken, Sie 01:24:05.000 --> 01:24:08.940 können mal ausrechnen, hinschreiben, wie viele Sekunden mit so einem 01:24:08.940 --> 01:24:12.840 Ding ein Zyklus eines normalen Prozessors heutzutage ist. 01:24:13.220 --> 01:24:16.500 Und Sie können davon ausgehen, auf so einem Prozessor innen drin, die 01:24:16.500 --> 01:24:18.920 Zeiteinteilung ist noch kleiner, noch feiner. 01:24:19.760 --> 01:24:24.080 Aber in der Informatik häufig ist es halt naheliegend, nicht mit 01:24:24.080 --> 01:24:29.880 Potenzen von 1000 zu rantieren, sondern mit Potenzen von 1024, 2 hoch 01:24:29.880 --> 01:24:30.260 10. 01:24:32.020 --> 01:24:38.140 Und deswegen hat man irgendwann so andere Präfixe definiert für Kilo 01:24:38.140 --> 01:24:41.280 -Binary, Mega-Binary und Gibi-Binary und so. 01:24:42.420 --> 01:24:45.020 Und die liest man dann Kibi, Mäbi, Gibi. 01:24:46.080 --> 01:24:52.500 Und Kibi sind also 1024, Mäbi 1024 zum Quadrat, Gibi 1024 hoch 3 und 01:24:52.500 --> 01:24:52.600 so. 01:24:52.860 --> 01:24:55.220 Und die Abkürzungen K, I, M, I, G, I. 01:24:56.540 --> 01:25:01.680 Also wenn Sie irgendwo sehen, großes G, kleines I, kleines O, dann ist 01:25:01.680 --> 01:25:03.140 das ein Gibi-Oktet. 01:25:03.980 --> 01:25:05.480 Das ist sowas wie ein Gigabyte. 01:25:05.980 --> 01:25:08.780 Nur ein bisschen präziser, weil es nämlich in Wirklichkeit nicht ein 01:25:08.780 --> 01:25:15.700 Gigabyte sind, eine Milliarde Byte, sondern also 10 hoch 9, sondern 2 01:25:15.700 --> 01:25:16.400 hoch 30. 01:25:18.120 --> 01:25:20.180 Also im Prinzip ist man hier präziser. 01:25:21.600 --> 01:25:23.780 Allerdings, das wissen Sie vielleicht auch, wenn Sie Festplatten 01:25:23.780 --> 01:25:28.040 kaufen, da stehen immer irgendwelche Größenangaben drin. 01:25:28.120 --> 01:25:31.480 Die sind natürlich nur so näherungsweise, weil so eine Festplatte mit 01:25:31.480 --> 01:25:33.660 magnetischen Platten... 01:25:33.660 --> 01:25:36.120 Wer hat noch so eine richtige Festplatte in seinem Rechner, so 01:25:36.120 --> 01:25:37.120 richtig, wo sich was dreht? 01:25:37.200 --> 01:25:37.480 Ja, ne? 01:25:38.760 --> 01:25:41.760 Da sind halt manchmal so Sektoren kaputt und deswegen das wirklich 01:25:42.220 --> 01:25:44.920 Nutzbare ist kleiner als das, was da maximal drauf ist. 01:25:46.320 --> 01:25:46.800 So. 01:25:48.700 --> 01:25:49.180 Okay. 01:25:51.700 --> 01:25:55.660 Also wenn Sie sowas irgendwo lesen, Gibi-Oktet oder so, dann wissen 01:25:55.660 --> 01:25:56.740 Sie jetzt auch, was das ist. 01:25:57.960 --> 01:26:01.560 Und dann machen wir am Freitag weiter.