Entwickler-Ecke :: Thema anzeigen - Mit Großen Zahlen arbeiten: 9*10^100

mimi - Sa 02.04.05 19:51
Titel: Mit Großen Zahlen arbeiten: 9*10^100

Hallo,
ich habe ein problem:
wie kann ich zahlen teilen die z.b. über
9*10^100 stellen haben kann ?
und diese zahle möchte ich dann durch die anzhal-1 der stellen teilen.

der Hintergrund ist folgender:
ich möchte ein eigens packformat schreiben womit man 500 MB auf ca 1 MB komprimieren kann.
Wie ?
Ich öffne eine Datei ermittle mir die Asscicode packe sie zu einer langen kette zusammen und teile diese durch die anzahl -1 und zu wiederherrstellen nehme ich einfach die das ergbnis dieser teilung was ich in einer Dateischreibe und nehme dies mal die anzhal und erhalte so die Asccicode Kette als trennzeichen nehme ich einfach eine zahl die nicht vorkommen kann in diese kette wie z.b. 300. Proble sind nur:
1. Das erstellen dieser Kette würde stunden dauern
2. Das Teilen und das Mal nehmen
dann könnte man noch die datei vorher einmal mit BZIP2 packen und hitnerher auch noch dann müsste ich eigentlich eine datei haben die sehr klein ist: nach meinen vorstellungen.
so Könnte es aussehn

Zitat:

030077300105300993001143001113001153001113001023001630032300873001053001103001003001113001193001153003230088
300803003230072300111300109300101300323006930010030010530011630010530011130011030013300103001330003006930078
300683006630069300783008530084300903009300823004530076300733009030069300783009030086300693008230084300823006
530071300133001030013300103008730073300673007230084300733007130032300453003230066300733008430084300693003230
079300823007130070300196300763008430073300713003230076300693008330069300783005830032300683001053001013001153
00101300114300323006930011030010030098300101300110300117300116300122300

habe schon mit dem Komprimieren angefangen hier als trennzeichen 300

Moderiert von AXMD: Zeilenumbrüche eingefügt.

uall@ogc - Sa 02.04.05 20:00

mimi nach deiner postanzahl abe ich eigentlich erwartet das du bisl erfahrung hast... die datei kannst du so nicht packen, denn du musst die ja den teiler merken, und das ergebnis

der teiler ist ja nur um 1 byte geschrumpft das ergebnis ist eventl nen dezimalzahl und die kannste net so einfach speichern oO

also lass es lieber bleiben das bringt nix ^^

und zu dem wie man das generell macht
nimm nen record
x,y: cardinal;

dann haste ja 64 bit = zahlen von 0..2^64-1
die veraltung musste dann selbst machen

mimi - Sa 02.04.05 20:19

Zitat:

mimi nach deiner postanzahl abe ich eigentlich erwartet das du bisl erfahrung hast

Leider sagt die Postzahle nicht über die erfahrung aus.

Zitat:

die datei kannst du so nicht packen, denn du musst die ja den teiler merken, und das ergebnis

Ja ich weiß ich dachte mir ich schreibe den Teiler(also die Anzahl der Zahlenkette) in einer Datei und Das ergbnis.
z.b.

50300503004030060300
diese zahle teile ich jetzt durch die anzahl also 20 stellen

hast recht... habst gerade mal getestet ich dachte die anzahl währe kleiner

dann müsste man diese zahl durch:
50300503004030060300 div 5030050300403006030 teilen und das würde nichts bringen

nagut dann müsste man nur den kleinstmöglichen teiler finden z.b. die Hälfte. Aber das umwandeln der Datei in reichen Asscicode komprimiert ja auch schon etwas(bei einer datei die z.b. 74,4 KB groß ist verkleinert er diese auf 5 kb *G*

Backslash - Mo 04.04.05 11:00

Zitat:

ich möchte ein eigens packformat schreiben womit man 500 MB auf ca 1 MB komprimieren kann.

Hallo Mimi,

ich möchte dir ernsthaft anraten, dich zumindest ein Stück weit mit bisher existierenden Verfahren wie BWT, PPM, etc. zu befassen, bevor du daran denkst einen Packalgorithmus dieser Stärke zu entwickeln. Ich find das wirklich interessant, dass immer noch Leute Packraten von 500:1 möglich halten. Nunja so unmöglich ist das ja gar nicht, wenn die Datei viele Lauflängen enthält ;-) Ich habe erst kürzlich selbst einen Thread zu diesem Thema geführt und feststellen müssen wieviel ich an Basiskenntnissen noch nicht hab, obwohl ich mich die letzten 5 Jahre intensiv mit dem Thema beschäftige.

