AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Effiziente Kompressionsverfahren

Ein Thema von Marphy · begonnen am 29. Mai 2005 · letzter Beitrag vom 19. Feb 2006
Antwort Antwort
Seite 2 von 6     12 34     Letzte »    
Dust Signs

Registriert seit: 28. Dez 2004
Ort: Salzburg
379 Beiträge
 
#11

Re: Effiziente Kompressionsverfahren

  Alt 29. Mai 2005, 22:11
Zitat von alzaimar:
Der hier in der Codelibrary gepostete Huffman Algorithmus hat Nichts, aber auch gar Nichts mit effektiven Kompressionsverfahren und inbesondere dem adaptiven Huffman Coding zu tun. Er implementiert den einfachen Brute Force Entropieverdichter, ein netter Algorithmus zum Üben, er eignet sich jedoch überhaupt nicht für den praktischen Einsatz. Ich weiss nicht, wieso das keiner ausprobiert.

Ich habe hier eine 110MB Datenbank (MSSQL), die sich wunderbar verdichten lässt. Die Kompressionsrate von 'Hufman' liegt bei ca 55%. Das ist schlecht. Sehr schlecht. Wie man dann behaupten kann, besser ginge es nicht, der kennt wohl kein LZW, LZSS oder BZIP usw.

RAR (adaptives Huffman Coding) kommt auf 95%,
Pkzip auf 91%. Zlib liegt gleich auf, was daran liegt, das die in PKZIP verwendeten Verfahren implementiert wurden.
Lz
Ich verwende in meinen Applikationen Zlib, da die Geschwindigkeit ordendlich und die erzielten Kompressionsraten ausreichend sind. Ich würde RAR nehmen, aber leider gibt es den Packer, soweit ich weiss, nicht als Code.

BZIP (oder Markov) soll zwar besser sein, die mir vorliegende Sourcen schaffen das aber nicht.
Es geht hier aber um schnelle Kompressionsverfahren, wie du ohne Zweifel dem ersten Beitrag entnehmen kannst. Und RAR ist bei den Kompressionsraten, die du ansprichst, alles andere als schnell...

Dust Signs
(aka AXMD in der EE)
Die Nummer, die Sie gewählt haben, ist imaginär. Bitte drehen Sie Ihr Telefon um 90° und versuchen Sie es erneut.
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#12

Re: Effiziente Kompressionsverfahren

  Alt 29. Mai 2005, 22:17
@Dust Signs: Bitte zitiere doch nur den Teil des Beitrags, den du für deine Stellungnahme auch benötigst, das liest sich deutlich besser, danke.

