Willkommen in Manus Zeitforum
InformationenAnmelden Registrieren

Erweiterte Suche

Einzigartiger Komprimierungsalgorithmus

Thema erstellt von Manu 
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Hallo Mike,

Kryptographie meint eigentlich das Verschlüsslen von Nachrichten, so daß sie nicht jeder lesen kann. (Autorisierung durch Schlüssel)

Ein zur Kryptographie verwandtes Thema ist die Authentifizierung von Daten
im einfachsten Fall durch Prüfsummen. Die Verwandtschaft zur Kryptographie ergibt sich
aus der Notwendigkeit, daß die Erzeugung der Prüfsumme anonym sein muß, d.h. daß sie
sich nicht fälschen läßt und damit
1. der Autor der Nachricht identifiziert wird und
2. die Korrektheit des Inhalts der Nachricht garantiert wird.


Datenkompression versucht, Daten möglichst kompakt darzustellen.

Hufman-Kodierung ist ein wesentlicher generischer Schritt für die Datenkompression,
mögliche Optimierungen sind
1.) der Level (Prediktion durch bedingte Verteilung)
2.) Dynamisches Modell
durch Adaption des Hufman-Baumes oder
Verwenden mehrerer Hufman-Bäume
3.) Vorverarbeiten von Daten z.B. durch
Delta-Kodierung (z.B. mnpg) oder
Längenkodierung (pcx)

Das sind wesentlich die Schritte, die in der Musterlösung zum obigen Wettbewerb angewendet wurden.

zu 2.) Z.B. die ZIP-Library detektiert, ob ein Datenstring aus Text besteht und wendet in entspr. Sequenzen einen dafür optimierten Kodierer an, insgesamt gibt es eine handvoll Kodier-Algorithmen innerhalb der ZIP-Library, von denen die optimale angewendet wird.

lg
Thomas

http://de.wikipedia.org/wiki/Entropiekodierung
Signatur:
Ich bin begeistert!
[Gäste dürfen nur lesen]
Beiträge: 8, Mitglied seit 14 Jahren
Oh, so eine schnelle antwort hätte ich nicht erwartet!

Ich hab wohl den übergang vom thema kryptographie zur kompression übersprungen in meinem beitrag. Das kommt davon wenn man eine ursprünglich lange einleitung auf eine kürzere reduziert.
(verlustbehaftete komprimierung :)

Verschiedene alogorithmen... gerade das stört mich so an der sache. Ich habe schon viel zeit damit verbracht, mir über dinge wie diesen gedanken zu machen und hatte nicht selten ideen, die nicht nur für mich eine kleine sensation waren...
(Kann mich noch gut erinnern als mir mit 12 jahren, in einer schlaflosen nacht mal so langweilig war, dass mir plötzlich eine formel zur berechnung der kugel-anzahl in einem dreieck mit x-kugeln seitenlänge einfiel. Oder wie mein damaliger schwager zu mir sagte ich schaffe es nicht ein programm zu schreiben, mit dem man geometrisch zeichnen kann und dann eine richtige perspektifische vorschau erhält... nach einem halben jahr tüfteln und dem film contact hatte ich die lösung)

Ich will eigentlich nur sagen, dass falls es noch jemanden gibt, der sich gerne solche gedanken macht und sich zufällig gerade mit diesem thema beschäftigen will, dann wär es interessant dessen gedankengänge dazu zu hören :)

mfg
Signatur:
"Wenn die Macht der Liebe die Liebe zur Macht übersteigt, erst dann wird die
Welt endlich wissen, was Frieden heißt."
[Gäste dürfen nur lesen]
Beiträge: 8, Mitglied seit 14 Jahren
Hab da einen versuch angestellt, eine datei so aufzubereiten, dass sie anhand des Huffman-Verfahrens leichter zu komprimieren ist...
Meine idee war dass ich bytes im datenstrom durch andere ersetze, die ab einem gewissen zeitpunkt nicht mehr im strom vorkommen.

Zuerst brauch ich mal eine liste mit 256 einträgen, in der jeder eintrag für die position des jeweiligen bytes steht, an der es das letzte mal in der datei vorkommt.
Beim schreiben/aufbereiten wird das original erst einmal solange kopiert, bis die erste stelle erreicht ist, an der ein byte "ausläuft".
Dieses byte wird jetzt zur "maske" und ersetzt jetzt das byte, das als nächstes "ausläuft".
Wenn das ersetzte byte ausgelaufen ist, wird das nächst auslaufende byte durch die maske ersetzt usw...

