Κωδικοποίηση με LZ78

[bnvdarklord]

Έχω μια εργασία πάνω στο LZ78 και έχω κολλήσει στην κωδικοποίηση...

 

Μεχρι τώρα εχω φτιάξει την κατασκευη του λεξικού, και δεν ξερω πως με την βοήθεια του θα καταλήξω στο τελικό κωδικοποιημένο αρχείο.

 

Για παράδειγμα εχω στο αρχείο εισόδου το εξής

ΑΒΒΑΒΑΒ

Και το λεξικό που δημιουργείται:

1 Α (0,Α)

2 Β (0,Β)

3 ΒΑ (2,1)

4 ΒΑΒ (3, 2)

 

Εχω ψαξει αρκετά στο internet, αλλα οτι και να βρω που να εξηγεί τον αλγόριθμο σταματάει στο λεξικό...

 

Ευχαριστώ

[V.I.Smirnov]

Λάθος σου που ψάχνεις πρώτα στο Internet.

Για σοβαρή δουλειά πρώτα πρέπει να ψάχνεις στη βιβλιοθήκη.

 

Το βιβλίο "Τhe data compression book" 2nd ed. ,1995 Nelson δίνει εξηγήσεις και πλήρη κώδικα.

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

Αν βρεις το βιβλίο χωρίς τα sources στείλε μου μήνυμα να σου τα δώσω.

[bnvdarklord]

Εκανα αναζήτηση στο site της βιβλιοθηκης του πανεπιστημίου αλλα δεν το ειχε... Εχω την εντύπωση πάντως πως το χε παρει το ματι μου πριν κανα δύο βδομάδες που εψαχνα, θα παω την πεμπτη λογικά να δω...

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

[bnvdarklord]

Σκεφτηκα κατι για την κωδικοποίηση:

 

Εστω οτι εχουμε το κειμενο που λεω και στο αρχικό post ΑΒΒΑΒΑΒ... Αποθηκευω σε ενα binary αρχείο τους κωδικούς με τις αναφορές που έχω στο λεξικό δηλαδη για αυτο το αρχείο αποθηκευω 0Α0Β2Α3Β.

Το πρόβλημα ως τώρα είναι οτι στο αρχικό ascii αρχείο καθε χαρακτήρας πιάνει 1byte οποτε το αρχικό ειναι 7bytes, ενώ στο binary που φτιαχνω καθε codeword(πχ 0Α) πίανει 8bytes, οποτε τα αρχεία βγαίνουν μεγαλύτερα...

 

Είμαι σε καλό δρόμο, ή ειναι κατι απλούστερο που δεν παει το μυαλό μου;

 

edit: Δοκιμασα να αποθηκευω το ίδιο πράγμα σε ascii, οπου καθε χαρακτήρας πιάνει λιγότερο από οτι στο binary, αλλα για πολυ μεγάλα λεξικά μπορεί να υπάρξει πχ 5421Α και το 5421 που πιάνει 4 γράμματα να αναφέρεται στο ΚΛ που πιάνει μόλις 2...