Good questions.
You're right that the LZW codes could get big. You are allowed to limit the codes to 16 bits, which means a maximum code of 65,536. So, you can make sure your codes don't go beyond that, and if they do, it is OK for this assignment for your program to give up. (In real life, the program should flush the dictionary, insert a marker of some kind in the file, and then start again compressing the rest of the file with a new empty dictionary.)
You are right that since you would use 16 bits to store each code in the compressed file, a code of 0 or 1 takes up just as much space as a 16,543 or a 9,999. But for typical textfile input, you will still generally see some compression. And then furthermore, the resulting file will usually be highly compressible using Huffman compression. (It is extra credit to do the Huffman compression on the result of your LZW.)
This is essentially how the popular compression programs like gzip and WinZip work. |