old_contents: # http://rosettacode.org/wiki/LZW_compression#Python
  def decompress(compressed):
      """Decompress a list of output ks to a string."""
  
      # Build the dictionary.
      dict_size = 0x10000
      dictionary = dict((unichr(i), unichr(i)) for i in xrange(dict_size))
      # in Python 3: dictionary = {chr(i): chr(i) for i in range(dict_size)}
  
      w = result = compressed.pop(0)
      for k in compressed:
          if k in dictionary:
              entry = dictionary[k]
          elif k == dict_size:
              entry = w + w[0]
          else:
              raise ValueError('Bad compressed k: %s' % k)
          result += entry
  
          # Add w+entry[0] to the dictionary.
          dictionary[dict_size] = w + entry[0]
          dict_size += 1
  
          w = entry
      return result
new_contents: # http://rosettacode.org/wiki/LZW_compression#Python
  from cStringIO import StringIO
  
  
  def decompress(compressed):
      """Decompress a list of output ks to a string."""
  
      # Build the dictionary.
      dict_size = 0x10000
      dictionary = dict((unichr(i), unichr(i)) for i in xrange(dict_size))
      # in Python 3: dictionary = {chr(i): chr(i) for i in range(dict_size)}
  
      result = StringIO()
      w = compressed.pop(0)
      result.write(w)
      for k in compressed:
          if k in dictionary:
              entry = dictionary[k]
          elif k == dict_size:
              entry = w + w[0]
          else:
              raise ValueError('Bad compressed k: %s' % k)
          result.write(entry)
  
          # Add w+entry[0] to the dictionary.
          dictionary[dict_size] = w + entry[0]
          dict_size += 1
  
          w = entry
      return result.getvalue()
  
subject: use StringIO in LZW to make it not O(N^2)