Zitat von Dust Signs:
Es geht hier aber um schnelle Kompressionsverfahren [...]
Ebenfalls aber auch um eine hohe Kompression und ähnliches (siehe Beitrag #1). Und eine hohe Kompression bietet nunmal RAR. Langsam ist es nicht, aber auch nicht das Schnellste.
Ich denke allerdings auch, dass Schnelligkeit und eine hohe Kompression einen Widerspruch darstellen. Je besser die Kompression, desto länger dauert das Komprimieren. Zumindest habe ich es bei den Kompressionsprogrammen, die ich nutze so festgestellt.
  Mit Zitat antworten Zitat
tommie-lie
(Gast)

n/a Beiträge
 
#13

Re: Effiziente Kompressionsverfahren

  Alt 29. Mai 2005, 22:24
Zitat von Dust Signs:
Es geht hier aber um schnelle Kompressionsverfahren, wie du ohne Zweifel dem ersten Beitrag entnehmen kannst. Und RAR ist bei den Kompressionsraten, die du ansprichst, alles andere als schnell...
BZip2 in Software iss auch nicht schnell
Wo wir schon dabei sind, darf ich wieder mit meinen obligatorischen non-PC-Plattformen kommen? Man könnte ja Kompressionsalgorithmen in Hardware gießen, idR schneller als auf einem RISC
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#14

Re: Effiziente Kompressionsverfahren

  Alt 29. Mai 2005, 22:36
@Dust Signs: Ich habe das 'schnell' schon gelesen. RAR ist schon ok, schneller als die mir vorliegende zlib-Version, soweit ich mich erinnere. Natürlich nicht so schnell wie PKZIP, aber ausreichend. Da die Kompressionsrate von RAR jedoch unerreicht ist, kommt RAR für mich als perfekter Kandidat in Betracht. Aber, das ist Geschmacksache. Wichtig war mir, das hier Dinge gepostet werden, ohne sie mal nachzuprüfen.

Von der Schnelligkeit her würde ich LZW Verfahren nehmen. Das ist sauschnell. Aber eben nicht sonderlich effizient. Probier das hier mal aus. Das ist zwar nur Delphi (kein ASM), aber geht wirklich ab wie Sau. Vielleicht reicht es Dir ja.

Ich habe auch den LZH Code als Delphi-Version probiert. Aber der ist einfach zu langsam.
Angehängte Dateien
Dateityp: pas lzrw1kh_172.pas (9,2 KB, 59x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Marphy

Registriert seit: 24. Feb 2005
162 Beiträge
 
Delphi 7 Professional
 
#15

Re: Effiziente Kompressionsverfahren

  Alt 30. Mai 2005, 16:05
Hallo zusammen,
danke erstmal für die rege Beteiligung!

Zitat:
Der hier in der Codelibrary gepostete Huffman Algorithmus hat Nichts, aber auch gar Nichts mit effektiven Kompressionsverfahren und inbesondere dem adaptiven Huffman Coding zu tun. Er implementiert den einfachen Brute Force Entropieverdichter, ein netter Algorithmus zum Üben, er eignet sich jedoch überhaupt nicht für den praktischen Einsatz. Ich weiss nicht, wieso das keiner ausprobiert.
Danke für den Hinweis, alzaimar!

Zitat:
Ich denke allerdings auch, dass Schnelligkeit und eine hohe Kompression einen Widerspruch darstellen. Je besser die Kompression, desto länger dauert das Komprimieren.
Natürlich. Ich habe nur die Forderung gestellt, dass der Algo möglichst schnell sein, dabei aber auch eine möglichst hohe Krompression bieten soll. Wenn es mit nur um Schnelligkeit ginge, würde ich nicht auf die Idee kommen, die Daten zu komprimieren.

Zitat:
Man könnte ja Kompressionsalgorithmen in Hardware gießen, idR schneller als auf einem RISC
Tolle Idee! Wahrscheinlich werde ich gleich eine kleine PCI-Karte basteln, dem Setup meiner Freeware beilegen und das Ganze dann zum Download anbieten...

Zitat:
@Dust Signs: Ich habe das 'schnell' schon gelesen. RAR ist schon ok, schneller als die mir vorliegende zlib-Version, soweit ich mich erinnere. Natürlich nicht so schnell wie PKZIP, aber ausreichend.
PKZIP ist höchstwahrscheinlich C++ oder gar Assembler. Wenn Delphi die gleiche Kompressionsmethode in seiner ZLib implementiert, ist diese "schlampig" geschrieben, Delphi nicht sonderlich schnell oder beides zusammen.
Bisher dachte ich jedenfalls, Delphi langt von der Performance her knapp an C(++) heran.

Zitat:
Von der Schnelligkeit her würde ich LZW Verfahren nehmen. Das ist sauschnell. Aber eben nicht sonderlich effizient. Probier das hier mal aus. Das ist zwar nur Delphi (kein ASM), aber geht wirklich ab wie Sau. Vielleicht reicht es Dir ja.
Werde ich auf jeden Fall mal ausprobieren. Danke!

Gruß, Marco
Marco
Wo ein Wille ist, ist auch ein Weg. Aber wo ein Weg ist, ist nicht unbedingt auch ein Wille...
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#16

Re: Effiziente Kompressionsverfahren

  Alt 30. Mai 2005, 16:32
Was PKZIP und zlib anbelangt, darfst Du nicht vergessen, das der gute Phillip Katz ('PK') sich einen abgebrochen hat, damit sein Tool die #1 wird. Also hat er optimiert, was das Zeug hält. Zlib ist 'nur' eine normale ASM-Implementierung, die natürlich noch Optimierungspotential hat. Beim LZW-Algorithmus z.B. gibt es ein Wörterbuch, das immer weiter wächst. Irgendwann wird es zu gross und muss 'bereinigt' werden. Ich meine, das PkWare das genaue WIE und WANN der 'Dictionary-Reinigung' nicht verraten. Gerade DAS macht aber noch einige Prozente in der Komprimierungsrate aus.

Die Geschwindigkeit von zlib hat m.E. nichts mit Delphi vs. C(++) zu tun, sondern mit Algorithmen und Optimierungen: "Ein BubbleSort in ASM ist immer langsamer als ein Quicksort in JavaScript." (Gut, bei mehr als 1000 Elementen )

Teste einfach mal zlib. Ich weiss nicht, welche Version Du hast. Ich habe die hier und mir reichts (ich wiederhole mich)
Angehängte Dateien
Dateityp: zip zlib_656.zip (47,6 KB, 26x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Dax
(Gast)

n/a Beiträge
 
#17

Re: Effiziente Kompressionsverfahren

  Alt 30. Mai 2005, 16:55
Zitat von alzaimar:
Der hier in der Codelibrary gepostete Huffman Algorithmus hat Nichts, aber auch gar Nichts mit effektiven Kompressionsverfahren und inbesondere dem adaptiven Huffman Coding zu tun.
Das ohne Zweifel, der Code is nach eigenen Aussagen nicht optimiert Und da du es gerade ansprichst: Wie funktioniert diese Kompressionsmethode denn genau? Entweder suche ich falsch oder ich bin blind

read you,
Dax
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#18

Re: Effiziente Kompressionsverfahren

  Alt 30. Mai 2005, 16:57
Huffman + http://de.wikipedia.org/wiki/Huffman
  Mit Zitat antworten Zitat
Dax
(Gast)

n/a Beiträge
 
#19

Re: Effiziente Kompressionsverfahren

  Alt 30. Mai 2005, 17:12
Ach Heinz Wie Die Huffman-Kodierung funktioniert weiß ich Ich wollt aber was zu adaptive Variante erfahren, und dazu hab ich nix gefunden
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#20

Re: Effiziente Kompressionsverfahren

  Alt 30. Mai 2005, 17:19
Ich wollte Dir nix Böses . Es geht ja bei Verfahren erst in zweiter Linie ums Optimieren. Wenn das Verfahren nicht stimmt, dann bringt 'Optimieren' hier auch Nichts. Deine Hufman-Implementierung is ordendlich, darauf kommt es an. Allerdings sollte man schon mal Vergleiche mit in freier Wildbahn auftretenden Packern machen, bevor man euphorisch die Implementierung des Hufman feiert. Aber egal.

Ich habe leider keine akkuraten Beschreibungen oder Listings zum RAR-Verfahren. Das LZH-Verfahren kann ich Dir geben...

Der 'Nachteil' vom von Dir implementierten 'statischen' Huffman Codiung ist:
1. Du musst den KodierungsBaum mitschicken.
2. Du berücksichtigst die Verteilung der Bytes nur in der gesamten Datei.

So, wie ich das verstanden habe, fängt der 'adaptive Hufman' mit einem standardisierten Kodierungsbaum an (Es gibt ein Listing für UNRAR, da steht er drin). Somit entfält Nachteil #1. Dann wird während des Kodierens der Kodierungsbaum immer wieder überarbeitet, um die aktuelle Bytehäufigkeit zu berücksichtigen. Somit entfällt Nachteil #2. Vermutlich stecken noch ettliche kleine 'Optimierungen' drin, um auf diese Kompressionsraten zu kommen: Trivial ist das nämlich nicht.

Am Spannendsten finde ich jedoch die Markov-Verfahren, die doch tatsächlich darauf aufbauen, das nächste Byte zu 'erraten'. Das klappt sogar. Unglaublich. Leider auch extrem langsam.

Hier das LZH-Verfahren (Ziemlich laaaangsam)
Angehängte Dateien
Dateityp: zip lzhpas_878.zip (7,2 KB, 23x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 2 von 6     12 34     Letzte »    


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:44 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz