3.5 示例：压缩 (Example: Compression)

作为一个例子，这节将演示如何实现简单形式的列表压缩。这个算法有一个令人印象深刻的名字，游程编码(run-length encoding)。

  1. (defun compress (x)
  2.   (if (consp x)
  3.       (compr (car x) 1 (cdr x))
  4.       x))
  6. (defun compr (elt n lst)
  7.   (if (null lst)
  8.       (list (n-elts elt n))
  9.       (let ((next (car lst)))
  10.         (if (eql next elt)
  11.             (compr elt (+ n 1) (cdr lst))
  12.             (cons (n-elts elt n)
  13.                   (compr next 1 (cdr lst)))))))
  15. (defun n-elts (elt n)
  16.   (if (> n 1)
  17.       (list n elt)
  18.       elt))

图 3.6 游程编码 (Run-length encoding)：压缩

在餐厅的情境下，这个算法的工作方式如下。一个女服务生走向有四个客人的桌子。“你们要什么？” 她问。“我要特餐，” 第一个客人说。 “我也是，” 第二个客人说。“听起来不错，” 第三个客人说。每个人看着第四个客人。 “我要一个 cilantro soufflé，” 他小声地说。 (译注：蛋奶酥上面洒香菜跟酱料）

瞬息之间，女服务生就转身踩着高跟鞋走回柜台去了。 “三个特餐，” 她大声对厨师说，“还有一个香菜蛋奶酥。”

图 3.6 展示了如何实现这个压缩列表演算法。函数 compress 接受一个由原子组成的列表，然后返回一个压缩的列表：

  1. > (compress '(1 1 1 0 1 0 0 0 0 1))
  2. ((3 1) 0 1 (4 0) 1)

当相同的元素连续出现好几次，这个连续出现的序列 (sequence)被一个列表取代，列表指明出现的次数及出现的元素。

主要的工作是由递归函数 compr 所完成。这个函数接受三个参数： elt ， 上一个我们看过的元素； n ，连续出现的次数；以及 lst ，我们还没检查过的部分列表。如果没有东西需要检查了，我们调用 n-elts 来取得 n elts 的表示法。如果 lst 的第一个元素还是 elt ，我们增加出现的次数 n 并继续下去。否则我们得到，到目前为止的一个压缩的列表，然后 cons 这个列表在 compr 处理完剩下的列表所返回的东西之上。

要复原一个压缩的列表，我们调用 uncompress (图 3.7)

  1. > (uncompress '((3 1) 0 1 (4 0) 1))
  2. (1 1 1 0 1 0 0 0 0 1)
  1. (defun uncompress (lst)
  2.   (if (null lst)
  3.       nil
  4.       (let ((elt (car lst))
  5.             (rest (uncompress (cdr lst))))
  6.         (if (consp elt)
  7.             (append (apply #'list-of elt)
  8.                     rest)
  9.             (cons elt rest)))))
  11. (defun list-of (n elt)
  12.   (if (zerop n)
  13.       nil
  14.       (cons elt (list-of (- n 1) elt))))

图 3.7 游程编码 (Run-length encoding)：解压缩

这个函数递归地遍历这个压缩列表，逐字复制原子并调用 list-of ，展开成列表。

  1. > (list-of 3 'ho)
  2. (HO HO HO)

我们其实不需要自己写 list-of 。内置的 make-list 可以办到一样的事情 ── 但它使用了我们还没介绍到的关键字参数 (keyword argument)。

图 3.6 跟 3.7 这种写法不是一个有经验的Lisp 程序员用的写法。它的效率很差，它没有尽可能的压缩，而且它只对由原子组成的列表有效。在几个章节内，我们会学到解决这些问题的技巧。

  1. 载入程序
  3. 在这节的程序是我们第一个实质的程序。
  4. 当我们想要写超过数行的函数时，
  5. 通常我们会把程序写在一个文件，
  6. 然后使用 load 让 Lisp 读取函数的定义。
  7. 如果我们把图 3.6 跟 3.7 的程序，
  8. 存在一个文件叫做，“compress.lisp”然后输入
  10. (load "compress.lisp")
  12. 到顶层，或多或少的，
  13. 我们会像在直接输入顶层一样得到同样的效果。
  15. 注意：在某些实现中，Lisp 文件的扩展名会是“.lsp”而不是“.lisp”。