Ich möchte dich nicht entmutigen aber du wirst für diese Problemstellung 500:1 keine Lösung finden. Die Idee mit dem kleinsten gemeinsamen Teiler hatten schon andere. Wie bereits erwähnt würde das Speichern dieses Teilers die Datei im Endeffekt sogar vergrößern.

Zitat:

der teiler ist ja nur um 1 byte geschrumpft das ergebnis ist eventl nen dezimalzahl und die kannste net so einfach speichern oO

Das Ergebnis evtl ne Dezimalzahl??? :gruebel: Die Basis des binären Zahlensytems ist 2. Entweder die Binärzahl ist gerade, dann kann ich durch 2 teilen oder sie ist ungerade, dann kann ich nicht durch 2 teilen. Kleinster gemeinsamer Teiler bedeutet im binären Falle, dass keine Dezimalzahl rauskommt, sonst würd man überhaupt keine Verkleinerung erreichen oder irre ich mich da?. :roll: Die Idee mit dem kleinsten gemeinsamen Teiler hatte ich vor längerer Zeit, als ich ein Verfahren zur verlustfreien Wav-Kompression entwickeln wollte. Hab das schnell aufgegeben, da die Packraten zu niedrig sind.

Wer weiß, vielleicht kommst du mit der Idee ja weiter? :wink:

Ansonsten findest du ein paar Informationen zu vorhandenen Verfahren hier:
http://www.faqs.org/faqs/compression-faq/part1/section-8.html
[url]http://www.data-compression.info[/url]
[url]http://www.datacompression.info[/url]

Dort wirst du sehr viele Links zum Thema 500:1 -Kompression finden. Wenn du dafür ne Lösung findest, dann respekt. Dagegen verblasst mein Algo mit einer minimalen Rate von 0,4 % erheblich :wink:

Viele Grüße

\\ Backslash \\

mimi - Mi 06.04.05 20:28

Zitat:

ch möchte dich nicht entmutigen aber du wirst für diese Problemstellung 500:1 keine Lösung finden. Die Idee mit dem kleinsten gemeinsamen Teiler hatten schon andere. Wie bereits erwähnt würde das Speichern dieses Teilers die Datei im Endeffekt sogar vergrößern.

das dachte ich mir schon,es muss einen hacken geben.
Aber ich glaube ich habe eine lösung gefunden:
ich teile diese AsccicodeKette einfach durch eine sehr kleine zahl und sorgedafür das die , weg kommen, das wird zwar tage dauern, aber es dürfte klappen

Danke für deine antwort, dann bin ich ja nicht der einzigte der diesen Traum hat *G*

mimi - Mi 06.04.05 21:30

Zitat:

Wer weiß, vielleicht kommst du mit der Idee ja weiter? :wink:

bestimmt, ich habe ein zwei ideen wobei die erste noch eine weilie dauern dürfte, weil dort muss ich eine geeignette asccitabbelncode finden und bei der zweiten: naja, dort kannst wenn du z.b. 500 MB packen möchtes tage dauern bis er es dann auf eine zwei stellige zahl gebracht hat und dann muss sie ja auch wieder hergestlelt werden, ich würde sagen das geht nur auf die Rechnern der Zukunpf die 16 Funktionen gleichzeitigausführen können bzw. das es Bool werte gibt mit 16 zustenden(ich weiß nicht wie die rechner geschrieben werden)

Aber ich halte es für machbar, von 4 GB auf 1 KB zu kommmen, es muss nur richtig angepackt werden und das braucht zeit !!!
Danke für die Links die werde ich mir mal ansehen.

Edit: Habe die lings mir angeschaut, sie sind leider alle auf englisch, aber ich werde mich mit diesem Thema noch genauer auseinander setzen !!!

mimi - Do 07.04.05 08:48

Zitat:

4GB -> 1KB ??

wieso kann man dann diese 1KB datei mit dem verfahren nicht wieder komprimieren?
das wäre dann der zweite schritt, oder?

1kb -> 1Byte
meinst du damit weiter komprimieren ?
ja natürlich du hast eine 3000000000000 stellige zahle teilst die dann einfach nur 5 so oft wie es gerade geht und wenn nichts meht geht nimmst du einfach einen andren Teiler bis du eine z stellige zahl hast und dann speicherst du ab, wie oft du nur 1000, duch 5, durch... geteilt hast und kannst die nacher und voher mit zip packen(evtl.)

