LZW Compression

LZW compression replaces repeated phrases with numbers from a dictionary that it builds while it reads, so the dictionary itself never has to be sent: the reader can rebuild it. Write lzw_compress(text, max_size=4096) that returns the codes LZW produces for text, in order, as a list of integers.

The dictionary maps strings to codes. It starts with the 256 one-character strings: chr(i) has code i, for i from 0 to 255. Then, until the whole text is used:

• find the longest string in the dictionary that the rest of the text starts with, and output its code;
• if at least one character of the text follows that string, add the string plus that next character to the dictionary with the next free code (256 for the first new entry, then 257, and so on);
• move on past the string you output (the next character is not used up: it starts the next search).

The dictionary may hold at most max_size entries in total, the 256 starting ones included. Once it is full, nothing more is added, and compression carries on with the entries it already has. The empty text gives an empty list.

Examples

lzw_compress("ABABABA")       # returns [65, 66, 256, 258]
lzw_compress("aaaa")          # returns [97, 256, 97]
lzw_compress("ABABABA", 257)  # returns [65, 66, 256, 256, 65]

In the first example: A is output (65) and AB gets code 256; B is output (66) and BA gets 257; AB is output (256) and ABA gets 258; ABA is the rest of the text and is output (258). In the last example there is room for only one new entry, AB.

Constraints

• text has 0 to 100,000 characters, each with a code below 256.
• 256 <= max_size <= 100,000