(defun compress (input &aux res)
  (let ((next-code 256)
        (table (make-hash-table :test #'equal)))
    (dotimes (i 256) (setf (gethash (string (code-char i)) table) i))
    (let ((s (string (read-char input))))
      (loop
          (let ((c (read-char input nil :eof)))
            (when (eql :eof c)
              (return))
            (let ((sc (concatenate 'string s (string c))))
              (cond ((gethash sc table)
                     (setf s sc))
                    (t
                     (push (gethash s table) res)
                     (setf (gethash sc table) next-code)
                     (incf next-code)
                     (setf s (string c)))))))
      (push (or (gethash s table) s) res))
    (reverse res)))

(defun decompress (input)
  (let ((table (make-hash-table :test #'eql))
        (next-code 256))
    (dotimes (i 256) (setf (gethash i table) (string (code-char i))))
    (with-output-to-string (output)
      (let ((old-code (gethash (pop input) table)))
        (princ old-code output)
        (do ((new-code (pop input) (pop input)))
            ((null new-code))
          (let ((s (gethash new-code table
                            (concatenate 'string old-code
                                         (string (char old-code 0))))))
            (princ s output)
            (setf (gethash next-code table)
                  (concatenate 'string old-code (subseq s 0 1)))
            (incf next-code)
            (setf old-code s)))))))