Einige punkte sind dabei zu beachten:
- Im schlimmsten fall kommt ein byte erst an der (datenstrom-länge - 256)ten stelle vor...
- Um den strom wieder ins original bringen zu können, muss die liste der "auslaufpositionen" der einzelnen bytes am anfang der datei angehängt werden.
- Normalerweise wird die länge einer datei mit 64 bit angegeben. Das würde bedeuten, mit jedem glättungsschritt würde die datei um (256 * 64 / 8) = 2KB wachsen

Ich habe das ganze ausprobiert und eine 1MB datei so lange geglättet, bis sie 2MB groß war...
Vorher kam jedes Byte ungefähr gleich oft vor, danach kam das byte "00000000" fast 350.000 mal vor, einige andere zwischen 10.000 und 50.000 mal und der rest zwischen 100 und 500 mal...
Wenn ich beide datein komprimire, dann komme ich auf das ergebnis, dass die ursprünglich 2MB große datei gerade mal 24KB größer ist als die ursprünglich 1MB große.

Ich werd mal testen was passiert, wenn ich statt 64bit zahlen 32bit für den kopf der datei verwende, dann könnten zwar nur noch ca 2GB große datein mit dem verfahren geglättet werden, aber das ergebnis wäre ca. doppelt so gut.

Ich weiß, das ist nicht gerade ein erfolg, ich will damit nur mal beweisen, dass die herkömmlichen komprimierungsverfahren ganz und gar nicht das maximum an möglicher effiktivität nutzen.
Ach ja... das glätten der datei dauerte ca. 5min. obwohl ich den code noch nicht mal optimiert hatte... mit der zeit stets also gar nicht mal so schlecht.
Signatur:
"Wenn die Macht der Liebe die Liebe zur Macht übersteigt, erst dann wird die
Welt endlich wissen, was Frieden heißt."
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Hallo Mike,

DesertMemphis schrieb in Beitrag Nr. 692-24:
Verschiedene alogorithmen... gerade das stört mich so an der sache ...

zur Repräsentation von Information werden syntaktische Regeln verwendet.
Abhängig von der Repräsentation ändern sich notwendig die Verteilungen im Hufman-Baum.
Und jede Sprache hat ihre eigene Syntax/Grammatik/Repräsentation.
Daran läßt sich wahrscheinlich nichts ändern,
das ist das Babelfish-Problem.

/OT
Natürlich schreibt sich der Mann "Huffman",
hatte im Hinterkopf immer den Hufschmid
aus "Königreich der Himmel"
OT/

lg
Thomas

Signatur:
Ich bin begeistert!
Beitrag zuletzt bearbeitet von Thomas der Große am 15.10.2009 um 10:04 Uhr.
[Gäste dürfen nur lesen]
Beiträge: 8, Mitglied seit 14 Jahren
Hab erst vor kurzem zig seiten über Huffman gelesen, deshalb war ich mir da sicher ;)

Thomas der Große schrieb in Beitrag Nr. 692-26:
Und jede Sprache hat ihre eigene Syntax/Grammatik/Repräsentation...

Ja... und deshalb verschiedene verfahren für verschiedene grundmuster (jgep, mpeg, ...)
Ich denke jedoch, dass man vlt. trotzdem eine möglichkeit finden kann datenströme unabhängig ihres ursprungs verlustfrei in einer kürzeren form darzustellen...
Ich bin nun mal ein fan der theorie, dass nichts unmöglich ist, solange es nicht an vorstellungskraft mangelt.

Im moment habe ich noch genug zeitlichen freiraum um mir über diese scheinbar hoffnungslose sache gedanken zu machen und bin immer noch nicht davon überzeugt, dass es nicht möglich ist...
Fürs erste unabhängig von der dafür benötigten zeit, denn wenn mal eine grundidee da ist lässt sie sich meistens optimieren...

Ich spiele gerade mit überlegungen inwiefern man von einem x beliebigen byte auf ein anderes x beliebiges schlüsse ziehen kann...
also wieviel könnte byte nr.1 über byte nr.2 verraten...
oder wieviel information braucht man mindestens um von byte nr.1 auf byte nr.2 schliessen zu können...

