Entwickler-Ecke
Algorithmen, Optimierung und Assembler - math. Beweis d. Nichtexistenz d. perf. Komprimierungsverf.
fuggaz - Fr 15.02.08 23:02
Titel: math. Beweis d. Nichtexistenz d. perf. Komprimierungsverf.
Hallo,
Es gibt ja kein perfektes Komprimierungsverfahren, da es immer auf die Daten ankommt, die man komprimieren möchte.
Ich habe aber von dem "Beweis der Nichtexistenz des perfekten Verfahrens" gelesen.
Das hört sich so an, als existiere da ein mathematische Beweis.
Gibt es den wirklich?
Google sagt oberflächlich nein.
Rein intuitiv sage ich wäre der Beweis mathematisch, allgemein sehr merkwürdig...
Allerdings kann man ja einfach zwei Beispielen und zwei verschiedene Arten von Daten kombinieren und zeigen, dass mal das eine Verfahren, mal das andere eine Vorteil aufweist.
Aber falls es doch so einen schönen Beweis gibt, würde ich davon gerne wissen;)
mfg fuggaz
fuggaz - Sa 16.02.08 00:01
Die Artikel kenn ich schon.
Danke dir trotzdem;)
Falls es keinen wirklich Beweis gibt, dann ist dies nur umso praktischer für mich.
Dann kann ich anhand von leichten Bsp. zeigen, dass es logischerweise keine perfektes Verfahren geben kann.
Ansonsten müsste ich den Beweis halt wenigstens nenne, wenn nicht sogar erklären.
Also ich bitte um euer Nichtwissen von einem solchen Beweis;) :-D
Oder dem Wissen der Nichtexistenz des Beweises der Nichtexistenz...^^
AXMD - Sa 16.02.08 00:08
Ist zwar nicht sehr wissenschaftlich, aber die einfachste Erklärung sehe ich zusätzlich darin, dass du keine halben Bits bzw. andere Bruchteile von Bits speichern kannst. Ich meine du kannst schon, aber du brauchst dafür ganze Bits. Klar gibt es Spezialfälle, in denen jedes Zeichen mit einer ganzen Anzahl von Bits optimal kodiert werden kann, aber wie oft kommt das in der Praxis schon vor?
AXMD
fuggaz - Sa 16.02.08 00:26
Exakt, wie oft kommt das schon vor.
Ja ich werde das wohl so auch schreiben.
alzaimar - Sa 16.02.08 00:39
Ich glaube, es geht eher darum, das es nicht einen perfekten Komprimierungsalgorithmus geben kann. Es kann jedoch sehr wohl eine perfekte Komprimierung geben. Und hier ist der Beweis sehr einfach (nämlich durch Kontraindikation):
Wir behaupten, es gäbe keine Komprimierung, die nicht doch weiter komprimiert werden könnte. Daraus folgt, das es mindestens eine Komprimierung gibt, die weiter komprimiert werden kann. Nun, dann komprimieren die eben nochmal. Wegen der Ausgangsforderung kann es sein, das diese komprimierte Komprimierung nicht perfekt ist. Also komprimieren wir wieder... Goto 1.
.... Es ist klar, das das nicht funktioniert, denn wenn, dann würde das Ergebnis irgendwann 0 bits lang sein.... Ergo: Es gibt eine Komprimierung, die nicht weiter komprimiert werden kann.
Interessant ist die Überlegung, das es keinen perfekten Komprimierungsalgorithmus geben kann. Denn daraus folgt sofort, das es unendlich viele KA geben muss. Gäbe es nur endlich viele, könnte ich den perfekten KA dadurch konstruieren, das ich die zu komprimierende Information einfach durch alle KA jage, und das kürzeste Ergebnis liefere. Et voila! Der perfekte KA. Dies steht im Widerspruch zur Behauptung und damit q.e.d.
Wenn es jedoch unendlich viele KA gibt, bedeutet dies, das das Ende der Fahnenstange (angedeutet durch 7-Zip, Markov und BZIP) noch lange nicht erreicht ist.
fuggaz - Sa 16.02.08 02:01
Ja wobei dabei natürlich viele Verfahren in einem einzigen implementiert werden.
Damit wäre der Unterschied zwischen den Verfahren aufgehoben und meine Bedingung über den Haufen geworfen.
Es soll ja jedes Verfahren als einzelnes dastehen.
Die perfekte Komprimierung gibt es natürlich im speziellen Fall.
Danke, dass du mich aber nochmal explizit darauf hingewiesen hast.
Das werde ich in einem Teil zusammen nennen, da es doch zusammengehört.
Tilo - Sa 16.02.08 07:15
Mein Ansatz zur Nichtexistenz:
Anhnahme: Es gibt perfekten Komprimieralgorythmus.
Folge: Es ist möglich unendlich viele Nachrichten mit y Zeichen auf x Zeichen, mit y>x und x,y endliche natürliche Zahlen, zu komprimieren.
Mit x Zeichen ist es aber nur möglich x^|Basis|, mit Basis als endliche Menge, viele Nachrichten zu kodieren.
Folge es muss gelten x^|Basis|>=unendlich.
Logischer Widerspruch. Demnach gibt es keinen perfekten Komprimieralgorythmus.
delfiphan - Sa 16.02.08 08:51
Natürlich gibt es den. Man nehme eine Nachricht, die 2 Bits lang ist und komprimiert ihn auf 1 Bit. Bei 2 Bits gibt es nun 4 verschiedene mögliche Texte. Bei 1 Bit gibt's nur noch 2 mögliche Texte: 1 und 0. Du kannst jetzt nur die 1 und die 0 dekomprimieren, kannst also nur 2 Ausgangstexte erhalten, nicht die ursprünglichen 4. Es kann also gar nicht sein, dass du alle 4 Texte um ein Bit komprimieren kannst, denn mit 1 Bit kannst du nun mal bloss 2 Texte darstellen.
Falls man jede Nachricht durch Kompression immer weiter verkürzen könnte, könnte man jede Nachricht durch mehrmaliges Komprimieren auf 1 Bit reduzieren. Wenn's den perfekten Algorithmus, wie du ihn nennst, gäbe, dann könntest du jeden x-beliebigen Text durch 1 Bit und die Anzahl angewendeter Kompressionen speichern.
Der math. Beweis findest du IIRC irgendwo im Forum und auch bestimmt im Netz.
alzaimar - Sa 16.02.08 09:49
 fuggaz hat folgendes geschrieben: |
