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

[drm]

Έστω η ακαίρεα διαίρεση

Κ / Δ με πηλικό Π, και υπόλοιπο Υ.

 

(Στην ουσία οι διαδοχικές αφαιρέσεις που προτείνονται είναι μία διαίρεση.).

 

Εάν εξετάσουμε την τάξη του κάθε αριθμού (τάξη = πλήθος ψηφίων) τότε θα δούμε το εξής

 

Τάξη(Δ) + Ταξη(Π) ~= Τάξη(Κ) (Στην καλήτερυ περίπτωση). Και Τάξη(Υ) ~= Τάξη(Δ).

 

άρα προκείπτει ότι Τάξη(Υ) + Τάξη(Π) = Τάξη(Δ) + Τάξη(Κ) - Τάξη(Δ) =>

Τάξη(Υ) + Τάξη(Π) = Τάξη(Κ) άρα δεν έχεις κάνει κάμία συμπίεση.

 

Παράδειγμα

>
Κ = 11111 {Τάξη(κ) = 5}

Δ =  1000 => Π = 11, Y =  111 {Τάξη(Π) + Τάξη(Υ) = 5}.

Δ =  100 => Π = 111, Y =   11 {Τάξη(Π) + Τάξη(Υ) = 5}.

Δ = 11111 => Π = 1, Υ = 0 {Τάξη(Π) + Ταξη(Υ) = 2}. Φαινομενικά κερδίζεις χόρο 
ΑΛΛΑ 
είτε πρέπει να μεταφέρεις και το Δ οπότε χάνεις, ή πρέπει να έχεις έναν έξυπνο τρόπο να βρεις το Δ, χωρίς να ξέρεις το αρχικό νούμερο (καθώς μην ξεχνάς ότι όταν κάνεις αποκωδικοποίηση δεν έχεις το αρχικό νούμερο).

 

----

 

Γενικά συμπιέσης που δεν υποθέτουν τπτ για την δομή του αρχείου δεν γίνεται να δουλέψουν για τον εξής λόγο

Εάν είχα μία συμπίεση που μπορούσε να μειώσει ΟΠΟΙΟΔΗΠΟΤΕ αρχείο κατά 1byte τότε: θα μπορούσα να πάρω ένα αρχείο 1GB και να το συμπιέσω κάτα 1byte. Μετά να πάρω το αρχείο που θα προκύψει και να το ξανα-συμπιέσω κατά 1byte. Τελικά θα μπορούσα με 0 (ή 1) bytes να μεταφέρω όλη την πληροφορία του αρχείου κάτι που όπως καταλαβαίνεις είναι αδύνατο στην γενική περίπτωση.

 

Όλοι οι υπάρχοντες αλγόριθμοι συμπίεσης (μη-απωλεστικής) υποθέτους πράγματα για τα αρχεία (πχ επαναλαμβανόμενα τμήματα) και για αυτό δουλεύουν.

[Erevodifwntas]

Αυτό που λέει (αν το έπιασα σωστά) είναι ότι κάνω διαίρεση με μία constant (άρα την ξέρω και δε χρειάζεται να την αποθηκεύσω στο αρχείο), έστω το 1000 και συμπεριφέρομαι σε ολόκληρο το αρχείο σαν να ήταν ένα τεράστιο νούμερο (έστω το 100.000.002). Στη συνέχεια κάνω συνεχείς τέλειες διαιρέσεις, και σημειώνω για κάθε μία το 1. έτσι θα έχω:

 

100.000.002/1000 = 100.002 (και σημειώνω 1)

100.002/1000 = 1002 (και ξανασημειώνω 1)

1002/1000 = 2 (σημειώνω άλλο 1)

2/1000 = 2 (σημειώνω 0 -για να δηλώσω το τέλος της διαδικασίας- και μετά το υπόλοιπο, δηλαδή 2).

 

έτσι το αρχικό αρχείο ήταν: 100000002

ενώ το τελικό: 11102

 

Το πρόβλημα της ιδέας είναι ότι πρέπει να κρατάς και το πηλίκο, οπότε το μέγεθος του αρχείου αυξάνει και πάλι. αν και γενικά τέτοιοι μηχανισμοί χρησιμοποιούνται σε πολλούς αλγορίθμους συμπίεσης. Δεν ήταν τελείως off, απλά δεν ήταν τόσο καλός όσο φαίνεται στην αρχή. Αλλά είναι μία καλή πρώτη σκέψη (επειδή τον αποπήραμε τον άνθρωπο)

[kagelos]

Η αφαίρεση δεν είναι διαίρεση και ο Vasilisxd δεν μίλησε και διαίρεση. Εγώ το είπα για χάρη συντομίας.

 

Δεν θα χρειαζόταν να κρατάς "τα υπόλοιπα των διαιρέσεων". Μόνο ένα πηλίκο και ένα υπόλοιπο.

 

Erevodifwntas +1

Όπως είπα στο πρώτο μου post : Υπάρχει αυτό το σκεπτικό (offset) αλλά δεν κάνει για συμπίεση. Αυτό που διέφυγε στον Vasili είναι ότι πρέπει να αποθηκεύεται και ο "constant", ο οποίος δεν είναι κατάλληλος για όλα τα αρχεία και άρα πρέπει να αποθηκεύεται ξεχωριστά για καθένα.

[lion2486]

Έστω ότι πετυχαίνεται συμπίεση και ξαναέχουμε το αρχικό νούμερο, μήπως υπάρχουν άπειρες δυαδικές ακολουθίες με τέτοιο άθροισμα; πως θα παραχθεί πάλι η ίδια ακολουθία;

[Erevodifwntas]

Η αφαίρεση δεν είναι διαίρεση και ο Vasilisxd δεν μίλησε και διαίρεση. Εγώ το είπα για χάρη συντομίας.

 

Sorry!!!! το διάβασα πολύ στα πεταχτά το όλο concept

[PCharon]

Γενικά συμπιέσης που δεν υποθέτουν τπτ για την δομή του αρχείου δεν γίνεται να δουλέψουν για τον εξής λόγο

Εάν είχα μία συμπίεση που μπορούσε να μειώσει ΟΠΟΙΟΔΗΠΟΤΕ αρχείο κατά 1byte τότε: θα μπορούσα να πάρω ένα αρχείο 1GB και να το συμπιέσω κάτα 1byte. Μετά να πάρω το αρχείο που θα προκύψει και να το ξανα-συμπιέσω κατά 1byte. Τελικά θα μπορούσα με 0 (ή 1) bytes να μεταφέρω όλη την πληροφορία του αρχείου κάτι που όπως καταλαβαίνεις είναι αδύνατο στην γενική περίπτωση.

 

Όλοι οι υπάρχοντες αλγόριθμοι συμπίεσης (μη-απωλεστικής) υποθέτους πράγματα για τα αρχεία (πχ επαναλαμβανόμενα τμήματα) και για αυτό δουλεύουν.

^ Αυτό ακριβώς. Δε χρήζει περαιτέρω ανάλυσης.