wenn es möglich wäre eine zufällige anordnung von bytes so zu transformieren, dass die ergebnis bytes möglichst gering in ihren werten (also nicht in ihrer anzahl) sind... oder dass die wertunterschiede zwischen den einzelnen möglichst gering sind...

...grübel, grübel... :)
Signatur:
"Wenn die Macht der Liebe die Liebe zur Macht übersteigt, erst dann wird die
Welt endlich wissen, was Frieden heißt."
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Hallo Manu,

jetzt hab' ich mir mal alle Beiträge durchgeschaut.

1.) Timeouts Beitrag-Nr. 692-7 mit den ISBN-Nummern zeigt, daß man bei Komprimierung im engeren Sinn annimt, daß öffentliche Information/Datenbanken nicht verfügbar sind.
Mit der Referenz http://www.wasistzeit.de/zeitforum hat man grundsätzlich alle Beiträge des Zeitforums, aber eben nicht standalone.

Beitrag-Nr. 692-9 vo Kampf-Sushi drückt das Prinzip aus.

2.) Beitrag-Nr. 692-14: Für die Aussage, daß in Pi alle Ziffernfolgen vorkommen, ist mir kein Nachweis bekannt, nur daß die Ziffern gleichverteilt seien.
Unabhängig davon kann man mit einem Permutations-Generator so eine Zahl konstruieren. Und genau dann sieht man, daß die Referenzierung einer Ziffernfolge genauso umfangreich ist, wie die Zifferfolge selbst.
Das bringt nichts!

3.) Die minimale Repräsentation von Information wird genau durch die Freiheitsgrade beschrieben, die man sich vor Konstruktion der Information offen läßt und sie wird erreicht, wenn man all das Vorwissen mit einfliessen läßt.
Dein Ansatz in Beitrag-Nr. 692-10, einen spezifischen Huffman-Baum mitabzuspeichern, entpricht dem wesentlich. Wieviel Baum optimal ist, hängt von den konkreten Daten ab.

lg
Thomas
Signatur:
Ich bin begeistert!
[Gäste dürfen nur lesen]
avatar
Manu (Administrator) https://wasistzeit.de
Beiträge: 715, Mitglied seit 19 Jahren
Hallo Thomas und alle anderen,

genau das ist das Problem bei der Sache.

In anderen Worten (um es allgemein etwas verständlicher zu sagen):
Wir haben also beispielsweise diese Zahl Pi. Also eine beliebige theoretisch unendlich lange Folge an Informationen. Jede Kombinationsmöglichkeit einer beliebigen Zahlenreihe kommt an irgend einer bestimmten Stelle in Pi vor. Um eine Zahlenreihe zu komprimieren, müssten wir nur die Position angeben, an der diese in Pi vorkommt.

Das Problem:
Je umfangreicher die zu komprimierende Zahlenfolge ist, desto unwahrscheinlicher ihr Vorkommen in Pi. Umso umfangreicher fällt also die Positionsangabe aus. Dazu kommt, dass Pi keine für unser Verfahren optimierte Zahl ist. Deshalb wiederholen sich kleinere und größere Zahlenfolgen systemlos in unregelmäßigen Abständen in ihr selbst. Somit ist die Wahrscheinlichkeit, dass unsere zu komprimierende Zahlenfolge durch Angabe ihrer Position in Pi weniger Information benötigt, deutlich niedriger als 50% und wird exponentiell niedriger, je länger die Zahlenfolge ist.

Ich hoffe, das hat so wirklich jeder verstanden.

DesertMemphis schrieb in Beitrag Nr. 692-22:
...nimm die zahl x die logik y und das ergebnis sind z bit aus dem originalstrom... schön wärs ;)

Das war auch mein ursprünglicher Gedanke. Der Versuch, den ultimativen universell einsetzbaren Algorithmus zu finden, gleicht wohl dem der durch unsere Vorfahren vergeblich stattgefundenen Experimente mit Perpetuum Mobiles.

DesertMemphis schrieb in Beitrag Nr. 692-22:
Ich habe mir zur stütze ein programm geschrieben, das mir die bytefolge einer datei als grafik zeigt ...
Vielleicht kann ich das programm mal als link reinstellen.. mal sehen ob sich noch mal jemand meldet hier...
Wenn du möchtest, schicke es mir einfach per E-Mail und ich biete es in diesem Thread zum Download an.
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Hallo Manu,

