rapt0r Δημοσ. 6 Μαρτίου 2004 Δημοσ. 6 Μαρτίου 2004 OPOS OLI GNORIZETE I SIMPIESI DEDOMENWN GINETE ME KAPIO TROPO, OXI KE POLI KALO KATA TI GNOMI MU... (INDEXING OF SAME DATA CHAINS AND REGROUPING UNDER A NEW REFERER...) PX: ---UNCOMPRESSED--- DOKIMI SIMPIESIS DOKIMI A DOKIMI B ---COMPRESSED--- ---INDEX--- Z="DOKIMI " X="SI" ---DATA--- ZXMPIEXS ZA ZB ---------------------------------------- KATA TI GNOMI MU AFTO INE PLEON ANAPOTELESMATIKO... EPISIS EXW VRI KATI WAREZ ISO TA OPIA AN TA KAPSIS SE CD INE 1.5 GB... (PX WIN2003 SERVER 4IN1 INE 780 MB KE AN TA KAPSIS I TA KANIS EXTRACT SE FAKELO INE 2 GB) EPISIS POLLA GAMES INE 50-100 MB ISO KE KAMENA INE 1 PLIRES CD... ------------------------------------------ MIN THEWRITHI PARANONMO TO POST DIOTI ANAFERW WAREZ, TO ANAFERW OS APLO PARADIGMA. ------------------------------------------ THA BORUSAME NA DIMIURGISUME KAPION DIKO MAS ALGORITHMO SIMPIESIS DEDOMENWN? (ISWS AN ANIGAME ENA ARXIO SE BINARY KE SIMPIEZAME TA BIT PU INE SE OKTADES SE ENA NEO DIKO MAS PINAKA SAN TON ASCII PU ANTI GIA 256 THA IXE 4096 CHAR. ???) DEN THA IXAME 8:1 SIMPIESI TOTE? --------------------------------------------
pantelisgeor Δημοσ. 6 Μαρτίου 2004 Δημοσ. 6 Μαρτίου 2004 an ginotane den to ekane kamia megali etairia na vgalei kai lefta apo ton algori8mo auto?
rapt0r Δημοσ. 6 Μαρτίου 2004 Μέλος Δημοσ. 6 Μαρτίου 2004 ginete apla praktika thewrite mi xrisimo, dioti o xronos simpiesis / aposimpiesis ine mi simferon ke apeti high-end ipologistika sistimata. omos gia idiotes pu exun xrono ke epithimun na simpiesun ta dedomena tus ine kalo kata ti gnomi mu, ke episis apo ola osa ine efikta na ginun ston programatismo den exi gini ute 1%... den xanume kati na dokimasume... endiaferete kanis?
random Δημοσ. 6 Μαρτίου 2004 Δημοσ. 6 Μαρτίου 2004 σχετικά με το βασικό ερώτημα, για συμμετοχή σε project, δεν με ενδιαφέρει, αλλα να σχολιάσω 2-3... PX:---UNCOMPRESSED--- DOKIMI SIMPIESIS DOKIMI A DOKIMI B ---COMPRESSED--- ---INDEX--- Z="DOKIMI " X="SI" ---DATA--- ZXMPIEXS ZA ZB ---------------------------------------- απο αυτό το "παράδειγμα" δεν κατάλαβα τίποτα... :oops: :?: ...KATI ..ISO TA OPIA (οποία AN TA KAPSIS SE CD INE 1.5 GB... (PX WIN2003 SERVER 4IN1 INE 780 MB KE AN TA KAPSIS I TA KANIS EXTRACT SE FAKELO INE 2 GB) Το συγκεκριμένο cd των win2003' date=' και τα παρόμοια 6in1, 5in1, κλπ, δεν είναι συμπιεσμένα. Απλά το cd , όπως και οι σκληροί δίσκοι, εχει μια μορφή FAT (file allocation table), δηλαδη εναν πίνακα οπου καταχωρήται η θέση κάθε αρχείου πάνω στη γεωγραφία του δίσκου, δηλαδη λέει κάπου στον πίνακα, με απλά λόγια, "το αρχείο WIN.EXE βρίσκεται στην παρακάτω θέση: το πρώτο του byte είναι το 1000στό byte του δίσκου, και έχει μήκος 1200 bytes..." όταν ζητήσεις το αρχείο, ο δίσκος διαβάζει το FAT για να βρει τη διεύθυνση του αρχείου, και πάει εκει... γυριζουμε λοιπον στο "περιεργο" cd. εχεί ενα FAT το οποιο εχει πολλές εγγραφές , για μία πραγματική διεύθυνση, οπότε λέει κάτι τέτοιο: αρχείο θέση μηκος \SRV1\I386\FILE.DAT 16016 1000 \SRV2\I386\FILE.DAT 16016 1000 \SRV3\I386\FILE.DAT 16016 1000 στην πραγματικότητα πρόκειται για το ίδιο αρχείο, αλλα έχει 3 εγγραφές στο fat. αυτό το καταλαβαίνουν τα προγράμματα που φτιάχνουν το cd (winiso, nero, cdimage.exe) αλλα οχι και ενα προγραμμα που εχει πρόσβαση μονο στα αρχεία (windows explorer) και τα παίρνει ενα ενα για να τα αντιγράψει, οποτε βλέπει τα διαφορετικά PAths και σου τα αντιγράφει 3 φορές στο σκληρό, με απλό file copy. EPISIS POLLA GAMES INE 50-100 MB ISO KE KAMENA INE 1 PLIRES CD... πολλά παιχνίδια, ενώ ο κώδικας, και τα video τους ειναι λιγότερα απο 600-700 mb, βάζουν και μερικά εξτρα αχρηστα αρχεία με πλασματικές εγγραφές στο fat , οπου αναφέρονται με τεράστια μεγέθη, για να μην μπορείς να τα κανεις αντιγραφή με απλό File copy. δηλαδή έχουν ενα αρχείο 100 KB, και με κατάλληλο πρόγραμμα γράφουν στο fat οτι έχει μέγεθος 4 GB. παλι δεν προκειτε για συμπίεση, και συνηθως αυτα τα cd αντιγράφονται εύκολα με Clonecd, Alcohool τα οποία δεν ασχολούνται με το τι λέει το fat, και διαβάζουν κατευθείαν τη φυσική ΄δομή του δισκου.
krot Δημοσ. 6 Μαρτίου 2004 Δημοσ. 6 Μαρτίου 2004 rapt0r αλγόριθμοι συμπίεσης υπάρχουν πάρα πολλοί και είναι επιστήμη ολόκληρη.... το παράδειγμα που έβαλες σαφώς και δεν είναι ιδιαίτερα αποτελεσματικός αλγόριθμος, (αλλά είναι εύκολος στην υλοποίηση) Ο πιο συνηθισμένος είναι παραλαγή αυτού που λες, αλλά με μεταβλητό αριθμό bytes, δηλ. το κάθε byte του αρχικού αρχείου πιάνει μεταβλητό αριθμό από bits στο συμπιεσμένο, ανάλογα με την συχνότητα που εμφανίζετε στο αρχικό. (αν ένας χαρακτήρας εμφανίζετε συνέχεια πιάνει λιγότερα bits από έναν που εμφανίζετε σπάνια) Στην αρχή του συμπιεσμένου αρχείου μπαίνει ένα πινακάκι με την αντιστοιχεία bytes αρχικού - bits συμπιεσμένου. Απ'όσο ξέρω έτσι κάνει και το zip... (και νομίζω λέγετε αλγόριθμος του hamilton).
Directx Δημοσ. 7 Μαρτίου 2004 Δημοσ. 7 Μαρτίου 2004 Σωστή περιγραφή! Απλά ονομάζεται «Huffman» ~ σε γενικές γραμμές τα περισσότερα πακέτα συμπίεσης βασίζονται σε διάφορες παραλλαγές του ...
morpheous Δημοσ. 7 Μαρτίου 2004 Δημοσ. 7 Μαρτίου 2004 den einai toso aplo:D idika gia eikones (jpg kai kata synepeia meta mpeg)prin ton huffman exoume kai ena fast furier transform panw se kapoioa digmata pou exoume parei xwrizodas tin eikona se pinakes 8x8 digmatwn....milame gia oloklirh episthmh!oso gia to ana anoigame to arxio binari kai sibiezame tote tha kaname mia aplh kodikopoihsh edropias me tin opoioa den tha ekmetalevomatan katholou ta xaraktiristika tou kathe arxeioou pros kodikopoihsh(an kseroume poio kanoume fisika) twra gia genikes kodikopoihseis se mazika arxeia kai tetoia ginode apisteftes erevnes:) dil den einai toso aplo na katsoume na ftiaksoume emeis ena:D (an se kati apo ta parapanw kanw lathos parakalw diorthoste me! na mathenoume kai na pragmata dil kai na diorthonoume ta lathi mas)
Directx Δημοσ. 7 Μαρτίου 2004 Δημοσ. 7 Μαρτίου 2004 Σωστή παρατήρηση! Για την συμπίεση της εικόνας (κάποτε το είχα ψάξει το ζήτημα για την συγγραφή ενός viewer –οπότε τα γράφω όπως τα θυμάμαι) υπάρχουν δυο μεγάλες κατηγορίες συμπιεστικών αλγορίθμων. Η πρώτη είναι οι απωλεστικοί (JPEG) όπου ένα τμήμα των εικονοστοιχείων που απαρτίζουν την εικόνα «χάνεται» ώστε να περιορισθεί το μέγεθος της θέτοντας παράλληλα όμως σε εφαρμογή ορισμένες τεχνικές που τείνουν να μετριάσουν αυτή την απώλεια σε αποδεκτά για το ανθρώπινο μάτι πλαίσια. Η δεύτερη κατηγορία είναι οι μη απωλεστικοί αλγόριθμοι (πχ. LZW/GIF) που συμπιέζουν την εικόνα δίχως να «χάνουν» κανένα από τα εικονοστοιχεία που την αποτελούν δίδοντας υψηλή ποιότητα αλλά χαμηλότερη συμπίεση σε σχέση με τους απωλεστικούς. Στην δεύτερη ομάδα συνήθως χρησιμοποιούνται τεχνικές Huffman (λιγότερο) ή LZW ή RLE (BMP) αλλά ακόμα και συνδυασμοί αυτών των τεχνικών ώστε να μπορέσουν να περιγραφθούν με όσο το δυνατόν λιγότερα bytes εικόνες υψηλής ανάλυσης που αναγκαστικά στον χρωματικό πίνακας τους (color index ή color map) περιέχουν για τον καθορισμό του χρώματος κάθε pixel που τις αποτελεί πάνω από ένα Byte ακολουθώντας την αρχή της τριχρωμίας RGB (εγγενή υποστήριξη RGB registers από το INT 10 του Video BIOS κάθε κάρτας VGA/SVGA) –εδώ παίζει περισσότερο το RLE&LZW-. Για το θέμα της εντροπίας δεν θέλησα να επεκταθώ καθόλου πριν, αλλά ουσιαστικά αποτελεί την βασική αδυναμία του Huffman για προφανείς λόγους. Σε διάφορα συμπιεστικά πακέτα (RAR/WinACE) που υποστηρίζουν την «μαζική συμπίεση γενικών αρχείων» (solid archives) πέραν του (γερασμένου) ZIP, ο Huffman μαζί με τον LZW φαίνεται ότι μπορούν να κάνουν «θαύματα» ειδικά όσο μεγαλύτερο είναι το λεξικό για κάθε chunk τους (αν και η συγκεκριμένη μέθοδος έχει ορισμένα «ενδιαφέροντα» μειονεκτηματάκια) ειδικά αν συμπιέζουμε αρχεία που ναι μεν έχουν υψηλή εντροπία αλλά παράλληλα έχουν κοινή καταγωγή (όμοιο format) για αναμενόμενους λόγους (κοινή συμπίεση static headers chunks, fragmented color maps κοκ..) Υ.Γ. Τα ίδια ισχύουν ως έναν βαθμό και στην συμπίεση μουσικής με εντελώς διαφορετική εσωτερική φιλοσοφία όσον αφορά την συμπίεση των ηχητικών δεδομένων σε απωλεστικούς αλγόριθμούς. Τέλος για την ιστορία αξίζει να σημειώσω ότι μια εφαρμογή «dictionary compression» όπως περίπου την περιγράφει ο φίλος rapt0r (με ακόμα πιο απλοϊκό τρόπο) εφάρμοζε στο αρχείο εντολών του AGI (ο interpreter για τα παιχνίδια της απο το 1984 ως το 1989/90) η Sierra, την προηγούμενη εικοσαετία..
thama Δημοσ. 13 Μαρτίου 2004 Δημοσ. 13 Μαρτίου 2004 Λοιπόν ώρα για λίγη θεωρία Το παρακάτω τμήμα μπορείτε να το βρείτε σε όλα τα βιβλία της θεωρίας πληροφοριών Τί είναι εντροπία μια πηγής πληροφορίας Υποθέτουμε ότι έχουμε μια πηγή πληροφορίας (έστω ένα αρχείο) με n διαφορετικά σύμβολα (στη γενική περίπτωση οχτάμπιτου αρχείου, μιλάμε για n=256 σύμβολα) όπου κάθε σύμβολο i=1..n έχει πιθανότητα εμφάνισης p(i) [στην πράξη απλώς υπολογίζουμε προσεγγιστικά τις πιθανότητες από της συχνότητα εμφάνισης πληθος συμβόλων i πρός συνολικό αριθμό συμβόλων του αρχείου] Εντροπία της πηγής πληροφορίας ορίζουμε το άθροισμα Η=-Σ p(i) log2 [p(i)] (το άθροισμα από 1 έως n) Το αποτέλεσμα έχει διαστάσεις bits/symbol Τι συμβολίζει αυτό ? Η εντροπία αποτελεί τον ελάχιστο αριθμό συμβόλων που μπορεί να παρασταθεί η παραπάνω πληροφορία. Δηλαδή, αν το για ένα αρχείο Η=2,7 bits/symbol σημαίνει ότι κανένας αλγόριθμος συμπόιεσης που στηρίζεται σε κωδικοποίηση εντροπίας, δεν είναι δυνατό να επιτύχει συμπίεση με μέσο αριθμό bits/symbol μικρότερο από το Η=2,7 Τώρα στο πρακτικό μέρος της υπόθεσης Ποιοι είναι οι καλύτεροι αλγόριθμοι συμπίεσης με κωδικοποίηση εντροπίας? Δύο αλγόριθμοι κυριαρχούν 1. Κωδικοποίηση κατα Huffman Με τον αλγόριθμο αυτό, παράγονται αναπαραστάσεις των αρχικών συμβόλων μεταβλητού μήκους με βάση ένα δυαδικό δέντρο που δημιουργείται σύμφωνα με την πιθανότητα εμφάνισης του κάθε συμβόλου. Έτσι τα σύμβολα με μεγαλύτερη πιθανότητα εμφάνισης αναπαριστώνται με λίγα bits και αντίστροφα Το τελικό αποτέλεσμα του αλγορίθμου εξαρτάται από τις πιθανότητες των συμβόλων και στη χειρότερη περίπτωση Huffman έχουμε μέσο μήκος λέξης Η+1 bits/symbol. (σημείωση ότι στους κώδικες με μεταβλητό μήκος το μέσο μήκος δεν είναι ακέραιο) Το αποτέλεσμα αυτό είναι καλό και ο αλγόριθμος του Huffman θεωρείτε ο καλύτερος αυτή τη στιγμή σε περιπτώσεις που η εντροπία δεν είναι μικρή (μικρή εντροπία συνήθως σημαίνει εντροπία κάτω από 5) 2. Υπάρχει ένας ακόμα αλγόριθμος στον οποίο το μέσο μήκος λέξης του τελικού κώδικα είναι ίσο με την εντροπία. Μιλάμε για την αριθμητική κωδικοποίηση Παρόλα αυτά ο αλγόριθμος αυτός χρησιμοποιείτε ελάχιστα και μόνο σε περιπτώσεις όπου ζητούμε την καλύτερη δυνατή συμπίεση σε δεδομένα με μικρή εντροπία (σκεφτείτε ότι αν η εντροπία είναι 2 και ο κώδικας Huffman μας δώσει μέσο μήκος 2,9 έχουμε περίσσεια πληροφορίας περίπου 45%) Ο λόγος του παραγκωνισμού του αλγορίθμου αυτού είναι η χρονική του πολυπλοκότητα. Είναι εξαιρετικά χρονοβόρος (όσοι έχετε Ματλαμπ, υπάρχει έτοιμη υλοποίηση, και δοκιμάστε να δέιτε) Πάμε τώρα λίγο πιο πέρα από την κλασσική θεωρία πληροφοριών Σε μερικές περιπτώσεις, όπως λχ οι εικόνες (άσχετο, αλλά οι εικόνες κατα JPEG δεν χρησιμοποιουν Φουριέ, αλλά διακριτό μετασχηματισμό συνημιτόνου, και μάλιστα μονοδιάστατο) ή ο ήχος, όπου η έντροπία είναι ήδη σε υψηλά επίπεδα, οι αλγόριθμοι αυτοί δεν επιτυγχάνουν σημαντική μείωση του μεγέθους. Εδώ τώρα έρχεται μια άλλη γκάμα αλγορίθμων (όπως το RLE, (A)DPCM κ.α.) οι οποίοι συνδυάζονται με τους προηγούμενους. Βασικός σκοπός των αλγορίθμων αυτών είναι η μείωση της εντροπίας. Πως θα γίνει αυτό ? Εδώ έρχονται οι πιθανότητες στην υπόθεση, και ένα μέγεθος που λέγεται αυτοσυσχέτιση. Οι αλγόριθμοι αυτοί κάνουν κάποια έξυπνα τρικάκια και μειώνουν την αυτοσυσχετιση, η οποία είναι σε άμεση σχέση με την εντροπία.(Αυτοσυσχέτιση μεγάλη σημαίνει ότι υπάρχει κάποια δυνατότητα πρόβλεψης, άρα περίσσεια πληροφορίας) Μια έξυπνη ιδέα είναι ο αλγόριθμος DPCM. Στον αλγόριθμο αυτό επιχειρείτε γραμμική πρόβλεψη του συμβόλου από 1,2,3 ή περισσότερα προηγούμενα σύμβολα (έστω κ). Έτσι στο τελικό αρχείου υπάρχουν τα κ πρώτα σύμβολα όπως είναι και κ+1 συντελεστές (οι οποίοι υπολογίζονται με βάση την αυτοσυσχέτιση σύμφωνα με την αρχή της ορθογωνιότητας του Παπούλη). Επειδή η πρόβλεψη δεν είναι ακριβής, ακολουθεί το σφάλμα, το οποίο αποδεδειγμένα έχει μικρότερη αυτοσυσχέτιση. Έτσι μειώνεται οι εντροπία. Ένας άλλος αλγόριθμος που αναφέρθηκε ήταν ο RLE(Run Length Encoding) Αυτος ο αλγόριθμος χρησιμοποιείται συμπληρωματικά. Χρησιμοποιείται μετά από μετασχηματισμούς, όπου υπάρχουν πολλά μηδενικα ανάμεσα στα σύμβολα.Τα σύμβολα που παράγει ο RLE είναι της μορφής (x,y) όπου x είναι το σύμβολο και y είναι ο αριθμός των μηδενικών που το ακολουθούν Ελπίζω να έλυσα κάποιες απορίες. Α! αν βρείτε κανένα έξυπνο τρόπο επιτάχυνσης της αριθμητικής κωδικοποίησης, plz inform me
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.