Dynamic Dictionary Coding

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

1. Πρέπει να εφαρμόσετε δυναμική κωδικοποίηση λεξικού.

Είσοδος

Η πρώτη γραμμή του αρχείου εισόδου περιέχει έναν θετικό ακέραιο που είναι ο αριθμός των συνόλων κειμένου που πρόκειται να συμπιεστούν. Κάθε σύνολο κειμένου θα αποτελείται από πολλές γραμμές που θα περιέχουν μόνο κείμενο από πεζά γράμματα και κενά. Μπορείτε να υποθέσετε ότι καμία λέξη δεν είναι μεγαλύτερη από ~20~ γράμματα, ότι καμία γραμμή εισόδου δεν είναι μεγαλύτερη από ~80~ χαρακτήρες και ότι δεν υπάρχουν περισσότερες από ~100~ γραμμές εισόδου. Τα σύνολα κειμένου χωρίζονται με μία μόνο κενή γραμμή και συμπιέζονται ξεχωριστά.

Έξοδος

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

Παράδειγμα

input

1
the cat chased the rat while
the dog chased the cat into the rat house

output

the cat chased 1 rat while
1 dog 3 1 2 into 1 4 house

1. Όταν μια λέξη συναντάται για πρώτη φορά, γιατί προστίθεται στο λεξικό αλλά δεν κωδικοποιείται χρησιμοποιώντας τη νέα της θέση στο λεξικό;
2. Ας υποθέσουμε ότι το αρχείο εισόδου περιείχε αριθμούς καθώς και λέξεις. Εξηγήστε τη δυσκολία που θα προέκυπτε και προτείνετε μια αλλαγή στη μέθοδο που θα ξεπερνούσε τη δυσκολία.