das mit der Zahl Pi als Lookup-Table geht wahrscheinlich gar nicht, weil nicht bewiesen ist, daß alle Ziffernkombinationen irgendwann darin vorkommen.

Wenn man eine Ziffernfolge der Länge n kodieren will, liegen idealerweise alle möglichen Kombinationen von n Ziffern in der Lookup-Table hintereinander, das sind n*10n Ziffern, der Index für die konkrete Ziffernfolge wäre in 1...10n.

Um diesen Index darzustellen braucht man gerade wieder n Ziffern. Der Kompressionfaktor ist 1.

lg
Thomas

Signatur:
Ich bin begeistert!
Beitrag zuletzt bearbeitet von Thomas der Große am 15.10.2009 um 22:00 Uhr.
[Gäste dürfen nur lesen]
Beiträge: 8, Mitglied seit 14 Jahren
Thomas der Große schrieb in Beitrag Nr. 692-30:
Wenn man eine Ziffernfolge der Länge n kodieren will, liegen idealerweise alle möglichen Kombinationen von n Ziffern in der Lookup-Table hintereinander, das sind n*10n Ziffern, der Index für die konkrete Ziffernfolge wäre in 1...10n.

Um diesen Index darzustellen braucht man gerade wieder n Ziffern. Der Kompressionfaktor ist 1.

Genau das ist der punkt an dem fast all meine überlegungen und ideen für mögliche lösungen zusammenlaufen...
Der binärcode nutzt jede einzelne kombination von x-bits - um also eine information zu verkürzen, bleibt nur die möglichkeit eventuelle redundanzen zu verringern.

Ich wünschte ich läge mit folgendem gedanken falsch, aber der versuch eine logik zu finden, anhand derer man eine sagen wir xbeliebige 7-bit-folge zu einer 8-bit-folge transformieren könnte ist zum scheitern verurteilt:

mit 1, 2, 3, 4, 5, 6, 7, 8 bit kann man ja jeweils 2, 4, 6, 8, 16, 32, 64, 128, 256 verschiedene werte darstellen.
selbst wenn man das ganze in algorithmen verpackt, sagen wir die erste x-bit-folge mal der zweiten y-bit-folge ergibt z-bit.
Wenn x 4bit wären und y 3bit, dann könnte man aus ihnen nur 16 * 8 = 128 verschiedene ergebnisse erhalten, was wiederum genau 7bit (4+3) sind...
Mit reinem um rechnen kann man meiner meinung nach also bistimmt niemals auf ein gewünschtes ergebnis kommen, da muss schon mehr information einfließen, die aber keinen zusätzlichen speicherplatz benötigt.

zum beisspiel der index des aktuell gelesenen bits in der datei, oder die gesamtlänge der datei... oder oder oder...

bleibt also zu überlegen, wieviel information steckt wirklich in einer datei?
Signatur:
"Wenn die Macht der Liebe die Liebe zur Macht übersteigt, erst dann wird die
Welt endlich wissen, was Frieden heißt."
[Gäste dürfen nur lesen]
avatar
Manu (Administrator) https://wasistzeit.de
Beiträge: 715, Mitglied seit 19 Jahren
DesertMemphis schrieb in Beitrag Nr. 692-22:
Ich habe mir zur stütze ein programm geschrieben, das mir die bytefolge einer datei als grafik zeigt... Der wert des gerade eingelesenen bytes gibt mir eine y koordinate und die position im datenstrom die x koordinate eines punktes in der grafik... die muster die dabei enstehen sind bei den meisten datein erstaunlich!!! eigentlich hätte ich mir großteils "weißes rauschen" erwartet, aber das gegenteil ist eher der fall! Es ergeben sich bei fast allen datein schon fast künstlerische muster! -ok, ihr dürft mich nach dieser aussage für verrückt halten-
Bei bereits komprimierten datein ist dann, wie erwartet fast nur mehr weißes rauschen zu sehen.
(Vielleicht kann ich das programm mal als link reinstellen.. mal sehen ob sich noch mal jemand meldet hier...)

