τρελή ιδέα για πρόγραμμα συμπίεσης

[Vasilisxd]

Παλιά είχα μια ιδέα για ένα πρόγραμμα συμπίεσης που ακόμα δεν μπορώ να καταλάβω που

βρίσκετε το σφάλμα στην σκέψη μου...

 

Ένα αρχείο είναι μια σειρά από μηδέν (0) και ένα (1). π.χ 1010000101010101000010101011010...κτλπ

Αυτό μεταφράζεται σε ένα αριθμό π.χ 2384498239017435734829...κτλπ.

Εάν αρχίσουμε να αφαιρούμε από αυτόν αριθμό/αρχείο - τον αριθμό π.χ 999.999.999.999.999.999

και μόλις τον αφαιρέσουμε π.χ 1 επτάκις φορές(και έχει φάει περίπου 20/30 γραμμές από το αρχείο), να σημειώνουμε τον αριθμό 1.

Έτσι θα ξέρουμε ότι από το αρχείο έχουμε αφαιρέσει τον αριθμό 999.999.999.999.999.999 ένα επτάκις φορές(ή όσες ορίσουμε εμείς)

και έχουμε σημειώσει μόνο έναν αριθμό , το 1.

Εάν επαναληφθεί αυτό αρκετές φορές , θα φτάσουμε να έχουμε σημειώσει πόσες φορές έγινε η αφαίρεση (μπορεί να γίνει και με διαίρεση)

σε ένα αρχείο και σε ένα άλλο να έχουμε το υπόλοιπο κομμάτι του αρχείου που δεν μπορεί να μειωθεί άλλο.

 

αυτά...

[antonl]

Κάποιες σκέψεις/απορίες.

Τα αρχεία δε νομίζω να τα βλέπει το λειτουργικό και συνεπώς το υποθετικό πρόγραμμα σαν 0 & 1.

Έστω όμως ότι ισχύει. Σκέψου πως έχεις ένα αρχείο 10MB. Το αρχείο που θα προκύψει με τον τρόπο συμπίεσης που αναφέρεις, δε νομίζω να χει σημαντικά μικρότερο μέγεθος.

[kagelos]

Το σκεπτικό σου εφαρμόζεται κατά κάποιον τρόπο σε αρκετούς τομείς. Π.χ. οι ημερομηνίες σε διάφορες πλατφόρμες είναι στην ουσία offset από μια συγκεκριμένη ημερομηνία. Δηλαδή έχουν π.χ. σαν πρώτη ημερομηνία την 1/1/1900 και στην συνέχεια οι ημερομηνίες εκφράζονται ως ticks (ας πούμε miliseconds) που πέρασαν από εκείνη την ημερομηνία. Αυτό γίνεται όμως για να διατηρηθεί ο τύπος σε ένα συγκεκριμένο μέγεθος (4 byte) και να είναι εύκολες οι πράξεις.

 

Για συμπίεση, αρχικά θα ήταν τεράστιο πρόβλημα το να αντιμετωπίζεις αστρονομικούς αριθμούς και να κάνεις πράξεις με αυτούς. Επιπλέον όσο κατεβαίνεις τάξεις μεγέθους στον αριθμό του αρχείου (αφαιρώντας), ανεβαίνεις στον αριθμό που κρατάς για να ξέρεις πόσες αφαιρέσεις έκανες. Άρα δεν συμπιέζεις.

 

Να σου πω το σκεπτικό σου με πιο απλό τρόπο. Έστω ότι το αρχείο είναι ο αριθμός 8524. Το διαιρείς με το 1000 και βγάζει πηλίκο 8 και υπόλοιπο 524. Έτσι εκφράζεται ως 1000 * 8 + 524. Πάνω κάτω αυτό λες. Θα δεις ότι δεν πέτυχα καμία συμπίεση.

 

Με λίγα λόγια ο αλγόριθμός σου δεν θα συμπίεζε ούτε ένα bit.

