Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Komprimierung_wie
fuggaz - Do 10.01.08 21:21
Titel: Komprimierung_wie
Hallo,
Ich wollte als einfache Komprimierung folgendes nehmen:
Ich suche Wiederholungen im Text und ersetze sie durch Zeiger.
Ich stoße aber auf ein paar Probleme:
1.Zum Algorithmus:
Da ich Wiederholungen suche, muss ich ja jede länge ab 1/2 des Textes ausprobieren...
und dann auch noch versetzt:
hallo du da du asdflksjdfldkfjlhallosdfsdfsdfsdf
Das dauert doch ewigkeiten?
Ich weiß nicht so recht wie ich bei google diesbezüglich was suchen soll~~
2.
Eine Art Bsp wie es aussehen könnte:
1.hallo.2.test.."1" dies ist ein "2" "1" "2" "1" "2"
Wie aber trenne ich Referenzwörter am Anfang?
Woher weiß ich dass das nicht so vom benutzer eingegeben wurde?
Ich will ja dem Benutzer nicht verbieten bestimmte Zeichen zu benutzen.
Was mich auch zur letzten Frage führt:
3.Textkodierung
unicode hat auch 30 einen pfeil, ANSI nicht.
Wie gehe ich damit um?
Auf ein paar Antworten würde ich mich freuen.
Gerne auch gute Links zum Thema.
mfg fuggaz
Edit:Doch noch eine Frage:
Warum bringt mir binär zu speichern kein Speichervorteil?
Wenn ich 26 einsen speicher ist die datei 26byte groß...
Dann brauch ich sie ja nicht binär zu speichern.
DrRzf - Fr 11.01.08 00:32
Wenn du den ASCII code binär speicherst (wie auch sonst) sinds und bleibens nun mal 26 Byte
Binär speichert nur 0 und 1
26 Einsen sind somt 26 Bit, also 3,25 Byte. (4 Byte)
golgol - Fr 11.01.08 09:07
zu 2.:
Also zu der Abgrenzung zwischen Definitionen und Benutzertext könntest du so vorgehen: Die ersten x Byte im Ausgabefile geben (in Bit-Codierung) an, wieviele der anfänglichen y Bytes definitionen sind. Somit wüsstest du dann, dass erst nach x+y Bytes der eigentliche Text losgeht. Somit würdest du keine Buchstaben unterdrücken. Der Nachteil wäre lediglich, dass du zu Beginn des Files einen gewissen Bereich dauerhaft reservieren müsstest, der groß genug ist, um einen Bereich zu reservieren, der alle möglichen Definitionen enthalten kann.
Wenn man bedenkt, dass mit 10 Bits bereits die Zahl 1023 dargesellt werden kann, müsste dafür max. 1kb genommen werden (grobe Schätzung).
Delete - Fr 11.01.08 10:32
Wenn man mal nach "komprimierung algorithmus" sucht, sollte man sehr schnell auf den namen Huffman und den damit verbundenen Codierungsalgorithmus stossen.
alzaimar - Fr 11.01.08 12:14
Deine Idee der Referenzierung auf Wortlisten wird selten implementiert. Ein ähnlicher Algorithmus ist jedoch LZSS, der hier im Ansatz erklärt wird:
http://www.binaryessence.de/dct/de000139.htm.
Wenn es Dir nur darum geht, Daten zu komprimieren, dann such mal nach ZLib bzw. ZLibEx. Damit geht das sehr schnell und auch ziemlich effizient.
fuggaz - So 13.01.08 00:47
@DrRzf:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22:
| var myFile : File; txtfile:textfile; byteArray : array[1..8] of byte; i: Integer;
begin
AssignFile(myFile, 'c:\Test.txt'); ReWrite(myFile,8);
for i := 1 to 8 do byteArray[i] := 1; BlockWrite(myFile, byteArray, 1);
CloseFile(myFile);
AssignFile(txtfile,'c:\test1.txt'); ReWrite(txtfile); Write(txtfile,'11111111'); closefile(txtfile); end; |
Beide Dateien sind gleich groß...
Oder mache ich etwas falsch.
Ich will acht mal 1 setzen.
Sollte folglich 1Byte groß sein.
Sind aber 8Bytes-wie die Textdatei...
@golgol:
Danke für den Tip!Das bringt mich auf die Idee nur die erste Zahl zu reservieren.
Die gibt dann darüber auskunft wie weit meine Definitionen reichen und wo der kodierte Text anfängt.
@Luckie:ja allerdings finde ich keinen speziellen beispiele, die auf meine Fragen eingehen.
@alzaimar:thx.Habe im Delphi zlib.pas gefunden.
Werde mal versuchen mich dort einzuarbeiten.
nagel - So 13.01.08 01:54
Du schreibst ein Array[1..8] of Byte in eine Datei, folglich ist diese 8 Byte groß. Was du hier machst, ist quasi, 8 mal den Bytewert 1 zu schreiben, so dass deine Datei vermutlich so aussieht: 01 01 01 01 01 01 01 01 (hex). Kannst ja mal mit einem Hexeditor überprüfen. Was du, soweit ich das verstanden habe, machen willst, ist ein FF zu schreiben, also 255, oder eben binär 11111111. Und wenn du irgendwann nicht nur 1en schreiben willst, musst du eben immer acht deiner Binärstellen in einen Bytewert umrechnen, aber dazu findest du hier sicher irgendwas.
fuggaz - So 13.01.08 12:53
Dann schreibe ich ja tatsächlich nicht wirklich binär :(
So ein Mist aber auch^^
Danke für den Link:)
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!