Und hier könnt ihr das Progrämmchen bei Interesse herunterladen. Mit dem Herunterladen der Datei erklärt ihr euch einverstanden, das Risiko für evtl. entstehende Schäden die durch das Herunterladen oder Ausführen des Programms verursacht werden, selbst zu tragen.

DOWNLOAD BITANALYSER.EXE 12,5 Kb

P.S.: War nicht die Rede von einem "Byte-Analyser"? ;-)
[Gäste dürfen nur lesen]
Beiträge: 8, Mitglied seit 14 Jahren
Danke fürs reinstellen!

Hatte heute wieder so eine Idee und auf der Suche nach vielleicht schon bekannten ähnlichen Verfahren bin ich über
den "Lempel-Ziv-Welch-Algorithmus" gestossen...

Der wurde hier noch nicht erwähnt glaub ich, ist aber zu interessant um es dabei zu belassen.
(Bei wiki ist eine recht gute erklärung zu finden)

Es arbeitet wie andere Algorithmen (z.B. zur Text-Komprimierung) mit einem Alphabeth bzw. einer Liste von häufig vorkommenden Zeichenkombinationen. Diese werden dann nur mehr als Index abgespeichert, welcher die Position in der Liste angibt.

Das Besondere:
Diese Liste wird nicht mit den komprimierten Daten abgespeichert.
Dank der genialen Logik kann sie beim Einlesen der zu entpackenden Daten rekonstruiert werden.

Eingesetzt wird der Algorithmus z.B. beim *.gif Format.

Die Schäche:
Der Algorithmus ist nur dann effektiv, wenn gewisse bit-Folgen häufiger vorkommen.

Vielleicht bringt das den einen oder anderen ja auf neue Ideen :)

...
Signatur:
"Wenn die Macht der Liebe die Liebe zur Macht übersteigt, erst dann wird die
Welt endlich wissen, was Frieden heißt."
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Hallo zusammen,

bei meinen Experimenten mit Datenkompressoren kam es vor, dass die Dekodierer-Implementierung einen kleinen Fehler hatte, das Ergebnis waren aber deutschklingende Wörter.
Das führte mich zu einem Gedankenexperiment, mit dem man subjetives und objektives Verstehen hart trennen kann.


Man stelle sich vor, man habe zwei perfekte Datenkompressionsalgorithmen "A" und "B". Jeder von ihnen erzeugt aus einer Nachricht notwendig eine gleichverteilte und unabhängige Folgen von 0-en und 1-en. Mit den Eigenschaften Gleichverteilung und Unabhängigkeit folgt, dass jede Kombination von 0/1-Ziffern im kodierten Text vorkommen können muss. Daraus folgt für die zugehörigen Dekodierer "A-1" und "B-1", dass sie jede Bitfolge sinnvoll interpretieren können.

Wenn man eine Folge (an) von Nachrichten mit Kodierer A komprimiert und anschliessend mit Dekordierer B-1 dekomprimiert, müsste das Ergebnis eine sinnvolle Folge von Nachrichten (bm) in der Sprache B sein.

Konsequenzen:
* Man kann mit einem Dekodierer A-1 und einem echten Zufallsgenerator beliebig viel Information Erzeugen.
* Die informationtheoretischen Überlegungen von v. Neumann zur Entropie sind wahrscheinlich falsch, weil er annahm, dass im weissen Rauschen keine Information steckt.
* Man kann jede Sprache, von der man alle ihre grammatischen und semantischen Aspekte erfasst hat, in jede andere verstandene Sprache übersetzen
* Aus der Erfahrung, dass man keinen perfekten Komprimierer gefunden hat, kann man ableiten, dass man die Gesetze, die hinter der Information stehen nicht wirklich verstanden hat.

lg
Thomas
Signatur:
Ich bin begeistert!
Beitrag zuletzt bearbeitet von Thomas der Große am 13.11.2012 um 01:23 Uhr.
[Gäste dürfen nur lesen]
Beiträge: 5, Mitglied seit 12 Jahren
Hallo Leute.

