Python 中的 RLE 介绍和加速代码-谢先斌的博客

Python 中的 RLE 介绍和加速代码

发布时间： 2025-10-04 更新时间： 2025-10-19 总字数：1197 阅读时间：3m 作者：谢先斌 IP上海

RLE（Run-Length Encoding）是一种简单且经典的无损数据压缩算法。它的核心思想是，对于一串连续出现多次的相同数据，用一个计数值和该数据本身来替代，从而达到压缩的目的。例如，字符串 “AAABBC” 经过 RLE 编码后可以表示为 “3A2B1C”。

RLE 的 Python 实现

一个简单的 RLE 编码函数可以使用循环来实现。它会遍历输入列表或字符串，统计连续相同元素的出现次数，并将结果存储在新的列表中。

def rle_encode(data):
    """
    一个简单的 RLE 编码实现。

    Args:
        data: 待编码的列表或字符串。

    Returns:
        一个包含 (计数, 元素) 元组的列表。
    """
    if not data:
        return []

    encoded = []
    count = 1
    for i in range(1, len(data)):
        if data[i] == data[i-1]:
            count += 1
        else:
            encoded.append((count, data[i-1]))
            count = 1
    encoded.append((count, data[-1]))
    return encoded

# 示例
data = "AAABBC"
encoded_data = rle_encode(data)
print(encoded_data) # 输出：[(3, 'A'), (2, 'B'), (1, 'C')]

这个简单的实现虽然直观，但对于大规模数据，其效率可能不是最优。

RLE 编码的加速方法

要提高 RLE 编码的性能，尤其是处理大型数据集时，可以使用一些更高级的 Python 特性或库。以下是几种常见的加速方法。

1. 使用 `itertools.groupby`

Python 的标准库 itertools 提供了一个名为 groupby 的函数，它可以将连续相同的元素分组。这非常适合用来实现高效的 RLE 编码。groupby 在内部使用 C 语言实现，因此性能通常比纯 Python 循环要快得多。

import itertools

def rle_encode_itertools(data):
    """
    使用 itertools.groupby 实现的 RLE 编码。
    """
    return [(sum(1 for _ in group), key) for key, group in itertools.groupby(data)]

# 示例
data = "AAABBCDDDD" * 1000
# 比较性能
import time
start_time = time.time()
rle_encode(data)
end_time = time.time()
print(f"简单循环版本耗时: {end_time - start_time:.6f} 秒")

start_time = time.time()
rle_encode_itertools(data)
end_time = time.time()
print(f"itertools.groupby 版本耗时: {end_time - start_time:.6f} 秒")

通常，itertools.groupby 版本的运行速度会比简单循环版本快一个数量级。

2. 使用 NumPy

如果你的数据是数值类型并且是 NumPy 数组，那么可以利用 NumPy 的向量化操作来进一步加速。通过查找相邻元素不相等的位置，我们可以高效地确定每个分组的边界。

import numpy as np

def rle_encode_numpy(x):
    """
    使用 NumPy 实现的 RLE 编码（适用于一维 NumPy 数组）。
    """
    if not isinstance(x, np.ndarray) or x.ndim != 1:
        raise ValueError("输入必须是一个一维 NumPy 数组。")

    # 查找相邻元素不相等的位置
    # np.where 返回一个元组，我们需要元组中的第一个元素
    diffs = np.where(x[1:] != x[:-1])[0] + 1

    # 将差异点的索引添加到数组的开始和结束
    starts = np.insert(diffs, 0, 0)
    ends = np.append(diffs, len(x))

    # 计算每个运行的长度
    lengths = ends - starts

    # 获取每个运行的值
    values = x[starts]

    return list(zip(lengths, values))

# 示例
data_np = np.array([1, 1, 1, 2, 2, 3])
encoded_np = rle_encode_numpy(data_np)
print(encoded_np) # 输出：[(3, 1), (2, 2), (1, 3)]

NumPy 版本特别适用于处理大型数值数组，因为它的操作在底层使用了优化的 C 或 Fortran 代码。

总结与建议

方法	优点	缺点	适用场景
简单循环	代码直观，易于理解和调试。	性能较慢，不适合大规模数据。	小规模数据，教学或快速原型开发。
`itertools.groupby`	性能优异，代码简洁，属于标准库。	可能会略微牺牲可读性。	绝大多数场景，特别是字符串或通用可迭代对象。
NumPy	对于数值数组性能极高。	需要安装 NumPy 库，不适用于字符串。	科学计算、数据分析、图像处理等领域的大型数值数组。

在实际应用中，对于大多数情况，推荐使用 itertools.groupby。它提供了一个完美的平衡：既高效，又不需要额外的依赖，并且代码简洁。如果你的数据是数值类型且需要极致性能，那么 NumPy 是一个非常好的选择。