Problem ist halt nur, es wird sehr sehr sehr lange dauern bis die Pack oder Entpack funtkion fertig ist

mimi - Do 07.04.05 11:50

Zitat:

Oder meinst du mit dem Satz, dass du sehr sehr lange brauchst um die Funtkionen zu schreiben? :wink:

das wird sich noch zeigen. ich dachte mir das jetzt so: ich teile eine sehr große zahl durch eine sehr kleine zahl(könnt ihr mir folgen :D ?) und fertig bis ich aus einer sehr großen zahle eine zwei oder ein stellige zahl habe nur den weg wie ich dahin gekommen bin muss ich in einer datei schreiben z.b. so:
20 X = 30
10 X = 5

das heißt dann:
ich habe die große zahl 30 mal druch 20 geteielt und weil es dann mit 20 nicht mehr ging habe ich 10 genommen und zwar 5 mal das müsste doch klappen oder ?
und beim wiederherstellen der Sehr großen zahl gehe ich genauso vor halt nur *:
ich nehme zuerst 5 * 10 und dann dieses eregbnis also 50 nehme ich 20 mal 30 und so müsste ich auf die zahl kommen die ich voher hatte,oder ist das falsch ? mit kleinen zaheln geht das:

49 / 7 = 7 weil 7 * 7 sind 49 siehe an: ich habe richtig gerechnet *G*
(sollte doch auch mit großen zahlen gehen oder ?)
das wird lustig wenn die funktion fertig ist:
4 GB > 1 KB und brauchst Tage um die daten wiederherzustellen *G*, naja evlt. gibt es sogar einen weg wie ich diese funktion verschnellern könnte mal sehen..... problem sind halt nur diese langen zahlen ketten

mimi - Fr 08.04.05 17:07

Zitat:

wenn du so einen algorithmus erfunden hast, dann sag ich: hut ab! das hat ja noch nicht einmal ein riesiges team geschafft!

darum habe ich ja auch gute chancen.

Ich glaube inwzischen das sich meine idee da nicht umsetzten läst aber wenn wird es Stunden/Tage/Wochen/Jahre dauern bis du eine 4 GB große datei zu 1 KB/ 10 MB gepackt hast :D

mal schauen, aber darum ging es eigentlich nicht, es ging ja nur darum eine sehr große zahl zu verkleinern und dann wiederherrzustellen.... z.b. wenn ich folgende zahl habe:
530063009300530063007300530011300123001330014300153001530016

diese zahl möchte ich genre auf eine 2-3 stellige zahl verkleinern und ich muss sie ja auch wiederherrstellen....
dafür muss es doch möglichkeiten geben, da ich nicht so gut mahte kann und auch nur die 4 Grundrechenarten und % und Dreisatzt kann. Kenne ich diese möglichkeiten leider nicht, aber es muss gehen.

Mit kleinen Zahlen geht das doch auch:
7*7 = 49
49 / 7 = 7

wist ihr was ich meine ?

mimi - Fr 08.04.05 17:25

Zitat:

7*7 müsstest schon 2 bytes haben, die zahl an sich ist zwar kleiner aber zum speichern bruacht du mehrere bytes