Ich hab grad mit erstaunen diesen Thread gefunden! Das sind viele Ideen, die ich auch schon hatte.
Seit ca. 10 Jahren (anfang 2002) hatte ich die Idee für einen Komprimierungsverfahren. Es hat auch theoretisch funktioniert (auf Papier). Ein kleines Tool geschrieben, hat auch funktioniert aber nicht so, wie ich es mir gewünscht hatte.
Zumindest hab ich aus ner 1MB Zip-Datei nochmal ca. 2KB rausgeholt.
Meine überlegung war eben auch, nicht die Bytes sondern das Muster der Bits an zu schauen.
Wenn man jetzt einen Algorythmus findet, der in dem Rauschen Muster finden kann, dann sollte die Datei eigentlich von 1GB auf 1MB zu komprimieren sein (grobe schätzung! Bitte nicht drauf rumreiten). Wenn die Datei dann mit so einem Muster verkleinert wurde, muss man die Bauanleitung (also das Muster) wieder mit in die Datei schreiben. Dann nochmal komprimieren. Und nochmal, und nochmal....
Da ich nie einen richtigen Algo zum Mustererkennen geschafft habe (wie gesagt, auf dem Papier mit der Menschlichen mustererkennung hats geklappt) hab ich das Projekt dann 4 Jahre ruhen lassen und jetzt wieder ausgegraben. Leider war nur noch die Idee zum ausgraben, da im laufe der Zeit mein Tool verschwunden ist :'-(

Jetzt die Frage, kennt jemand einen Algo, der Muster in einem Rauschen erkennen kann?

Ich will nur so einen Algo. Wenn Ihr gleich anfängt mit "des klappt ned" dann stört mich des nicht, ich will es versuchen! Ich denk seit 10 Jahren drüber nach, ich muss es probieren! Wenns dann ned geht, ok, aber ich geb ned vorher auf!

Gruß
Nasty
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Nasty schrieb in Beitrag Nr. 692-35:
Zumindest hab ich aus ner 1MB Zip-Datei nochmal ca. 2KB rausgeholt.

Sei gegrüßt Nasty,

das heißt Du warst auf dem richtigen Weg.

Zitat:
Meine überlegung war eben auch, nicht die Bytes sondern das Muster der Bits an zu schauen.
Es gibt da nichts zu verschenken.

Zitat:
Wenn man jetzt einen Algorythmus findet, der in dem Rauschen Muster finden kann, dann sollte die Datei eigentlich von 1GB auf 1MB zu komprimieren sein (grobe schätzung!
Irgendwo könnte ich einen Intuition haben, die mir sagt, was das heißt: "Im Rauschen Muster finden und damit beliebige Kompressionsfaktoren erreichen".
Man kann im "weißen" Rauschen beliebig viele Muster finden. Die Frage ist, ob sie der Kompression von Nachrichten dienlich sind. Vom Konzept der Hufman-Kodierung her hat man die Konkurrenz von "vielen Mustern", die die Code-Wörter länger machen und der Informationsmenge, die man mit einem Code-Wort damit darstellt.
Mit der Annahme der Akausalität der Nachrichten-Elemente leitet die Informationstheorie eine Prinzipielle Grenze der Kompressionrate ab.

Zitat:
Jetzt die Frage, kennt jemand einen Algo, der Muster in einem Rauschen erkennen kann?
Ich will nur so einen Algo.
Schlage vor Korellations-Statisitken, eben das Grundprinzip des Data-Mining.
Z.B. Man betrachtet Zeichen- oder Bit-Folgen und zählt, wie oft die Vorkommen.
Man definiert, wann eine Korellation signifikant ist. Hinsichtlich der Datenkompression dürfte das Kriterium sein: "Welche Kompression wird durch die Substitution der unkomprimierten Information durch das Muster erreicht?"

Gruß
Thomas
Signatur:
Ich bin begeistert!
[Gäste dürfen nur lesen]
Beiträge: 5, Mitglied seit 12 Jahren
Hallo Thomas,

ich glaube, wir meinen was anderes mit "Muster".
Ich gehe davon aus, dass es ein Algo schafft herauszufinden, wann wo wie Bits gesetzt sind.
Man nimmt eine Datei, davon die ersten (die Optimale größe hängt vom Algo ab) 10KB, schiebt die in den Algo und der liefert dann: 123,1, 10,1, 15,0, 3,0, 7,1, 5,0
d.H Position 123 is ne 1, dann das 10te is ne 1, das 15te eine 0 ...... das 5te eine 0. Dann wiederholt sich das ganze ausser die Startposition (123), also wieder das 10te is ne 1.

Am Anfang hab ich immer nur nach 0 oder 1 gesucht. Beim Umwandeln in Bit hab ich gezählt, was öffter vorkommt und dann der Regel nur gesagt, gugg nach nullen.

Alle diese getroffenen Bits werden gelöscht und alle anderen rücken auf.
Diese "Regel" die dann als Ergebnis kommt, schreibt man vorne an diesen Dateiblock dran und nimmt den nächsten 10KB Block.
Der wird nach der bearbeitung an den ersten dran gehängt. Das ganze geht dann, bis man mit der Datei fertig ist.

Danach, fängt man mit der Datei wieder von vorne an. Die ganzen Regeln stehen ja an den einzelnen Blöcken drinnen und werden im 2. Schritt mit Komprimiert.

Ums Entpacken braucht Ihr euch keine Sorgen machen, das funktioniert bereits! ;-)

