CCC '97 S4 - Dynamic Dictionary Coding

View as PDF
Submit solution
Points: 5
Time limit: 1.0s
Racket 2.0s
Memory limit: 256M
Problem type

A common method of data compression, dictionary coding, is to replace words in a text by numbers indicating their positions in a dictionary. Static dictionary coding, in which the dictionary is known in advance, can be problematic, as it is necessary to have the dictionary available to understand the coded text. Dynamic dictionary coding avoids this problem by deriving the dictionary from the text to be compressed. The text is processed from beginning to end, starting with an empty dictionary. Whenever a word is encountered that is in the dictionary, it is replaced by a number indicating its position in the dictionary. Whenever a word is encountered that is not in the dictionary, it appears as-is in the compressed text and is added to the end of the dictionary.

You are to implement dynamic dictionary coding.

Input Specification

The first line of the input contains a positive integer which is the number of sets of text which are to be compressed. Each set of text will consist of several lines containing text made of lowercase letters and spaces only. You may assume that no word is longer than 20 letters, that no input line is longer than 80 characters, and that there are no more than 100 input lines. Each set of text is terminated by a single blank line, and are to be compressed individually.

Output Specification

The output should contain the sets of text input compressed using dynamic dictionary coding as described above. Lineation and spacing should be preserved exactly as in the input with the different sets of compressed text separated by a single blank line. In particular, every empty line in the input should be matched with an empty line in the output.

Sample Input

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

Sample Output

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

Comments


  • 0
    PaulOlteanu  commented on Feb. 13, 2015, 4:29 a.m. ← edit 2

    Is it a problem with the way I read the input, or the way I'm printing?

    Input method:

    while True:
  temp = input()
  if len(temp) < 1:
    break;
  else:
    lines.append(temp)

    • 3
      moladan123  commented on April 22, 2016, 1:06 a.m. ← edit 2

      EOFError happens in python whenever you try to read a line when there isn't one. Try and read up on the try statement. Something like this:

      try:
    some code
except EOFError:
    pass

  • 3
    MathBunny  commented on Feb. 13, 2015, 12:03 a.m. ← edited

    How do you know when the program ends execution???


    • 2
      MathBunny  commented on Feb. 13, 2015, 12:03 a.m. ← edited

      In the sample input there is no blank space or anything !!


      • 2
        kobortor  commented on Feb. 13, 2015, 12:13 a.m. ← edited

        Each case will consist of several lines containing text made of lower case letters and spaces only and will be separated from next case by a single blank line.

        Just keep looping until you hit a blank line.