naja das war nur ein kleines beispiel, bei den großen zahlen würde ich durch konstante zahlen teilen, aber ich habe auch das gefühl das es nicht geht. Hatte heute mal etwas rumgetestet und habe es nicht geschaft die "alte" zahlenfolge widerrherzustellen. Das ist noch einproblem. Das teilen mag ja noch gehen, aber ich brauche ja die gleiche zahl wider. sons gehen ja daten verloren :(

ich hatte da noch eine andre idee, aber die geht nicht so einfach da habe auch noch keine lösung gefunden, kann sein, das ich in ein paar jahren draufkomme *G*

I.MacLeod - Fr 08.04.05 17:37

@mimi:

Denk mal an folgendes:

in einem byte kannst du 2^8 verschiedene Zahlen speichern, in zwei bytes 2^16, in drei 2^24 usw. Mit anderen Worten: in einem Byte lassen sich genau 256 verschiedene Datensätze / Dateien / irgendwas speichern.

Für 2^n bits heißt das also: 2^n verschiedene Dateien. Wenn du jetzt 2^n bits mit einem Algorithmus garantiert um nur 1 bit verkleinern willst, kannst du nur noch 2^(n-1) verschiedene Dateien darstellen, du "verlierst" also jede zweite Möglichkeit. => RAD-Kompressoren sind unmöglich

mimi - Sa 09.04.05 13:01

habe mich gerade mit meiner RAD kompri... versucht, doch leider ohne erfolgt ich kann jetzt wohl eine zahl z.b.
5456 - 500 nehmen sooft bis es nicht mehr geht aber alleding brauche ich dann die anzahl und das ergbnis und zusmammen ergibt das dann eine 3 stellige zahle die untereinander abgespeichert werden musss oder halt mit einem Trennzeichen.... naja warh aber eine schöne idee fand ich auf jedenfall wie die meisten RAD Komprision....

naja evtl. in paar jahren finde ich einen anderen weg mal sehen....

Backslash - Mo 11.04.05 17:32

Hallo Mimi,

ich wollte dich oben nicht entmutigen. Dein Ehrgeitz in dieser Sache ist durchaus respektwürdig. Ich befasste mich bis vor kurzem mit Folgen von 1 MB - Größe. Da wird es schon einige Generationen dauern, bis irgendwann mal einer alle möglichen Datenfolgen ausgerechnet hat ;-)

Hier mal eine Kleinigkeit, warum man durch den Teilalgorithmus nicht alle Folgen verlustfrei teilen kann: Wenn man die letzte Binärstelle anschaut, so wird es in Bitfolgen der Länge n immer (2^n)/2 gerade und (2^n) / 2 ungerade Folgen geben. Aus dem Grund wird 2 als Teiler nur in 50% der Fälle gehen. In den anderen Fällen musst du auf andere Teiler ausweichen. Dann hast du noch das Problem, selbst wenn du die Datei durchs Teilen von 4 GB auf 1KB runtergeteilt hast, dass du auch noch die Multiplikationsinformationen speichern musst. Die brauchen insgesamt mindestens wieder soviel Informationen wie die ursprüngliche Datei.

Naja, ich wollt das eben nur anmerken, damit du dich nachher nicht zusehr in Bereiche stürzt, die nicht gehen können. Allerdings ist bemerkenswert, dass du mit dem Teileralgo einen zumindest rekursiven Algorithmus gefunden hast für bestimmte Datenfolgen.

Ich denke bei binären Folgen müsste der Teiler pro Divisionsschritt >= 4 sein, damit du überhaupt einen binären Erfolg von mindestens 1 Bit pro Vorgang bekommst. Sehe ich das richtig? War nur ein Denkansatz ohne das jetzt nachzurechnen ;-)

Viele Grüße

\\ Backslash \\

F34r0fTh3D4rk - Di 12.04.05 15:56

ok eigentlich ist es doch möglich, wenn man einen packer schreibt, der den inhalt der datei immer durch die gleiche zahl teilt, meinetwegen, 10mio, dann ist die datei ja kleiner, und damit sie wieder lesbar wird, wird sie wieder mit 10mio multipliziert (bei jemandem, der den gleichen packer hat), und bei der multiplaktion ist dann praktisch die alte datei wiederhergestellt, also hätte jede auch noch so kleine zahl eine dazugehörige datei. natürlich ist es etwas kompliziert, wenn man nachkommastellen hat, aber doch machbar, oder ?

(Bitte nicht hauen :lol: )

Delete - Di 12.04.05 17:33

F34r0fTh3D4rk hat folgendes geschrieben:

Wow du bist ein richtiger profi. :roll:

Gibst erst deinen Senf zu etwas, was du anscheinend nicht vollständig gelesen hast und entwickelst dann eine Idee, die das Hauptthema dieses Threads ist.

Ich fand das Thema von Anfang an nachvollziehbar, aber leider hab ich nicht die Ahnung um zu sagen, ob das klappt.
Jedenfalls fand ich Mimi etwa vorschnell mit seiner Behauptung. Erst ausprobieren, dann Thesen posten, ist meiner Meinung sicherer.

Backslash - Mi 13.04.05 16:50

Zitat:

Schonmal daran gedacht, dass da ein großer Dezimalbruch rauskommen kann? Um es verständlicher zu machen. Wenn du jede Datenfolge jeder x-beliebigen Größe durch 2 oder durch 3 teilst (immer), so wirst du vielleicht eine Verkleinerung bekommen, außerdem auch einen Dezimalbruch bzw. Teilerrest. Man könnte jedoch mit der Modulo-Funktion herausfinden ob eine Datenfolge ohne Rest teilbar ist. Allerdings gibt das immer noch keine Kompression bei Daten, die zum Beispiel aus Zufallsgeneratoren stammen, da die Wahrscheinlichkeit für eine gerade Folge genauso hoch sein sollte wie die für eine ungerade Folge, bzw. deren letzte Stelle 0 oder 1 ist ;-)

mimi - Mi 13.04.05 19:42

Zitat:

dass du mit dem Teileralgo einen zumindest rekursiven Algorithmus gefunden hast für bestimmte Datenfolgen

was meinst du mit "rekursiven Algorithmus" ?
eine sich immer widerholde funktion ?

@F34r0fTh3D4rk
genau davon sprach ist die ganze zeit :shock:

@Backslash
das ist bei meinen verzuchen mit kleinen zahlen rauß gekommen ich habe z.b. ein Programm geschrieben das immer

4000 / 100 = 40
aber bei andren zahlen z.b.

6548 / 100 = 65,48
also wieder 4 zeichen die ich abspeichern muss also bringt das nichts dann dachte ich an - nehmen da war die anzahl zu hoch.

das problem ist meiner ansicht nach wenn ich eine große zahl in 4 schritten duchgehe und die 4 ergbnisse teile bis es nicht mehr geht habe ich wegen der nach kommerzahlen eine zu lange zhal rauß.

aber es war eine schöne idee.
Man müste nur eine möglichkeit finden zahlen ohne koma zu bekommen, dann hätte das verfahrnen bestimmt erfolgt. wobei das verfahren bestimmt lange zeit braucht.

Ich habe in meinen test gesehen das es ca 2-4 minuten dauert eine Asccicode kette zubilden dabei war die datei nur ca 74,4 kb rauß(die eular.txt aus system32 *G*)

Oder seit ihr anderansicht ? das problem ist ja wie schon gesagt: bei ungeraden zahlen.

edit:
evlt. kann man ja ein eigenen zufalls generatur entwickeln wenn ich bei Random immer den gleichen start werde angebne bekomme ich immer den gleichen zahlen folge rauß.... vileicht kann man darauß was machen

Heiko - Mi 13.04.05 20:13

Ich nehm mal ein Beispiel. Du hast nur den Text ABBBABBA (natürlich viel länger). Da es nur 2 Zeichen sind, schriebst du in eine Bibliothek, die am Anfang der Datei ist, das es nur die beiden Zeichen gibt und A=0 und B=1 ist. Damit erhälst du die Bitfolge (ohne Bibliothek): 01110110. Damit hast du 8Byte in 1Byte(=8Bit) umgewandelt, sparst also bei langen Texten viel Speicher und die Bibliothek wird bei großen Dateien sich kaum bemerkbar machen.

Heiko - Do 14.04.05 07:04

Dein Beispiel für eine Komprimierung werde ich heute Nachmittag, wenn ich nach dem Training noch Zeit habe, ausprobieren. Ich glaub aber nicht das man den Text stark komprimieren kann, da er so ziemlich kurz ist. Ich habe gerade mal versucht dein Beispieltext mit Win-Rar zu packen.
Ergebnis: ungepackt: 45Bytes
gepackt: 114Bytes (bei höchster Kompressionsrate)

So weit ich weiß arbeiten die Packer nach dem Prinzip wie ich es dir vorgeschlagen hatte. Das Problem bei so kurzen Texten ist die Bibliothek, dass die zu groß wird.

Die Packraten gehen teilweise deutlich über 30-50%. Mit Win-Rar habe ich gerade eine html-Seite auf 8% komprimiert, also 92%.

Gausi - Do 14.04.05 10:24

Man kann nicht jede beliebige Datei komprimieren. Eine Jpg oder mp3-Datei lässt sich nur minimal komprimieren, weil sie schon komprimiert sind. Da lässt sich auch nicht mehr viel tricksen. Und irgendwo ist bei jeder Komprimierung Schluss. Man kann nicht jede Datei auf eine Größe von ein paar Bytes reduzieren. Es geht einfach nicht.

Andere Dateien dagegen lassen sich sehr schön packen, und das kann man auch missbrauchen. Ein Beispiel dafür ist die Suche bei Google

42.ZIP. Per eMail verschickt an ein System mit Virenschutz, welches gepackte Anhänge entpackt, um sie auf Viren zu untersuchen...da freut sich der Anwender!