Die Regel darf halt nur (muss man halt schauen was sinnvoll is) 6 Werte haben, sonst weiß man nimmer, wo die Daten anfangen.
Also man nimmt die Regel und führt die aus. Man schreibt so lange die Bits nach der Regel in die Vorhandene Datei, bis ein fertiger 10KB Block existiert. Dann geht das ganze einfach da weiter. Jetzt muss ne Regel kommen, dann Daten, .....

Wie gesagt, entpacken kein stress. Packen eigentlich auch ned, wenn ich nur nen Algo (er)finden würde, der mir solche Regeln auswerfen kann.

Wenn jmd fragen hat, einfach melden. Ich bin mir ned sicher, ob ich des für euch verständlich erklärt habe. Für mich klingts einleuchtend ;-)

grüße
Nasty
[Gäste dürfen nur lesen]
Beiträge: 5, Mitglied seit 12 Jahren
Vielleicht doch noch:


'X'O'X''X'OXOOXOOXOXXOOXOXXOOOXXO
O'X'O'X''X'OXOOXOOXOXXOOXOXXOOOXX
XO'X'O'X''X'OXOOXOOXOXXOOXOXXOOOX
XXO'X'O'X''X'OXOOXOOXOXXOOXOXXOOO
XOOO'X'O'X''X'OXOOXOOXOXXOOXOXXOO

ganz vereinfacht.
An Position 1 is X, Dann jedes 2. ist ein X Dann jedes erste ein X dann (ich überspring hier einfach mal) Dann jedes 25. is ein X
also Regel 1,X 2,X 1,X 25,X

komprimiert dann (nur mal die erste Zeile):
Regel, OOXOOXOOXOXXOOXOXXOOOXXO (also ohne die 3 Xe, die die Regel gefunden hat)

Jetzt muss halt so mehr gefunden werden, als die Regel speicher kostet.

Jetzt verständlicher?
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Nasty schrieb in Beitrag Nr. 692-38:
Jetzt verständlicher?
Nein! Was ist Dein Alphabet, was machen die Quotes? Deine Zählung ist auch nicht klar.

lg
Thomas
Signatur:
Ich bin begeistert!
[Gäste dürfen nur lesen]
Beiträge: 5, Mitglied seit 12 Jahren
Die X und O stehen für Bits mit wert 1 oder 0 (such dir aus welches was ist ;-) )
die Quotes sollten die vom Algo getroffenen Bits Symbolisieren ('X' = getroffenes Bit)
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.729, Mitglied seit 16 Jahren
Hallo Nasty,

vermute Du machst eine Längenkodierung der X-Abstände.
Wenn Du einen gleichverteilten Binärstring z.B. "XOOXXXOXOXOXX..." kodierst,
dann hast Du die Längen-Verteilung

1 --> 1/2
2 --> 1/4
3 --> 1/8
...
n --> 2-n

Ein Konstanter String "XXXXXXXXXX"
hat die Längenkodierung 1,1,1,1,1,1,1,1,1,1
also genau 10 Bit

Ein alternierender String "OXOXOXOXOX"
hat die Längenkodierung 2,2,2,2,2
Für die Kodierung der 2en brauchst Du aber je 2 Bit, weil ihre Wahrscheinlichkeit 1/4 ist
insgesamt wieder 10 Bit.

Mit Kombinatorik kann man zeigen, dass die Längenkodierung für gleichverteilte Binärstrings nichts hergibt.

Gewinnen kannst Du dabei nur, wenn ausgezeichnete Längen häufig vorkommen.

lg
Thomas

