Dynamic Dictionary Coding

A common method of data compression, called dictionary coding, replaces words in a text with numbers that indicate their positions in a dictionary. Static dictionary coding, where the dictionary is fixed in advance, can be inconvenient: you must already have the dictionary on hand to decode the text. Dynamic dictionary coding avoids this by building the dictionary from the text being compressed.

The text is processed from beginning to end, starting with an empty dictionary. Each word is handled in order:

• If the word is already in the dictionary, it is replaced by a number giving its position in the dictionary (positions are numbered from 1 in the order words were added).
• If the word is not yet in the dictionary, it is written unchanged in the compressed output and appended to the end of the dictionary.

Implement dynamic dictionary coding.

The first line contains a positive integer: the number of text sets to compress.

Each text set consists of one or more lines of text containing only lowercase letters and spaces. No word is longer than 20 letters, no line is longer than 80 characters, and no set has more than 100 lines. Consecutive text sets are separated by a single blank line, and each set is compressed independently (every set starts from an empty dictionary).

Output each text set after compressing it with dynamic dictionary coding. Preserve line breaks and spacing exactly as in the input, and separate the compressed sets with a single blank line.

When a word is encountered for the first time, why is it added to the dictionary but written out unchanged, instead of being encoded with its newly assigned position?

Suppose the input could also contain numbers as well as words. Explain the difficulty this would cause, and suggest a change to the method that would overcome it.