delfiphan - Do 14.04.05 14:30

mimi hat folgendes geschrieben:

was eine eine idee währe:
wenn das Programm die Datei in einen richtig format bringen kann, das z.b. zip dann mit bis zu 100 % packen kann....

Wieso programmierst du's nicht einfach und wirst Millionär? -- Wenn es ein Programm gäbe, welches eine beliebige Datei in ein Format bringen würde, welches man mit Zip "bis zu 100% packen" könnte, wäre dieses Programm nicht schon längst ins Zip eingebaut worden? Überleg doch mal.

Die Information, die in einer Datei steckt, muss auch in der komprimierten Datei stecken (oder im Packer). Ein Packer kann nichts anderes tun als redundante Informationen zu löschen. Eine Transformation vor der Komprimierung kann hilfreich sein, wenn du Information über die Datei besitzt, welche Zip nicht ausnützt bzw. ausnützen kann. Wenn du aber selbst auch nichts weiteres über die Datei weisst, kannst du's vergessen.

Heiko - Do 14.04.05 14:44

Ich denk mal die maximale Kompressionsrate bei sinnvollen Texten, also wie Programmquelltexte, kann man die Datei maximal um 95% packen und auf keinen Fall mehr. Als nicht sinnvolle Texte sehe ich z.B. eine Textdatei die nur aus A besteht. Solche Dateien kann man auf fast 0% runterkomprimieren. Das Beipsiel habe ich auch mal ausgetestet.
unkomprimiert: 42,2 MB (44.353.984 Bytes)
komprimiert: 3,06 KB (3.141 Bytes) als rar-datei (maximale Kompressionsrate).
Wie du siehst kann man solche Dateien sehr gut kompremieren. Aber solche Dateien hat man ja schließlich normalerweise nicht :wink: . Bei meinem letzten Post hatte ich mal einen meiner Quelltext packen lassen (auf 8%), woran du auch siehst das sinnvolle Texte nie über 95% kompremiert werden. Allso ist es utopisch 4GB sinnvolle Dateien auf 20-30MB zu packen. Solche Dateien kannst du maximal auf 200MB komprimieren, und dann dürfen es auch nur Textdaien sein.

Das Verfahren, welches ich dir vorgeschlagen habe, ist so weit ich weiß auch das Verfahren auf das WinZip und WinRar bauen. Die unterschiedliche Packleistung hängt dabei nur von der Effektivität der Bibliotheken ab, wo momentan eindeutig WinRar vorne liegt. Das Problem bei solchen Packprogramme liegt an der richtigen Plazierung der Bibliotheken in der Datei.
Als Beispiel: ABBAGFFG (müsste natürlich viel länger sein)
Hier würde es sich lohnen nicht eine Bibliothek mit 4Zeichen anzulegen (also A, B, F, G), sondern 2 Bibliotheken: Bibliothek 1: AB
Bibliothek 2: FG,
da im ersten Abschnitt nur A und B vorkommen und im 2. Abschnitt nur F und G. Wenn diese Abschnitte länger sind als hier, dann spart man wesentlich mehr Speicherplatz als mit nur einer Bibliothek.
Und was Gausi sagte stimmt. Versuch mal ein Musikalbum zu komprimieren. Dann sparst du vielleicht von 120MB 3MB, bringt also nicht viel. Das Problem bei solchen Dateien ist dass sie schon auf ähnliche Art kompriemiert sind. Als Beispiel speichere mal eine Zahl als String ab und als Vergleich, mit z.B. TFileStream, eine Zahl als Integer. Dann wirst du sehen, dass z.B. 4294967295 nicht mehr 10Bytes (als String) benötigt, sondern nur noch 4Bytes. Und da z.B. mp3-Dateien schon solche Zahlen als Integer, und nicht als String, abspeichern kann, man die Zahl auch nicht viel weiter komprimieren.

Heiko - Do 14.04.05 19:40