Ja wobei dabei natürlich viele Verfahren in einem einzigen implementiert werden.
Damit wäre der Unterschied zwischen den Verfahren aufgehoben und meine Bedingung über den Haufen geworfen. |
Welche Bedingung? Zip ist ein kombinierter RLE und ZLW. ZLW selbst ist ja eine Kombination aus Bitkodierung und Dictionary. So ziemlich jeder Komprimierungsalgorithmus implementiert mehrere Verfahren. Beim Beweis der Existenz bzw. nichtexistenz ist es doch legitim, einen Monsteralgorithmus zu entwerfen, der von mir aus 10^10 Zeilen hat und 1000000 Jahre benötigt. So lange er endlich lang ist und terminiert, ist es ein Algorithmus bzw. eine E/A-Relation.
@Delfiphan: Imho hast Du mit deiner 2->1 Bit Geschichte nur bewiesen, das man eine isolierte Information der Länge 2 Bit nicht verlustfrei auf 1 Bit komprimieren kann (ohne zu wissen, was die 2 Bit bedeutet). Der perfekte KA (PKA) könnte doch zum Ergebnis kommen, das bei 2 Bit Schluss ist.
Ich glaube, es gibt sehr wohl einen PKA, und der funktioniert so: Er schmeisst die gesamte Redundanz aus der Information raus. :mrgreen:
Dazu müsste er die Information jedoch verstehen. Enthält die Information keine Redundanz, komprimiert er auch nicht. Wenn deine 2 Bit-Information die Zustände von 2 Lampen beschreiben würde, ist in den 2 Bits nun mal keine Redundanz. Beschreibt es dagegen den Zustand einer Lampe, wobei 00 = Aus und (01,10,11) = An bedeutet, dann kann man die 2 Bits sehr wohl komprimieren.
Ich behaupte also, das es sehr wohl mindestens einen PKA gibt. Ich weiss auch, wie er aussieht: Ein ziemlich großes neuronales Netz, genannt 'Gesunder Menschenverstand'...
Gausi - Sa 16.02.08 09:55
Vielleicht sollten wir zur endgültigen Klärung erst einmal definieren, was ein
perfekter Komprimierungsalgorithmus überhaupt ist.
- er verkleinert jede Nachricht
- er verkleinert jede Nachricht besser als jeder andere Algorithmus
- er macht jede Nachricht nicht größer
- er macht jede Nachricht nicht größer als jeder andere Algorithmus
- er beseitigt jede Form von Redundanz (was ist bitte schön das genau?)
delfiphan - Sa 16.02.08 11:26
alzaimar: Das war nur ein Beispiel und kein Beweis. Genauer gesagt ein Gegenbeispiel. Ein Gegenbeispiel genügt jedoch, um die Aussage "Es existiert ein Algorithmus, der jede Nachricht verkürzen kann" zu widerlegen. Wie gesagt ist der formale Beweis iirc irgendwo im Forum.
Der Beweis geht mehr oder weniger so, dass es nicht möglich ist, eine injektive Funktion zu haben, welche eine Menge A auf eine kleinere Menge B abbildet. Schubfachprinzip o.ä.
fuggaz - Sa 16.02.08 16:24
Ich seh das ganze eher aus praktischer Sicht.
Wie man auch sagen kann:
Es ist möglich mit 99,9999...% der Lichtgeschwindigkeit zu reisen.
Jedoch praktisch gibt es da ein Problem.
Ich weiß, dass die guten Programme mehrere Verfahren kombinieren, jedoch will ich nur sagen, dass aus praktischer Sicht es kein Einzelverfahren gibt, das perfekt ist.
Also ein Einzelverfahren ist meinetwegen die Huffman-Kodierung.
Eine Kombination wäre dann eine Wörterbuchalgorithmus, auf den man die Huffman-Kodierung anschließend loslässt.
"Der math. Beweis findest du IIRC irgendwo im Forum und auch bestimmt im Netz.":
Kannst du mir eine Stichworttip geben?
Ich weiß nicht nach was ich da suchen soll.
Wie gesagt habe ich bei google nicht viel gefunden. Wahrscheinlich suche ich einfach nach dem falschen.
alzaimar - Sa 16.02.08 16:46
| Gausi hat folgendes geschrieben: |
Vielleicht sollten wir zur endgültigen Klärung erst einmal definieren, was ein perfekter Komprimierungsalgorithmus überhaupt ist.
* er verkleinert jede Nachricht |
Nein. Ein PKA komprimiert nur jede Information besser als jeder andere Algorithmus.
| Gausi hat folgendes geschrieben: |
er beseitigt jede Form von Redundanz (was ist bitte schön das genau?)
|
Ich nenne die Redundanz eines Textes die Menge an Daten, die nicht dazu dienen, Information darzustellen. Nenne es 'für das Verständnis der Information nicht wichtige Daten'. Oder so: Daten = Information + Redundanz. Bei einer positiven ganzen Zahl < 256, die durch ein 4 Byte Int dargestellt wird, sind mindestens drei Bytes überflüssig. Sie dienen also nicht zur Darstellung der Zahl, sondern reservieren Platz, falls selbige mal wächst. Oder vereinheitlichen die Darstellung, damit eben auch Zahlen > 255 mit dem gleichen Format dargestellt werden können.
| delfiphan hat folgendes geschrieben: |
| ... Ein Gegenbeispiel genügt jedoch, um die Aussage "Es existiert ein Algorithmus, der jede Nachricht verkürzen kann" zu widerlegen... |
Imho geht es nicht darum, denn das ist eh klar. Dieser fiktive 'Immer-Verkleinerer' muss ja bloß in einer Schleife immer auf seinen eigenen Output angesetzt werden und würde aus jeder Information 0 bits machen. Verlustfrei :party:
Aber richtig, da die Definition eines PKA nicht klar ist, sollte man das vielleicht erstmal ausformulieren. Ich habe den TE so verstanden, das er meint, ein PKA sei ein einziger Algorithmus, der jeden Text, jede Information immer optimal komprimiert.
Allerdings ist die Einschränkung auf ein 'Verfahren' so nicht möglich, denn wo soll man die Grenze ziehen zwischen 'Kombination' und 'Einzelverfahren'?. Wich ich bereits sagte, ist LZW schon eine Kombination. Fuggaz will ein paar Zeilen Code, die optimal sind. Und das geht nicht (wegen der 'paar Zeilen'). Ein PKA muss -wenn es ihn gibt- die Information erstmal verstehen, um dann eben das Wesentliche zu extrahieren und das optimal kodiert darzustellen.
Man kann z.B. ein Bild sehr gut komprimieren, in dem man genau erklärt, was auf ihm zu sehen ist. Das Resultat ist kleiner als jedes GIF. Ein Film ist schnell erzählt und i.a. ist das Buch, auf dem er basiert, viel viel kompakter zu komprimieren, als der Film. Trotzdem ist der Informationsgehalt (wenn man die Story als Information definiert, und nicht das Makeup der Hauptdarsteller) 100% enthalten.
Wie gesagt: Optimal Komprimieren ohne Verständnis des Inhaltes geht nicht. Mit Verständnis schon.
tommie-lie - Sa 16.02.08 17:08
| delfiphan hat folgendes geschrieben: |
| "Es existiert ein Algorithmus, der jede Nachricht verkürzen kann" zu widerlegen. |
Wenn es dir nur darum geht, diese Aussage zu widerlegen, das Handwerkzeug dafür heißt Schubfachprinzip und lernt man im ersten Semester des Informatik-Studiums.
Der komplette Beweis ist wenige Zeilen lang ist und ist
hier [
http://www.faqs.org/faqs/compression-faq/part1/section-8.html] in Section 9.2 zu finden.
Informationstheoretisch entfernt ein Kompressionsalgorithmus Redundanzen. Irgendwann enthält eine gegebene Nachricht keine Redundanz mehr, sie ist also absolut zufällig. Ab dieser Stelle ist es nicht mehr möglich, Informationen zu entfernen und so die Nachricht zu verkürzen, ohne Entropie zu verlieren, was automatisch zum Verlust der Originalnachricht führt. Es ist sichelich möglich, einen Algorithmus zu entwerfen, der eine gegebene Nachricht so weit verkürzt, daß sie keinerlei Redundanz mehr enthält. Allerdings ist dann dort das Ende der Fahnenstange für diese Nachricht, verkürzt man sie weiter, kann man die Originalnachricht nicht mehr restaurieren.
| alzaimar hat folgendes geschrieben: |
| Ein PKA muss -wenn es ihn gibt- die Information erstmal verstehen, um dann eben das Wesentliche zu extrahieren und das optimal kodiert darzustellen. |
Nicht notwendigerweise, um eine redundanzfreie Nachricht zu erhalten. Allerdings können spezialisierte Algorithmen jederzeit weiter Informationen entfernen, die ein ebenso spezialisierter Algorithmus zur Umkehrung der Kompression wieder hinzufügt. Beispielsweise kann man bei einer HMTL-Seite bestimmte Teile der Nachricht, wie zum Beispiel das schließende </html> am Ende, einfach weglassen, denn der Dekomprimierungsalgorithmus weiß, daß jede Nachricht diese Information enthält und kann sie so wieder einfügen. Die Komprimierung liegt hier also auch in der Spezialisierung. Man kann nicht ohne den spezialisierten Algorithmus wieder die ursprüngliche Information besorgen.
| alzaimar hat folgendes geschrieben: |
| Man kann z.B. ein Bild sehr gut komprimieren, in dem man genau erklärt, was auf ihm zu sehen ist. Das Resultat ist kleiner als jedes GIF. Ein Film ist schnell erzählt und i.a. ist das Buch, auf dem er basiert, viel viel kompakter zu komprimieren, als der Film. Trotzdem ist der Informationsgehalt (wenn man die Story als Information definiert, und nicht das Makeup der Hauptdarsteller) 100% enthalten. |
Nein, das ist verlustbehaftete Kompression. Selbst wenn ich der beste Maler und du der beste Beschreiber von Bildern, du könntest mir nicht ein Bild so beschreiben, daß ich es malen kann und mein Gemälde exakt so aussieht, wie das Originalbild, es sei denn deine Beschreibung ist mindestens so umfangreich wie das Bild selbst. Stell dir einen Baum vor, du müsstest mir sagen wieviele Blätter er hat, welches Blatt welche Größe hat und wie die Äste verzweigt sind, wieviele Grashalme auf der Wiese, auf der er steht, zu erkennen sind und in welchem Winkel sie sich vom Erdboden richtung Himmel strecken.
Sicherlich reicht die Information "Laubbaum auf Wiese" aus, um einen ebensolchen zu malen, aber das wäre eben nicht exakt die gleiche Information wie auf dem ursprünglichen Bild. Genauso reicht JPG und Vorbis oder MP3 aus, um Bilder und Audioinformationen zu komprimieren, aber es sind eben nur Bilder, die so ähnlich aussehen und Audioinformationen, die sich so ähnlich anhören wie das Original.
Hidden - Sa 16.02.08 17:24
| Gausi hat folgendes geschrieben: |
Vielleicht sollten wir zur endgültigen Klärung erst einmal definieren, was ein perfekter Komprimierungsalgorithmus überhaupt ist.
- er verkleinert jede Nachricht, die komprimiert werden kann
- er verkleinert jede Nachricht besser als jeder andere Algorithmus, der diese Nachricht nicht perfekt komprimiert
- er macht jede Nachricht nicht größer
- er macht jede Nachricht nicht größer als jeder andere Algorithmus
- er beseitigt jede Form von Redundanz
|
delfiphan - Sa 16.02.08 23:38
| tommie-lie hat folgendes geschrieben: |
| delfiphan hat folgendes geschrieben: | | "Es existiert ein Algorithmus, der jede Nachricht verkürzen kann" zu widerlegen. |
Wenn es dir nur darum geht, diese Aussage zu widerlegen, das Handwerkzeug dafür heißt Schubfachprinzip |
@tommie-lie: Ich hab auf die ursprüngliche Frage von fuggaz geantwortet. Da er die Frage nicht genauer spezifiziert hat, habe ich hinzugeschrieben, wie ich die Frage interpretiere und darauf geantwortet. Dass man das mit dem Schubfachprinzip beweist, hab ich ja bereits geschrieben - du hast wohl nur die Hälfte gelesen. Danke, dass du uns mitteilst in welcher Klasse du das gelernt hast.
| tommie-lie hat folgendes geschrieben: |
| Irgendwann enthält eine gegebene Nachricht keine Redundanz mehr, sie ist also absolut zufällig. |
Was heisst hier absolut zufällig. Wenn du zufällig Texte generierst, kann es schon mal vorkommen, dass du "00000000000" erhältst. Wenn du diesen Text ausschliesst, weil er nicht zufällig aussieht, dann kann nicht die Rede von Zufall sein. Denn der Zufall bevorzugt nun mal keine bestimmte Sequenz. Was du meinst ist Kolmogorov Zufälligkeit.
Delete - Sa 16.02.08 23:49
| tommie-lie hat folgendes geschrieben: |
| Selbst wenn ich der beste Maler und du der beste Beschreiber von Bildern, du könntest mir nicht ein Bild so beschreiben, daß ich es malen kann und mein Gemälde exakt so aussieht, wie das Originalbild, es sei denn deine Beschreibung ist mindestens so umfangreich wie das Bild selbst. Stell dir einen Baum vor, du müsstest mir sagen wieviele Blätter er hat, welches Blatt welche Größe hat und wie die Äste verzweigt sind, wieviele Grashalme auf der Wiese, auf der er steht, zu erkennen sind und in welchem Winkel sie sich vom Erdboden richtung Himmel strecken. |
nicht ganz richtig, sondern die beschreibung muss mindestens so gut sein, wie du malen kannst ... ;-)
ansonsten, kann man nur ordentlich komprimieren, wenn man weiss um welche art der daten es sich handelt. die verlustfreie und die komprimierung, in der informationen (oberflächlich betrachtet) verloren gehen, wurde bereits gennant. ausserdem muss neben der semantik der daten, auch der zeitfaktor mit berücksichtigt werden... wenn man unendlich viel zeit hat, kann man schon sämtliche möglichkeiten durchprobieren, welche eine relativ gute kompremierungsleistung erreicht, was allerdings nicht heisst, dass es optimal komprimiert ist...
tommie-lie - So 17.02.08 01:28
| delfiphan hat folgendes geschrieben: |
| tommie-lie hat folgendes geschrieben: | | Irgendwann enthält eine gegebene Nachricht keine Redundanz mehr, sie ist also absolut zufällig. |
Was heisst hier absolut zufällig. Wenn du zufällig Texte generierst, kann es schon mal vorkommen, dass du "00000000000" erhältst. Wenn du diesen Text ausschliesst, weil er nicht zufällig aussieht, dann kann nicht die Rede von Zufall sein. Denn der Zufall bevorzugt nun mal keine bestimmte Sequenz. Was du meinst ist Kolmogorov Zufälligkeit. |
Was ist meine ist Zufälligkeit, und dagegen hat auch Kolmogorov nichts einzuwenden. Wenn du eine Berechnungsvorschrift (also eine TM) angeben kannst, die exakt dieselbe
zufällige Nachricht erneut erzeugen kann, ist diese Vorschrift so mindestens lang wie die Nachricht selbst. Mag zwar sein, daß in einem großen Haufen zufälliger Symbole fünf Mal hintereinander eine 0 auftaucht, aber solange dieses Muster nicht berechenbar ist (und da das Muster zufällig ist, ist es das nicht), kannst du damit auch nicht die Nachricht verkürzen.
| Grenzgaenger hat folgendes geschrieben: |
| nicht ganz richtig, sondern die beschreibung muss mindestens so gut sein, wie du malen kannst ... ;-) |
Dann würde man erst Recht nicht das Original erhalten, ist aber schon die Beschreibung nicht so umfangreich wie das Bild selbst,
kann ich nicht das Original wiederherstellen, selbst wenn ich mindestens so gut malen könnte wie der Maler des Originalbildes.
| Grenzgaenger hat folgendes geschrieben: |
| ansonsten, kann man nur ordentlich komprimieren, wenn man weiss um welche art der daten es sich handelt. |
Nein, nicht notwendigerweise. Dieses Zusatzwissen ist ebenfalls Teil der Information und müsste streng genommen mit zur Größe der komprimierten Nachricht dazugezählt werden.
| Grenzgaenger hat folgendes geschrieben: |
| wenn man unendlich viel zeit hat, kann man schon sämtliche möglichkeiten durchprobieren, welche eine relativ gute kompremierungsleistung erreicht, was allerdings nicht heisst, dass es optimal komprimiert ist... |
Durchprobieren? Soweit, so gut, aber wie stellst du fest, daß du die richtige Kombination gefunden hast? Du musst also mit irgendwas vergleichen, was den selben Informationsgehalt hat, wie die Originalnachricht.
delfiphan - So 17.02.08 11:12
| tommie-lie hat folgendes geschrieben: |
| Wenn du eine Berechnungsvorschrift (also eine TM) angeben kannst, die exakt dieselbe zufällige Nachricht erneut erzeugen kann, ist diese Vorschrift so mindestens lang wie die Nachricht selbst. Mag zwar sein, daß in einem großen Haufen zufälliger Symbole fünf Mal hintereinander eine 0 auftaucht, aber solange dieses Muster nicht berechenbar ist (und da das Muster zufällig ist, ist es das nicht), kannst du damit auch nicht die Nachricht verkürzen. |
Nein, ich meine, die Nachricht ist "00000000000...", nichts weiteres vorne und nichts hinten. Es kann durchaus sein, dass du durch Zufall 1000x eine 0 erzeugst, denn jede Sequenz ist gleich wahrscheinlich, wenn du gleichverteilt Zahlen ziehst. Du sprichst von Kolmogorov Zufälligkeit. Ich glaube die Definition muss man schon unterscheiden, sonst könnte man missverstehen, dass jede zufällig gezogene Sequenz nicht komprimierbar ist, weil sie ja zufällig gezogen ist. So ist das aber nicht. Fast jedes (im mathematischen Sinn) Muster, das du durch Zufall ziehst ist Kolmogorov zufällig, aber nicht jede.
"Das Muster ist zufällig, also nicht berechenbar": Das könnte man wieder missverstehen. Du meinst nicht berechenbar durch ein Programm, das kürzer ist als das Muster. Hast zwar weiter oben was davon geschrieben, aber weiter unten ist das nicht implizit annehmbar.
alzaimar - So 17.02.08 11:40
| tommie-lie hat folgendes geschrieben: |
| ...Beispielsweise kann man bei einer HMTL-Seite bestimmte Teile der Nachricht, ... |
Dazu muss er doch trotzdem den Inhalt verstehen ('Ah, is ne HTML-Seite'). Für mich ist das kein Widerspruch zu meiner Behauptung. Wir suchen ja keinen PKA für HTML-Seiten, sondern fragen uns, ob es eine Black-Box gibt, die jeden Text immer optimal komprimiert. Und da behaupte ich immer noch, das das ohne Wissen um den Inhalt nicht gehen kann (Beispiel mit den Lampen).
| tommie-lie hat folgendes geschrieben: |
| alzaimar hat folgendes geschrieben: | | Man kann z.B. ein Bild sehr gut komprimieren, in dem man genau erklärt, was auf ihm zu sehen ist. |
Nein, das ist verlustbehaftete Kompression. |
Wenn für Dich ein Bild nur aus Pixeln besteht, ja. Aber das meinte ich nicht, denn das das verlustbehaftet ist, ist mir klar, denn sonst hätte ich JPG statt GIF geschrieben. Es geht ja um Information. Und ein Bild hat ja auch einen Inhalt und wenn ich den genau beschreibe (Betonung auf 'genau') kann ich das Bild originalgetrei wieder herstellen. Vorausgesetzt natürlich, wir definieren 'Inhalt eines Bildes' nicht als Summe aller Pixel, sondern eben als das, was man sieht. Was ich meine ist der Kontext, vor dem die Komprimierung stattfindet. In der IT wird eine verlustfreie Kompression derzeit immer so definiert, das kein einziges Bit bei der Kompression/Dekompression verloren geht. Ist das nötig? Wenn ich z.B. Programmcode komprimiere, und mache das so, das ich einfach die Verfahren aufzähle ('.. und dann werden die Daten per Hashing gemappt...'), dann kann ich einen Programmcode sehr effektiv komprimieren, und den Code so wieder erstellen, daß er genauso funktioniert. Ok, Leerzeilen, Bemerkungen (wenn ich sie als redundant deklariert habe) sind flöten, und vielleicht sind auch Variablennamen anders, aber es ist im Sinne der E/A-Relation genau das gleiche Programm.
| tommie-lie hat folgendes geschrieben: |
| Selbst wenn ich der beste Maler und du der beste Beschreiber von Bildern, du könntest mir nicht ein Bild so beschreiben, daß ich es malen kann und mein Gemälde exakt so aussieht, wie das Originalbild, es sei denn deine Beschreibung ist mindestens so umfangreich wie das Bild selbst. |
Entschuldige, aber das ist haltloser Quatsch. Jeder Kompressor beschreibt die Information mit anderen Worten und die Beschreibung (der komprimierte Text) ist doch nun wirklich wesentlich kürzer als das Original.
| tommie-lie hat folgendes geschrieben: |
| Stell dir einen Baum vor, du müsstest mir sagen wieviele Blätter er hat, .... |
Du argumentierst so, also ob das, was Du dir nicht vorstellen kannst, nicht existiert. Wie gesagt, ZIP/LHA etc. machen's vor. Wir haben nur noch keine adäquate kompakte Beschreibungssprache für Bilder gefunden, die den Inhalt beschreibt. Weil Du dir das nicht vorstellen kannst, heißt das dann, das es soetwas nicht gibt? ;) .
Ich kann einen ganzen Film informationstechnisch so eindampfen (und ich kann jedes Pixel wieder herstellen ), indem ich den Film mit anderen Worten beschreibe, also nicht als Folge von Bildern und jedes Bild als Folge von Pixeln, sondern eben als Veränderungen der einzelnen Bilder. Auch hier wirst Du als Maler aus meiner Beschreibung den Film wieder 1:1 herstellen können, obwohl meine Beschreibung viel kompakter ist, als der ursprüngliche Film
Wie Du siehst, ist Kompression also nichts Anderes, als die Beschreibung einer Information in einer anderen Sprache. 'Beschreibung' impliziert 'Wissen um des Inhaltes'. Die klassischen KA, also LZH, ZIP etc. beschreiben den Text, indem sie ihn als 'Folge von Bytes' interpretieren. Kompressoren, die wissen, das es sich um einen englischen Text handelt, können viel effektiver komprimieren etc.
tommie-lie - So 17.02.08 15:09
| alzaimar hat folgendes geschrieben: |
| Dazu muss er doch trotzdem den Inhalt verstehen ('Ah, is ne HTML-Seite'). Für mich ist das kein Widerspruch zu meiner Behauptung. Wir suchen ja keinen PKA für HTML-Seiten, sondern fragen uns, ob es eine Black-Box gibt, die jeden Text immer optimal komprimiert. Und da behaupte ich immer noch, das das ohne Wissen um den Inhalt nicht gehen kann (Beispiel mit den Lampen). |
Ich behaupte, daß ein solcher Algorithmus zmindest denkbar wäre, aber daß man eben mit spezialisierten Algorithmen, die über den Aufbau der Nachricht bescheid wissen, noch stärker komprimieren kann, man dann aber streng genommen den Algorithmus selbst zur Größe der Nachricht hinzurechnen müsste, weil in diesem die Information über den Aufbau steckt.
Ein General-Purpose-Algorithmus würde also die Nachricht so weit eindampfen, daß aus der komprimierten Nachricht immer noch hervorgeht, daß es sich um eine Nachricht mit bestimmter Syntax und bestimmten festen Konstrukten handelt. Ein spezialisierter Algorithmus kann auch diese Information noch entfernen und somit die Nachricht weiter verkleinern.
| alzaimar hat folgendes geschrieben: |
| Wenn für Dich ein Bild nur aus Pixeln besteht, ja. Aber das meinte ich nicht, denn das das verlustbehaftet ist, ist mir klar, denn sonst hätte ich JPG statt GIF geschrieben. Es geht ja um Information. Und ein Bild hat ja auch einen Inhalt und wenn ich den genau beschreibe (Betonung auf 'genau') kann ich das Bild originalgetrei wieder herstellen. Vorausgesetzt natürlich, wir definieren 'Inhalt eines Bildes' nicht als Summe aller Pixel, sondern eben als das, was man sieht. |
Ok, für mich wäre an dieser Stelle die Anzahl der Blätter des Baumes eine Information, die im ursprünglichen Bild enthalten ist, die ich also allein durch das Anschauen des Originalbildes bestimmen kann. Wenn für dich die wichtige Information "Baum auf Wiese" ist, dann ist das natürlich sehr viel weniger, als meiner Meinung nach im ursprünglichen Bild enthalten war. Daß "Baum auf Wiese" auch kürzer ist, als eine (in meinem Sinne) vollständige Beschreibung des Bildes, ist dann ebenfalls klar.
| alzaimar hat folgendes geschrieben: |
| Wenn ich z.B. Programmcode komprimiere, und mache das so, das ich einfach die Verfahren aufzähle ('.. und dann werden die Daten per Hashing gemappt...'), dann kann ich einen Programmcode sehr effektiv komprimieren, und den Code so wieder erstellen, daß er genauso funktioniert. |
Ja, man erhält wieder einen ähnlichen Code, der den gleichen Zweck erfüllt. Aber besonders für uns als Programmierer hat doch der Code noch mehr Eigenschaften als nur den reinen Algorithmus. Wenn du extrem ekligen Code hast, ihn auf diese Weise beschreibst und anschließend rekonstruierst, wird dein Code vermutlich einen ganz anderen Ekligkeitsfaktor haben, als der ursprüngliche Code. Informationen über den Kenntnisstand des Entwicklers sind insofern ebenfalls Teil des Codes (übrigens kann auch in einem Bild eine emotionale Nachricht enthalten sein, die der Maler dort ganz bewusst untergebracht hat, und die man bei einer Komprimierung ja möglichst ebenfalls erhalten möchte).
| alzaimar hat folgendes geschrieben: |
| tommie-lie hat folgendes geschrieben: | | Selbst wenn ich der beste Maler und du der beste Beschreiber von Bildern, du könntest mir nicht ein Bild so beschreiben, daß ich es malen kann und mein Gemälde exakt so aussieht, wie das Originalbild, es sei denn deine Beschreibung ist mindestens so umfangreich wie das Bild selbst. |
Entschuldige, aber das ist haltloser Quatsch. Jeder Kompressor beschreibt die Information mit anderen Worten und die Beschreibung (der komprimierte Text) ist doch nun wirklich wesentlich kürzer als das Original. |
Ich sagte umfangreich, das heißt die Menge an Informationen muss gleich sein. Eine Darstellung der Beschreibung kann dabei weniger Platz beanspruchen, als das Originalbild. Beispielsweise kann man die Beschreibung in eine Textdatei speichern und auf CD brennen, die wahrscheinlich kleiner sein wird, als die Leinwand, auf der das Originalbild war. Eine andere Darstellung der Beschreibung wäre, handschriftlich auf einen Bogen Papier zu schreiben, daß dieser dann kleiner ausfällt als die Leinwand, wage ich zu bezweifeln.
Genauso benötigt auch UTF-32 immer mindestens genauso viel Platz wie die Darstellung des gleichen Textes in UTF-8, jedoch ist der Informationsgehalt (der Text selbst) bei beiden Kodierungen der gleiche.
Vielleicht sollte ich als Zusatz auch noch erwähnen, daß, als ich die Analogie mit dem Bild suchte, Redundanzen im Bild vollständig ignorierte. Ein Himmel, der an jeder Stelle exakt die gleiche Farbe hat, lässt sich natürlich sehr viel kürzer beschreiben, als einer, der viele unterschiedliche Farbverläufe und Wolken hat.
| alzaimar hat folgendes geschrieben: |
| Wie Du siehst, ist Kompression also nichts Anderes, als die Beschreibung einer Information in einer anderen Sprache. |
Ja, man sucht die Kodierung, die die wenigste Redundanz enthält.
| alzaimar hat folgendes geschrieben: |
| 'Beschreibung' impliziert 'Wissen um des Inhaltes'. Die klassischen KA, also LZH, ZIP etc. beschreiben den Text, indem sie ihn als 'Folge von Bytes' interpretieren. Kompressoren, die wissen, das es sich um einen englischen Text handelt, können viel effektiver komprimieren etc. |
Ja, das habe ich ja nie bezweifelt, aber ich bin der Meinung, daß man dann eben auch die Information, daß es sich um englischen Text handelt, ebenfalls zur komprimierten Nachricht rechnen müsste. Diese Information ist ja existent und ganz offenbar von absoluter Notwendigkeit, um mit der komprimierten Nachricht wieder die Originalnachricht zu erhalten.
alzaimar - So 17.02.08 15:27
| tommie-lie hat folgendes geschrieben: |
| alzaimar hat folgendes geschrieben: | | Wenn ich z.B. Programmcode komprimiere, ... |
... Aber besonders für uns als Programmierer hat doch der Code noch mehr Eigenschaften als nur den reinen Algorithmus. |
Nee, für mich nicht. Als Aufhänger zum Ärgern ja, aber ansonsten ist Stil und Nomenklatur für mich eben nicht notwendiger Bestandteil von Code.
| tommie-lie hat folgendes geschrieben: |
| Wenn du extrem ekligen Code hast, |
:motz: WIE? ICH UND ECKLIGEN CODE! DAS NIMMST DU SOFORT ZURÜCK :bawling: (woher weisst Du das überhaupt) :zwinker:
| tommie-lie hat folgendes geschrieben: |
| ... Informationen über den Kenntnisstand des Entwicklers sind insofern ebenfalls Teil des Codes (übrigens kann auch in einem Bild eine emotionale Nachricht enthalten sein, die der Maler dort ganz bewusst untergebracht hat, und die man bei einer Komprimierung ja möglichst ebenfalls erhalten möchte). |
Wir reden aneinander vorbei. Ich rede nur von unterschiedlicher Auffassung von Information (neben dem Byte-für-Byte) und den damit möglichen unterschiedlichen Komprimierungen. Aber im Grunde genommen decken sich unsere Ansichten, denn
| tommie-lie hat folgendes geschrieben: |
| ... ist der Informationsgehalt (der Text selbst) bei beiden Kodierungen der gleiche. |
| tommie-lie hat folgendes geschrieben: |
| ... man sucht die Kodierung, die die wenigste Redundanz enthält. |
| tommie-lie hat folgendes geschrieben: |
| ...ich bin der Meinung, daß man dann eben auch die Information, daß es sich um englischen Text handelt, ebenfalls zur komprimierten Nachricht rechnen müsste. Diese Information ist ja existent und ganz offenbar von absoluter Notwendigkeit, um mit der komprimierten Nachricht wieder die Originalnachricht zu erhalten. |
Genau, und so ein Kompressor/Dekompressor hätte die Vorraussetzungen, um immer optimal zu komprimieren. Leider scheitert das bisher an der fehlenden Möglichkeit, Semantik formal zu beschreiben.
tommie-lie - So 17.02.08 19:07
| alzaimar hat folgendes geschrieben: |
| Nee, für mich nicht. Als Aufhänger zum Ärgern ja, aber ansonsten ist Stil und Nomenklatur für mich eben nicht notwendiger Bestandteil von Code. |
Naja, für mich ist das eben auch eine Information, die ih aus dem Code lesen kann.
| alzaimar hat folgendes geschrieben: |
| Genau, und so ein Kompressor/Dekompressor hätte die Vorraussetzungen, um immer optimal zu komprimieren. Leider scheitert das bisher an der fehlenden Möglichkeit, Semantik formal zu beschreiben. |
Jo, allerdings nur für Englische Texte. Setzt man ihm einen deutschen oder chinesischen Text vor, wird er wahrscheinlich nicht ganz so optimale Ergebnisse erzielen.
Wenn ein perfekter Algorithmus jede Nachricht optimal verkürzen soll, klappt das also nicht mit dem Verstecken der Informationen im Algorithmus selbst.
Delete - So 17.02.08 22:36
| tommie-lie hat folgendes geschrieben: |
| Grenzgaenger hat folgendes geschrieben: | | nicht ganz richtig, sondern die beschreibung muss mindestens so gut sein, wie du malen kannst ... ;-) |
Dann würde man erst Recht nicht das Original erhalten, ist aber schon die Beschreibung nicht so umfangreich wie das Bild selbst, kann ich nicht das Original wiederherstellen, selbst wenn ich mindestens so gut malen könnte wie der Maler des Originalbildes. |
kommt doch auch auf deine perspektive an... ob aus dem flugzeug, ob du auf dem boden stehst oder ob du mit dem elektronenmikroskop auf deinen baum/deine landschaft guckst... je nachdem brauchst du unterschiedliche informationen um dein bild hinzubekommen, so dass man es auch wieder erkennen kann.
von daher, hängt deine komprimierung auch immer von der semantik ab. denn IMHO hat nicht jeder mensch das auge eines elektronenmikroskops...
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!