Που μπορώ να βρώ πληροφορίες για τους LZ77 και LZ78?

[bnvdarklord]

Εχω ψαξει αρκετα στο google και εχω δει το αρθρο στο wikipedia, αλλα δεν εχω βρει πουθενα καποιο κειμενο που να περιγραφει την διαδικασία κωδικοποίησης με αυτούς τους αλγόριθμους ...

 

Μηπως ξερει κανεις καποια καλή σελίδα που να εξηγεί πληρως την διαδικασία?

[virxen75]

κάτι τέτοιο σου κάνει?

http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html

 

http://sites.google.com/site/compgt/lz77

 

http://www.binaryessence.com/dct/en000138.htm

[ee3509]

τα κάναμε στο MSc αυτά, δεν είναι εύκολο να το καταλάβεις αν δεν σου εξηγήσει με παράδειγμα κάποιος που το ξέρει

 

σε γενικές γραμμές φτιάχνει ενα dictionary στο οποίο αποθηκεύει patterns,

μετα όταν συναντάει τα patterns μέσα στο αρχείο τα αντικαθιστά με το offset στο οποίο έχει αποθηκεύσει το αρχικό pattern με το οποίο έχει κάνει match.

 

π.χ. αν τα θυμάμαι ακόμα λίγο έστω οτι έχουμε τη λέξη ΑΡΑΡΑΤ

 

τότε η συμπιεσμένη μορφή είναι κάπως ετσί : ΑΡ3ΑΤ

 

το οποίο όταν το κάνει deflate γίνεται : ΑΡ + ΑΡ στην θέση 3 + ΑΤ = ΑΡΑΡΑΤ

 

βέβαια στο συγκεκριμένο ένα byte γλυτώσαμε, δεν έγινε και τίποτα,

νομίζω όμως ότι έχει και τεχνικές partial match και overlapping για πιο ζόρικα κόλπα

 

για να πεις οτι το κατάλαβες πάντως θέλει και λίγο θεωρία πληροφορίας,

λίγο απο huffman, λίγο απο coding, λίγο απο error correction, έτσι για να "δέσει"

 

μάλλον κάνε ενα MSc να τα μάθεις

 

κάτι λέει και εδώ : http://marknelson.us/1989/10/01/lzw-data-compression/

[bnvdarklord]

κάτι τέτοιο σου κάνει?

[...]

 

Τα ειχα βρει αυτα, αλλα (αν καταλαβα σωστα) μετα την κατασκευη του λεξικου δεν λεει με πια λογικη αντικαθιστας τα patterns...(πχ στο 3ο pattern που ειναι το abc οπου abc βαζω το 3?) Και επισης για το ποσες φορες περνας το αρχειο για να φτιαξεις το λεξικο(λογικα μια αλλα νομιζω στην lzw περνας και 2η φορα? εχω ψιλομπερδευτει)

 

Ψαχνομαι γιατι το εχω να υλοποιησω το lz(77 ή 78) ως εργασία στο 2ο ετος....

 

edit:

 

π.χ. αν τα θυμάμαι ακόμα λίγο έστω οτι έχουμε τη λέξη ΑΡΑΡΑΤ

 

τότε η συμπιεσμένη μορφή είναι κάπως ετσί : ΑΡ3ΑΤ

 

 

Ισως δεν το εχω καταλαβει σωστα, αλλα η συμπιεση δεν θα ηταν 33ΑΤ?

[V.I.Smirnov]

Ένα βιβλίο που περιγράφει τον αλγόριθμο LZ78 με κώδικα είναι το "Τhe data compression book." , 2nd edition, 1995.

Κάπως παλιό αλλά αναπτύσσει πολλούς αλγόριθμους συμπίεσης δίνοντας κώδικα. Τα προγράμματα που δίνει είναι σε C.

Δυστυχώς, για κάποιους αλγόριθμους δεν μπορεί να δώσει εμπορικό κώδικα επειδή είναι κατοχυρωμένες πατέντες αλλά και αυτό που δίνει δουλεύει.

Έχει μάλιστα και ένα κεφάλαιο για συμπίεση εικόνας με fractal τεχνικές.

 

Υπάρχουν και πολλά άλλα πιο καινούρια βιβλία που μελετούν το θέμα σε έκταση και βάθος που ποικίλει.

Κάποια δίνουν και κώδικα.

Για σοβαρή δουλειά πρέπει να στραφείς στην βιβλιογραφία. Μόνον με το διαδίκτυο είναι ημίμετρα....

[ee3509]

 

Ισως δεν το εχω καταλαβει σωστα, αλλα η συμπιεση δεν θα ηταν 33ΑΤ?

 

Οχι γιατι φτιάχνει το dictionary σε πραγματικό χρόνο καθώς σαρώνει την είσοδο. Ομως αυτό που σου είπα είναι στο περίπου ούτως ή άλλος, ψάξε μήπως βρείς απο κανενα uni σημειώσεις του μαθήματος data compression σε μεταπτυχιακο

[Evgenios1]

Τωρα που εψαχνα κατι subtitles βρηκα αυτο .

LZW_src.zip

[bnvdarklord]

Σε ευχαριστώ, αλλα αυτός ειναι ο LZW, ενω εγω θελω ειτε τον LZ77 ή τον LZ78... Εξαλλου το να το παρω ετοιμο δεν ειναι και η καλυτερη λυση... Θα παω την δευτερα στην βιβλιοθηκη του πανεπιστημιου να δω τι μπορω να βρω.....