In die Bibliotheken speichert man rein, welche Zeichen vorkommen, welchen Wert diese haben und natürlich wieviel Bits ein Zeichen benötigt. Wie immer ein Beispiel dafür :wink: :
unkomprimiert: ABCDCDBA
komprimiert wird eingespeichert:
1. Die Zahl 4 (wieviel Zeichen in der Bibliothek sind)
2. Die Zeichen 1-4, also A (=0), B (=1), C (=2), D (=3) (damit kein das Programm weiß wo das Ende der Aufzählung ist, wurde davor die Anzahl eingespeichert)
3. Wieviel Bits ein Zeichen belegt: 2 (da mit 2^1 die Zahlen 0, 1, 2 und 3 dargestellt werden kann; maximal 1Byte, da jedes Zeichen, soweit ich weiß, genau 8Bits benötigt)
4. Der Text ABCDCDBA: 01232310 (die Zeichen mit dem Wert des Zeichen [der Wert wird durch die Reihenfolge der Zeichenfestlegung festgelegt] ersetzen; jede Ziffer hier belegt 2Bits, also die Bitanzahl die oben eingespeichert wurde).

Ich hoffe das du es jetzt verstanden hast, sonst muss ich mal am Wochenende einen Packer schreiben, obwohl ich eigentlich keine Zeit habe :wink: (wer hat den heutzutage überhaupt noch Zeit?).

Heiko - Fr 15.04.05 07:12

Warum mehrere Bibliotheken an manchen Stellen sinnvoll sind, habe ich dir bereits in einem Post geschrieben (der 3., von mir, über diesem). Aber ich erklär dir das nocheinmal kurz. Stell dir einen Text vor der alle 256 Zeichen die es gibt beinhaltet. Da es relativ unwahrscheinlich ist das alle Zeichen ständig verwendet werden, oder das alle Zeichen in einem kurzen Text verwendet werden, ist es in diesem Fall sinnvoll mehrere BLs anzulegen, denn es gibt mit sehr hoher Wahrschenlichkeit Textabschnitte, die nur maximal 128 verschiedene Zeichen verwenden. Wenn man in solchen Fall dann eine neue BL einschiebt, benötigt mann, z.B. wenn im ersten Teil alle Zeichen verwendet wurden, nur 7 statt 8Bits für die Zeichen im folgendem Textabschnitt.

Bei deinem Text:

Quelltext

1:
2:

Hallo,
wie geht es dir ?

hat es kein sinn mehrere Bibliotheken anzulegen, da der Text zu kurz ist und jedes Zeichen innerhalb eines kleinen Bereiches verwendet wird. Deshalb nehm ich nur eine Bibliothek. Ich nehme die Punkte aus dem vorletzten Post ohne weitere Erklärung (aber eine kurze Rückerinnerung), da ich die dort schon erklärt hatte.

1. 17 (Zeichenanzahl)
2. #13, #32, ?, ',', H, a, d, e, g, h, i, l, o, r, s, t, w (#13=Zeilenumbruch; #32=Leerzeichen; '' habe ich nur hinzugefügt, damit man erkennt, dass das Zeichen auch Zeichen ist und kein Aufzällungskomma).
3. 5 (sowiel Bis belegt ein Zeichen)
4. 4, 5, 11, 11, 12, 2, 1, 0, 16, 10, 7, 1, 8, 7, 9, 15, 1, 7, 14, 1, 6, 10, 13, 1, 3, 1

Mir ist aber nochwas eingefallen. Den Punkt 3 kannst du weglassen, da das Programm aus der Anzahl der Zeichen ermitteln kann. Dafür müsste an dieser Stelle stehen, wo die nächste BL steht.

PS: Ich wünsche dir viel Spaß beim Durchdenken des Punktes 4. Ich habe für diesen Post immer 1/2 Stunde gebraucht, da ich mir die Buchstaben per Hand sortiert und ausgetauscht habe.

mimi - Fr 15.04.05 09:29

Du meinst also folgendes:
Du gehts davon aus das in einer Datei(bin) nicht alle zeichen das asscicode stehen, sehe ich das richtig ?
und jetzt sammelst du zeichen: du gehts mit einer schleife jedes zeichen durch wandels es in asscizeichen und sagt z.b. nach 10 zeichen eine neue BL gut z.b. so:

Ich habe jetzt eine Datei z.b. eine exe datei die möchte ich gerne packen.
Ich gehe diese datei zeichen für zeichen durch und nach 10 zeichen lege ich eine neue BL an,
damit ich das zeichen wiederherstellen kann verwende ich ein Trennzeichen z.b. ein, also so:
0,1,2,3,10,11,12,5,8,7,6
und davor speicherst du ab wie welches zeichen 0 steht z.b.:
0=120, 1=210, 2=215, 3=110,.....
das ist eigetnlich keine schlechte idee, wenn ich das richtig verstanden hab.

