Autor |
Beitrag |
fuggaz
      
Beiträge: 106
|
Verfasst: Fr 15.02.08 23:02
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
|
|
AXMD
      
Beiträge: 4006
Erhaltene Danke: 7
Windows 10 64 bit
C# (Visual Studio 2019 Express)
|
Verfasst: Fr 15.02.08 23:14
Schau dir mal die Wikipedia-Artikel zum Thema Informationsgehalt und Entropie
Das beantwortet deine Frage zwar nicht direkt, aber die beiden Artikel erklären dir (indirekt), warum es keine perfektes Kompressionsverfahren geben kann.
AXMD
|
|
fuggaz 
      
Beiträge: 106
|
Verfasst: 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;)
Oder dem Wissen der Nichtexistenz des Beweises der Nichtexistenz...^^
|
|
AXMD
      
Beiträge: 4006
Erhaltene Danke: 7
Windows 10 64 bit
C# (Visual Studio 2019 Express)
|
Verfasst: 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 
      
Beiträge: 106
|
Verfasst: Sa 16.02.08 00:26
Exakt, wie oft kommt das schon vor.
Ja ich werde das wohl so auch schreiben.
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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.
_________________ Na denn, dann. Bis dann, denn.
|
|
fuggaz 
      
Beiträge: 106
|
Verfasst: 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
      
Beiträge: 1098
Erhaltene Danke: 13
Win7 geg. WInXP oder sogar Win98
Rad2007
|
Verfasst: 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
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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.
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'...
_________________ Na denn, dann. Bis dann, denn.
|
|
Gausi
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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?)
_________________ We are, we were and will not be.
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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 
      
Beiträge: 106
|
Verfasst: 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
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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
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.
_________________ Na denn, dann. Bis dann, denn.
|
|
tommie-lie
      
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: 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 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.
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
Hidden
      
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: 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
|
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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.
Zuletzt bearbeitet von delfiphan am So 17.02.08 00:12, insgesamt 1-mal bearbeitet
|
|
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: 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
      
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: 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.
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: 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.
|
|
|