[Vasilisxd]

Με λίγα λόγια ο αλγόριθμός σου δεν θα συμπίεζε ούτε ένα bit.

 

:lol:

 

Ακόμα και αν διαιρούσα 99999999999 πεντάκις φορές το νούμερο με το 2 (εάν δεν ήταν μονός)

και αυτό το έκανα 999999999999999 πεντάκις φορές και τότε σημείωνα το 1

[tmjuju]

Δεν πρέπει να έχεις σχέση με πληροφορική

ούτε και με μαθηματικά

Αλλά μου έφτιαξες την ημέρα

Το αρχείο δεν είναι αριθμός αλλά αυτό δεν έχει μεγάλη σημασία… δοκίμασε να το κάνεις dryrun, λύσε το πρόβλημα έστω σε μια κόλλα χαρτί και θα καταλάβεις…

Η απόδειξη μενει στον αναγνώστη…

[kagelos]

@Vasilisxd : Αν διαιρούσες τον αριθμό με το 2, 999999 πεντάκις φορές, θα μειωνόταν ο ίδιος ο αριθμός προφανώς, αλλά θα έπρεπε να αποθηκεύεις και το 999999 πεντάκις ώστε να ξέρεις πόσες φορές πρέπει να πολλαπλασιάσεις ώστε να ξαναφτιάξεις το αρχείο. Άρα ότι κέρδισες μειώνοντας τον αριθμό, το χάνεις αποθηκεύοντας τον αριθμό που διαίρεσες. Αν από εκεί και πέρα πεις ότι το 99999 πεντάκις θα το κρατάω για όλα τα αρχεία μου μια φορά, μπορείς να πεις ότι κερδίζεις, αλλά ο ένας αυτός συγκεκριμένος αριθμός δεν κάνεις για όλα τα αρχεία. Αυτό γιατί π.χ. κάποια αρχεία θα είναι πολύ μικρότερα (άρα δεν θα μπορείς να διαιρείς) ή πολύ μεγαλύτερα.

 

@tmjuju : Μπορείς να μου πεις σε τι ακριβώς απαντάει το post σου και γιατί αυτό που κάνεις δεν είναι trolling; btw το αρχείο φυσικά και μπορεί να θεωρηθεί αριθμός. Απλά είναι τεράστιος.

[javavall]

Επιπλέον κάνοντας πράξεις με τόσο μεγάλους αριθμούς χάνεις σε ακρίβεια. Δεν θα έχεις το ίδιο νούμερο κάνοντας την αντίστροφη διαδικασία.

[kagelos]

Πως χάνεις σε ακρίβεια κάνοντας πράξεις με ακέραιους;

[javavall]

Αν διαιρούσες τον αριθμό με το 2, 999999 πεντάκις φορές...

 

Πόσα δεκαδικά ψηφία θα κράταγες? Επιπλέον σε κάθε ατελή διαίρεση το σφάλμα θα αυξάνεται.

[kagelos]

Ακέραια διαίρεση εννοείται, κρατώντας το υπόλοιπο.

[javavall]

Θα κράταγες τα υπόλοιπα όλων των διαιρέσεων? Δε θα ήταν συμπίεση αυτό.

[drm]

Εάν κοιτάξεις λίγο τις τάξεις των αριθμών που θα προκείπτουν θα δείς ότι δεν κερδίζεις τίποτα στην γενική περίπτωση.

[MiDi_MiLiZ]

Αν από εκεί και πέρα πεις ότι το 99999 πεντάκις θα το κρατάω για όλα τα αρχεία μου μια φορά, μπορείς να πεις ότι κερδίζεις, αλλά ο ένας αυτός συγκεκριμένος αριθμός δεν κάνεις για όλα τα αρχεία. Αυτό γιατί π.χ. κάποια αρχεία θα είναι πολύ μικρότερα (άρα δεν θα μπορείς να διαιρείς) ή πολύ μεγαλύτερα.

