为什么 liblzma 无法压缩任何随机字符串？
Why does liblzma fail to compress any random string?
我正在使用 ruby 绑定，ruby-xz。
random_string = SecureRandom.random_bytes(100)
compressed_string = XZ.compress(random_string, compression_level = 9, check = :none, extreme = true)
compressed_string.size # => always 148
我已经在不同长度的字符串上测试了一万次。
我知道至少有一半的字符串是 1-不可压缩的（不能压缩超过 1 位），3/4 的字符串是 2-不可压缩的，等等（这是从一个计数参数得出的。 ) 显然，这并没有说明可压缩字符串数量的下限，但肯定有一些，不是吗？
说明
有几个原因：
liblzma，当不处于 RAW 模式时，添加一个 header 描述字典大小和一些其他设置。这是它变大的原因之一。
LZMA 与许多其他压缩器一样，使用范围编码器以所需的最少位数对字典压缩的输出（本质上是 LZ77 的 badass 版本）进行编码。所以在比特流的末尾，最后的比特被填充成一个完整的字节。
您正在压缩随机噪声，正如您所指出的那样，它很难压缩。范围编码器试图找到最少的比特来编码字典压缩循环输出的符号。所以在这种情况下，会有很多符号。如果 LZMA 发现了一个（或两个）重复出现的模式，那么它可能最终只从输出中节省了一两个位。如第 2 点所述，您无法在字节级别观察。
实验
观察开销的一些小实验
原始模式下带有 lzma 的空文件：
$ dd if=/dev/urandom bs=1k count=0 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c
1
它至少需要一两个位来表示它到达了流的末尾，这被填充为一个字节
1k 文件充满零
$ dd if=/dev/zero bs=1k count=1 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c
19
很好，但从理论上讲复杂性，可能仍然有几个字节到很多（1000x'\0' 本来是最佳编码）
1k 个文件，所有位都为 1
$ dd if=/dev/zero bs=1k count=1 2>/dev/null | sed 's/\x00/\xFF/g'| xz -9 -e --format=raw -c 2>/dev/null | wc -c
21
有趣的是，xz 比全零压缩效果差一点。很可能与 LZMA 字典在位级别上工作的事实有关（这是 LZMA 的新颖想法之一）。
1k 随机文件：
$ dd if=/dev/urandom bs=1k count=1 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c
1028
所以比输入多了4个字节，还不错。
1k 随机文件的 1000 次运行：
$ for i in {1..1000}; do dd if=/dev/urandom bs=1k count=1 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c; done | sort | uniq -c
1000 1028
所以每次都需要 1028 个字节。
我正在使用 ruby 绑定，ruby-xz。
random_string = SecureRandom.random_bytes(100)
compressed_string = XZ.compress(random_string, compression_level = 9, check = :none, extreme = true)
compressed_string.size # => always 148
我已经在不同长度的字符串上测试了一万次。
我知道至少有一半的字符串是 1-不可压缩的（不能压缩超过 1 位），3/4 的字符串是 2-不可压缩的，等等（这是从一个计数参数得出的。 ) 显然，这并没有说明可压缩字符串数量的下限，但肯定有一些，不是吗？
说明
有几个原因：
liblzma，当不处于 RAW 模式时，添加一个 header 描述字典大小和一些其他设置。这是它变大的原因之一。
LZMA 与许多其他压缩器一样，使用范围编码器以所需的最少位数对字典压缩的输出（本质上是 LZ77 的 badass 版本）进行编码。所以在比特流的末尾，最后的比特被填充成一个完整的字节。
您正在压缩随机噪声，正如您所指出的那样，它很难压缩。范围编码器试图找到最少的比特来编码字典压缩循环输出的符号。所以在这种情况下，会有很多符号。如果 LZMA 发现了一个（或两个）重复出现的模式，那么它可能最终只从输出中节省了一两个位。如第 2 点所述，您无法在字节级别观察。
实验
观察开销的一些小实验
原始模式下带有 lzma 的空文件：
$ dd if=/dev/urandom bs=1k count=0 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c
1
它至少需要一两个位来表示它到达了流的末尾，这被填充为一个字节
1k 文件充满零
$ dd if=/dev/zero bs=1k count=1 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c
19
很好，但从理论上讲复杂性，可能仍然有几个字节到很多（1000x'\0' 本来是最佳编码）
1k 个文件，所有位都为 1
$ dd if=/dev/zero bs=1k count=1 2>/dev/null | sed 's/\x00/\xFF/g'| xz -9 -e --format=raw -c 2>/dev/null | wc -c
21
有趣的是，xz 比全零压缩效果差一点。很可能与 LZMA 字典在位级别上工作的事实有关（这是 LZMA 的新颖想法之一）。
1k 随机文件：
$ dd if=/dev/urandom bs=1k count=1 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c
1028
所以比输入多了4个字节，还不错。
1k 随机文件的 1000 次运行：
$ for i in {1..1000}; do dd if=/dev/urandom bs=1k count=1 2>/dev/null | xz -9 -e --format=raw -c 2>/dev/null | wc -c; done | sort | uniq -c
1000 1028
所以每次都需要 1028 个字节。