Αλγόριθμοι Συμπίεσης

...το μέρος για να ξεκινήσετε!

Συντονιστής: adem1

Κανόνες Δ. Συζήτησης
Παρακαλώ να επιλέξετε, με προσοχή, την άδεια που θέλετε να έχουν οι οδηγοί που συγγράφετε.
Πληροφορίες για τις άδειες μπορείτε να βρείτε εδώ.
Άμα επιθυμείτε κάποια άλλη άδεια επικοινωνήστε με κάποιο Διαχειριστή είτε Συντονιστή.

Σημαντικό είναι να χρησιμοποιήσετε την υπηρεσία http://imagebin.ubuntu-gr.org για τις εικόνες.

Αλγόριθμοι Συμπίεσης

Δημοσίευσηαπό kalakouentin » 28 Οκτ 2008, 21:05

Όπως πολλοί θα έχετε παρατηρήσει υπάρχουν πολλές επιλογές στο Ubuntu περί αλγορίθμων συμπίεσης. Από περιέργεια λοιπόν αποφάσισα να τους τεστάρω. Αποφάσισα ότι οι κύριοι ανταγωνιστές θα είναι 5. Ο bz2, ο lzma, ο 7z, ο zip και ο gz. Τέλος όρισα 7 "αντιπροσωπευτικά" για εμένα set προς συμπίεση και άρχισα να "συμπιέζω"! :D
Τα 7 σετ είναι τα ακόλουθα:
  1. Series_set: Ο πρώτος κύκλος της σειράς Numb3rs.14 .avi. 4.4 Gbytes.
  2. Οffice_set: Mια συλλογή από πιθανά έγγραφα γραφείου: 8.xls, 3.ods, 3.odp, 11.odt, 15.pdf, 3.txt, 2.ppt, 10.rtf και 20.doc. 75.3 MBytes
  3. Photos_set: 55 φωτογραφίες που τράβηξα στο Imperial War Museum στο Λονδίνο. 55 .JPG. 77.9 MBytes
  4. Video_set: Μια συλλογή από ξεκάρφωτα videάκια. 1.mp4, 1.mpg, 2.ogg, 4.mov, 2.wmv. 385.2 MBytes
  5. Various_set: Μια συλλογή από ότι έβρισκα στο Documents Folder μου. 1.torrent, 1.csv, 2.DjVu, 7.xls, 1.gif, 10.jpg, 1.sub, 6.ods, 29.odt, 151.pdf, 10.txt, 16.png, 4.ppt, 2.ps, 9.Rscripts, 3.mov, 1.rar, 2.rtf, 4.srt, 6.bmp, 35.doc, 4.zip. 333.3 MBytes
  6. RandomSequence_set: Ένας κατάλογος από 20000 ψευδοτυχαίων ακολουθίες συμβόλων μέσου μήκους 4630 χαρακτήρων που δημιουργήθηκαν μέσω της random.uniform και της random.randint από ένα python script. (Αυτό ουσιαστικά είναι ένα test για να δω την "ωμή" ισχύ του κάθε αλγόριθμου). 1.fas. 104.2 MBytes
  7. Tolstoy_set: (Τα "Άννα Καρένινα", "Πόλεμος και Ειρήνη" και "Αφέντης και Δούλος" του Τολστόι και τα 3 μαζί σε 1 .txt που κατέβασα απο'το Project Gutemberg (στα αγγλικά). 1.txt 5.2 MBytes

Ο καθένας από αυτούς τους αλγόριθμους κρίθηκε ΜΟΝΑΧΑ ως προς το τελικό του αποτέλεσμα. Δεν συνέκρινα ούτε πόσο χρόνο ήθελε, ούτε αν ήταν πιο computationally intensive.
Tα αποτελέσματα παρουσιάζονται παρακάτω. Πρώτα σε bytes και μετά ακολουθεί ο πίνακας με τους λόγους συμπίεσης (μέγεθος συμπιεσμένου αρχείου προς ασυμπίεστο). Επίσης πρέπει να σημειωθεί ότι οι αλγόριθμοι bz2, lzma και gz πρώτα έκαναν archive το αρχείο σε .tar και μετά το συμπίεζαν. Ακόμα στο Series_set ο αλγόριθμος zip δεν δεχόταν να κάνει συμπίεση τόσου μεγάλου αρχείου άρα δεν παρουσιάζονται μετρήσεις σχετικά με αυτό. Επίτηδες στους λόγους δεν ενδιαφέρθηκα για ακρίβεια πέρα από 3 δεκαδικά ψηφία ( <0.1%) γιατί θεώρησα ότι δεν χρειάζεται και όποια διαφορά δεν έχει ουσιαστικό ρόλο στο τελικό αποτέλεσμα. (πχ. στα 500 ΜBytes 0.1% είναι 0.5 MBytes ντάξει δεν το θεωρώ άξιο λόγου)

Στους ακόλουθους πίνακες οι καλύτερες τιμές είναι πάντα οι μικρότερες. Η καλύτερη επίδοση παρουσιάζεται με bold μαύρο και η χειρότερη με bold κόκκινο.
Εικόνα
Εικόνα

Καλύτερος αλγόριθμος συνολικά παρουσιάζεται ο 7z. Σχεδόν σε όλα τα test πήγε καλύτερα από όλους, όπως και συνολικά. 2ος καλύτερος αλγόριθμος είναι συνολικά είναι ο lzma. (Εδώ πρέπει να σημειωθεί ότι αν και ο χρόνος δεν έπαιξε ρόλο στη βαθμολόγηση των αλγορίθμων ο lzma ήταν πάντα και εμφανέστατα ο πιο αργός). Ο bz2 είναι καλύτερος από τον zip συνολικά άσχετα άμα αυτό δεν αποτυπώνεται στον τελικό μέσο όρο γιατί δεν πρέπει να ξεχνάμε ότι το test Series που ήταν ένας γενικότερος κόλαφος για όλα τους αλγόριθμους ο zip ούτε καν το εκτέλεσε και έτσι αυτό αποκλείστηκε από τη συνολική του βαθμολόγηση. Τελευταίος σχεδόν πάντα ήταν ο gz. Ο gz και ο zip ουσιαστικά είναι ο ίδιος αλγόριθμος και έτσι προφανώς βγάζουν τα ίδια σχεδόν αποτελέσματα.

Ως κατακλείδα, τα προφανή: Ο 7z είναι ο "καλύτερος" για γενική χρήση ενώ ο bz2 ίσως κάνει κάτι καλύτερο σε εξειδικευμένες περιπτώσεις. Οι zip και gz έχουν ουσιαστικά ξεπεραστεί και ο lzma έχει μέλλον αλλά πραγματικά θέλει ΠΟΛΥ βελτιστοποίηση από πλευράς ταχύτητας. Όλοι οι αλγόριθμοι (από τον χειρότερο στον καλύτερο) δεν έχουν παρά 3-4% διαφορά στην τελική απόδοση κατά μέσο όρο. Με την εξαίρεση του test στο Tolstoy_set σε όλες τι άλλα set η διαφορά της χειρότερης ή από την καλύτερη συμπίεση ήταν μέγιστο στο 10% (data not shown). Άρα το τοπίο μάλλον δε θα αλλάξει ριζικά σύντομα γιατί ακόμα και ο πιο "φρέσκος" lzma δεν έχει να προσφέρει κάποιο σημαντικό πλεονέκτημα ακόμα.
A. Kαι μην συμπιέζεται τα video σας. Άδικος κόπος. .avi,.mov, .ogv, etc. απλά δεν συμπιέζονται "ουσιαστικά". (γιατί στα 4,4 giga τα 63 Μbyte είναι σταγόνα στον ωκεανό!)

Licenses και βασικοί αλγόριθμοι πίσω από κάθε υλοποιηση:
  1. 7z: LGPL - LZMA
  2. bz2: BSD license - Burrows-Wheeler transformation
  3. lzma: GPL - LZMA
  4. gz: GPL - LZ77 algorithm και Huffman coding
  5. zip: Ποικίλες άδειες κυρίως freeware - ίδιο με τον gz
Για την ιστορία LZ σημαίνει Lempel - Ziv.Ο αλγόριθμος Lempel-Ziv θεωρείται ο "προτάτορας" όλων των μελλοντικών αλγόριθμων συμπίεσης.
Εικόνα
Γνώσεις ⇛ Linux: Συμπαθητικές ┃ Προγραμματισμός: Συμπαθητικότερες ┃ Αγγλικά: Αστέρι
Λειτουργικό ⇛ Ubuntu 10.04 32bit σε HP nw9440 ┃ Ubuntu 10.04 32bit σε Toshiba Satellite U400┃ SLED 11 64bit σε Dell OptiPlex 780
kalakouentin
seniorTUX
seniorTUX
 
Δημοσιεύσεις: 545
Εγγραφή: 05 Ιούλ 2008, 05:50
Εκτύπωση

Re: Αλγόριθμοι Συμπίεσης

Δημοσίευσηαπό simosx » 28 Οκτ 2008, 22:33

Ωραίο κείμενο!

Αδμίν, μεταφορά στα HowTos;
προσωπικό ιστολόγιο ϗ πλανήτης Ubuntu-gr
Συμβάλετε και εσείς στο ελληνικό βιβλίο Ubuntu!
1 Γνώσεις Linux: Πολύ καλό ┃ Προγραμματισμού: Πολύ καλό ┃ Αγγλικών: Πολύ καλό
2 Ubuntu 13.10 saucy 3.11.0-031100rc1-generic 64bit (el_GR.UTF-8, Unity ubuntu)
3 AMD E-450 APU with Radeon HD Graphics ‖ RAM 3555 MiB ‖ Sony Corporation VAIO
4 AMD nee ATI Wrestler [Radeon HD 6320] [1002:9806] {fglrx_pci}
5 eth0: Atheros Inc. AR8151 v2.0 Gigabit Ethernet [1969:1083] (rev c0) ⋮ wlan0: Atheros Inc. AR9285 [168c:002b] (rev 01)
Φτιάξτε και εσείς τη δική σας υπογραφή (παραπάνω κείμενο) αυτόματα με κλικ εδώ!
simosx
Επίτιμο μέλος
Επίτιμο μέλος
 
Δημοσιεύσεις: 10334
Εγγραφή: 11 Μάιος 2008, 18:52
Launchpad: simosx
IRC: simosx
Εκτύπωση

Re: Αλγόριθμοι Συμπίεσης

Δημοσίευσηαπό ftso » 28 Οκτ 2008, 22:54

simosx έγραψε:Ωραίο κείμενο!

Αδμίν, μεταφορά στα HowTos;


Ασυζητητί. :D

Μπράβο σου @kalakouentin!
Άβαταρ μέλους
ftso
Επίτιμο μέλος
Επίτιμο μέλος
 
Δημοσιεύσεις: 6409
Εγγραφή: 12 Μάιος 2008, 13:40
Τοποθεσία: Αθήνα
IRC: ftso
Εκτύπωση


Επιστροφή στο Οδηγοί - How to - Tutorials