Φανταζομαι οτι μπορει να δημιουργηθει και ενας αλγοριθμος που πριν την συμπιεση να επιλεγει ποιος αριθμος ειναι ιδανικος για τη διαιρεση με το συγκεκριμενο αρχειο.

 

Δηλαδη χοντρικα, πριν το συμπιεσει, να διαβαζει το αρχειο, να το αντιστοιχει σε ενα νουμερο και επειτα να επιλεγει ενα μικροτερο του νουμερο για διαιρεση. Ο οποιος σιγα σιγα να τελειοποιηθει και να επιλεγει τον ιδανικοτερο αριθμο για διαιρεση ωστε να επιτυγχανει μεγιστη συμπιεση.

 

Ωστοσο θεωρω οτι υπαρχουν δυο αλλα προβληματα που ηδη αναφερθηκαν. Στη διαιρεση ειναι αυτο που λεει ο javaall, δηλαδη καθε διαιρεση θα εχει και υπολοιπο που θα πρεπει να αποθηκευεται, αρα παπαλα η συμπιεση. Οποτε η λυση ειναι η αφαιρεση.

 

Και στη περιπτωση αυτη υπαρχει προβλημα: οι πραξεις με αστρονομικα νουμερα οπως αρχικα αναφερθηκε.

 

Επειδη δεν εχω μεγαλη σχεση με τα προγραμματιστικα, οι σημερινοι αλγοριθμοι συμπιεσης πως λειτουργουν περιπου?

[NewProject]

>
Lossless compression is the following string:

25.888888888
 This string can be compressed as:

25.[9]8

 

απο wikipedia ( http://en.wikipedia.org/wiki/Data_compression )

[lion2486]

Φανταζομαι οτι μπορει να δημιουργηθει και ενας αλγοριθμος που πριν την συμπιεση να επιλεγει ποιος αριθμος ειναι ιδανικος για τη διαιρεση με το συγκεκριμενο αρχειο.

 

Δηλαδη χοντρικα, πριν το συμπιεσει, να διαβαζει το αρχειο, να το αντιστοιχει σε ενα νουμερο και επειτα να επιλεγει ενα μικροτερο του νουμερο για διαιρεση. Ο οποιος σιγα σιγα να τελειοποιηθει και να επιλεγει τον ιδανικοτερο αριθμο για διαιρεση ωστε να επιτυγχανει μεγιστη συμπιεση.

 

Ωστοσο θεωρω οτι υπαρχουν δυο αλλα προβληματα που ηδη αναφερθηκαν. Στη διαιρεση ειναι αυτο που λεει ο javaall, δηλαδη καθε διαιρεση θα εχει και υπολοιπο που θα πρεπει να αποθηκευεται, αρα παπαλα η συμπιεση. Οποτε η λυση ειναι η αφαιρεση.

 

Και στη περιπτωση αυτη υπαρχει προβλημα: οι πραξεις με αστρονομικα νουμερα οπως αρχικα αναφερθηκε.

 

Επειδη δεν εχω μεγαλη σχεση με τα προγραμματιστικα, οι σημερινοι αλγοριθμοι συμπιεσης πως λειτουργουν περιπου?

Ένας από τους αλγόριθμους συμπίεσης που έχω δει στη σχολή μου είναι ο LZW, ο οποίος λειτουργεί με τη δημιουργία ενός δέντρου για λεξικό. Στην ουσία καταγράφει ακολουθίες από bit και αν επαναλαμβάνονται απλά εκτυπώνεται πάλι ο αριθμός του λεξικού. Αν σε κάποιο σημείο δεν πραγματοποιείται συμπίεση με το υπάρχον λεξικό, τότε αρχικοποιείται και ξαναξεκινάει η διαδικασία. Το καλό είναι ότι δεν χρειάζεται να αποθηκευτεί το λεξικό, γιατί μπορεί να ξαναδημιουργηθεί κατά της αποσυμπίεση.