P10 - 游程编码
Run-length encoding of a list
官方模块:
Problems.P10核心函数:encode
← P09 将连续重复元素打包成子列表 | P11 改进的游程编码 →
← P09 将连续重复元素打包成子列表 | P11 改进的游程编码 →
题目描述
利用 P09 的 pack 函数实现游程编码（run-length encoding）：将连续重复的元素编码为 (元素, 出现次数) 元组。
函数签名
1encode :: Eq a => [a] -> [(Int, a)]
输出格式为 [(出现次数, 元素)]。
思路
题目明确提示用 P09 的 pack 来实现：
pack把连续重复元素打包成子列表- 对每个子列表，取其长度（出现次数）和第一个元素
- 组合成
(count, element)元组
实现
方法一：利用 pack
1encode :: Eq a => [a] -> [(Int, a)]
2encode xs = [(length group, head group) | group <- pack xs]
列表推导式：每个 group 来自 pack xs，取 length group 作为出现次数，head group 作为元素。
也可以用 map 写：
1encode :: Eq a => [a] -> [(Int, a)]
2encode = map (\group -> (length group, head group)) . pack
方法二：自己实现 pack + encode（不依赖外部函数）
1encode :: Eq a => [a] -> [(Int, a)]
2encode [] = []
3encode (x:xs) = let (group, rest) = span (== x) xs
4 in (1 + length group, x) : encode rest
不依赖 pack，直接用 span 边分组边编码。每步切分出与 x 相等的连续段，个数是 1 + length group。
方法三：使用 group 标准库
1import Data.List (group)
2
3encode :: Eq a => [a] -> [(Int, a)]
4encode = map (\g -> (length g, head g)) . group
Data.List.group 等价于 P09 的 pack。
编码与压缩
游程编码是数据压缩中最基础的方法。对于有大量连续重复的数据（如图像的二值化表示），压缩比非常可观：
1encode "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"
2-- [(12,'W'),(1,'B'),(12,'W'),(3,'B'),(24,'W'),(1,'B')]
12 个 ‘W’ 编码为 (12, 'W')，一个字符加一个整数，比存 12 个字符省得多。
测试
1>>> encode "aaaabccaadeeee"
2[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]
3
4>>> encode []
5[]
6
7>>> encode [1,1,2,2,2,3]
8[(2,1),(3,2),(1,3)]
9
10>>> encode "a"
11[(1,'a')]