du müsstes sogar garnich abspeichern wenn die nächste BL ist die kannst du selbst ermitteln, du weißt wenn eine BL zu ende ist also fängt eine neue an bei nächsten zeichen.

also meine ich das jetzt:
0=120, 1=210, 2=215, 3=110,..... und das bis 10 und abspeichern würde ich das so:

120,210,215,110, ich weiß ja: das erste zeichen ist 0 und das zweite ist 1
0,1,2,3,10,11,12,5,8,7,6

und damit es noch besser wird: wenn ich z.b. auf ein zeichen komme was schon in einer BL steht kann ich ja ein verweis auf die BL bringen wo das zeichen drin steht, ob das was bringen würde ?

Nur dann müste ich die datei erstmal pasen und alle BL raußkopiern* z.b. in einer TStringList und dann kann ich ja einfach sagen, wenn du auf b34 trifst meine ich die 3 BL und das 4 zeichenm.

*oder es werden alle BLs am anfang gespeichert nur dann wird das entpacken recht aufwendig bzw. es könnte auch so gemacht werden:

Zitat:

0=120, 1=210, 2=215, 3=110,
0=140, 1=110, 2=210, 3=120,
1 BL*
0,1,2,3,10,11,12,5,8,7,6
2 BL*
0,1,2,3,10,11,12,5,8,7,6

* diese zeile würde ich nicht abspeichern also die datei würde dann so aussehen:

Zitat:

0=120, 1=210, 2=215, 3=110,
0=140, 1=110, 2=210, 3=120,
0,1,2,3,10,11,12,5,8,7,6
0,1,2,3,10,11,12,5,8,7,6

das würde glaube ich nichts bringen, aber irgenwie muss der Paser wissen wann eine BL gemeint ist und welcher index aus der BL gemeint ist.

Weil dann würde das bei großen dateien bestimmt was bringen.
Dann währe das doch auch egal, ob die datei mit ZIP schon gepackt wurden ist oder ?

I.MacLeod - Fr 15.04.05 18:50

Heiko hat folgendes geschrieben:

Da ist es sinnvoll variable Bitzahlen für die Zeichen zu verwenden. Wenn du dann massenhaft "e"s hast, hast du dadurch auch nur einen sehr kurzen Code. Weniger häufig vorkommende Werte bekommen dann eben auch entsprechend längere Codes.

Siehe: http://de.wikipedia.org/wiki/Huffman

Heiko - Fr 15.04.05 19:22

Die Idee finde ich nicht schlecht, bringt aber nicht unbedingt Vorteil, da man bei den meisten Zeichen noch mehr Bytes benötigt, da man ein Byte als Zeiger auf den Unterzweig benötigt. Aber es kann sein, dass das Verfahren bei größeren Dateien Vorteile bringt.

@mimi: Die BL hat keine feste Größe, sondern immer eine angepasste, so dass man mit einer BL am meisten spart. Ansonsten scheint es mir, als ob du das Verfahren verstanden hast.

mimi - Fr 15.04.05 21:19

die e.wikipedia.org/wiki/Huffman kompirmierung finde ich nicht so gut: es wird irgenwie ein baum von zeichen angelgt und du musst diesen Baum mitabspeichern das, dauert und macht die datei nur größer... so wie ich es verstanden habe

@Heiko
ja bei kleinen dateien währe diese pack funktion besitmmt nicht so gut wie bei großen Dateien. aber ich kann mir schon vorstellen das es was bringt bei 2 GB dateien...
Das Problem ist nur diesen verweis zu machen: untern den BLs wenn da dann sowas steht:
3040459939
49588394B12

Ich weiß ja jede BL ist von 0-9 zeichen lang(standart größe.es sei denn es sind mehr oder weniger dann wird eine neue BL angelgt z.b. bei 11 zeichen oder so.
und wenn der Paser jetzt auf ein B kommt erwartet er eine 1 zeichen und danach noch eins das sind drei zeichen wie könnte man das verkürzen, das es auch was bringt.

ich werde den Packalgo mal schreiben und testen.
Hast du einen namen für den Pack algo ?
gibst den schon ?
(testen werde ich ihn aufjedenfall, weil die idee ist nicht schlecht.

I.MacLeod - Fr 15.04.05 21:49

Heiko hat folgendes geschrieben:

Der Baum wird einmal abgespeichert. Wenn mans richtig macht ist der Overhead nicht viel größer als der bei deiner Methode - und die Kompressionsraten sind besser.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 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!