Signatur:
Ich bin begeistert!
Beitrag zuletzt bearbeitet von Thomas der Große am 08.09.2011 um 01:00 Uhr.
[Gäste dürfen nur lesen]
Beiträge: 8, Mitglied seit 14 Jahren
Hallo liebe Gedankensportler!

Freut mich, dass es nach so langer Zeit immer noch Begeisterung für dieses Thema gibt :)
Meine wurde zwar etwas gezähmt/abgelenkt/überblendet, aber in Ruhe gelassen hat mich dieses Kapitel noch immer nicht.

Zu Nasty's Idee:

Ich dachte mir auch öfters, dass die Unterteilung einer Datei, in Blöcke mit bekannter Größe, und deren Komprimierung, mit Hilfe von Mustererkennung, Erfolgversprechend klingt.
Ich hab mir erlaubt deinen Vorschlag für eine Mustererkennung abzuändern und einen stark vereinfachten Versuch angestellt...

---Original--- (10 Bit Block der original Datei)
1101011010

---Kodierung---
Schritt 1: index5 = 0 (Jedes 5te Bit war eine 0)
11011101

Schritt 2: index2 = 1
1010

Schritt 3: index2 = 0
11

Schritt 4: start = 1

Ergebnis der Kodierung:
1 (2)0 (2)1 (5)0
bzw.
1 (010)0 (010)1 (101)0 = 1010001011010

---Decodierung---

Schritt 1: start = 1 index2 = 0 (Blocklänge bekannt)
1010101010 ...1010101010

Schritt 2: index2 = 1
1101110111 ...011101110111011101110111011101

Schritt 3: index5 = 0
1101011010 ...1101011010110101101011010110101101011010

Ende Decodierung:
1101011010


Die Idee dahinter gefällt mir recht gut, jedoch gibt es einige ungeklärte Dinge:

- Wie wird die Bitlänge der "index"-Information bestimmt?
(schnell überlegt: Index-Maximum = Länge eines Blocks = 10 = 3Bit)

- Wie werden in der Output Datei die einzelnen Blöcke unterschieden, wenn die Bitlänge eines Codierten Blocks variiert?
1(010)0(010)1(101)0 ? Block2 ? Block3 ? ...
(Im Falle dieses Versuchs könnten die Abschnitte "?" mit (111) gekennzeichnet sein, da der Index niemals diesen Wert haben wird)

- Woraus könnte man die Effektivität der Komprimierung errechnen?
Und genau hier steh ich noch an.

Vielleicht mache ich noch ein paar Versuche mit verschiedenen Blockgrößen, wobei ich erst noch an der Mustererkennung feilen müsste, welche übrigens gar nicht so kompliziert ist:

...i = Blocklänge
...Solange i größer als 1 ist, überprüfe Block auf durchgehende Abfolge von 1 bzw. 0 in "i" Abständen.
...Wenn Abfolge vorhanden, merken(Info ausgeben) und Abfolge aus Block entfernen.
...i = i - 1, Schleife wiederholen.

Tja... und das wars auch erst einmal schon wieder...


Ich würde an dieser Stelle nur noch gerne etwas klarstellen:

Ein Kollege aus dem Kurs, an dem ich ich damals teilgenommen hatte, während ich meine ersten Beiträge zu diesem Thema schrieb, meinte er müsse mich belehren, was meine Auffassung von Respekt betrifft...

Seiner Meinung nach sei es von mir unverschämt hier in diesem Vorum meine Ansichten von mir zu geben...
Ich hätte nicht das Neiveau und was sonst noch, um auch nur im geringsten etwas beitragen zu können, was von Interesse wäre...

Nicht dass ich seinen Worten große Beachtung schenke... denoch... sollten meine Beiträge hier als störend empfunden werden, dann soll das bitte jemand ehrlich und ohne Scheu zur Kenntnis geben! Danke :)

Grüß euch

Signatur:
"Wenn die Macht der Liebe die Liebe zur Macht übersteigt, erst dann wird die
Welt endlich wissen, was Frieden heißt."
Beitrag zuletzt bearbeitet von DesertMemphis am 06.10.2011 um 11:42 Uhr.
[Gäste dürfen nur lesen]
In diesem Forum dürfen nur Mitglieder schreiben. Hier kannst du dich anmelden
Zum Seitenanfang Nach oben