Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Giới hạn nén: entropy, đếm chuỗi và chọn codec theo phép đo

Câu hỏi bài này trả lời: dữ liệu nén được đến mức nào, vì sao không codec nào nén được mọi đầu vào, và các codec trong thư viện chuẩn của Python (zlib, bz2, lzma, zstd) đánh đổi kích thước và tốc độ ra sao trên dữ liệu cụ thể?

Cần biết trước: Python cơ bản và logarit cơ số 2. Lab dùng thư viện chuẩn của Python 3.14.4 (zlib 1.2.12, bz2, lzma và compression.zstd với libzstd 1.5.7) trên macOS arm64, với chuỗi giả tự sinh và mã nguồn của chính thư viện chuẩn. Tài liệu Python ghi compression.zstd là module tùy chọn; bản Python thiếu nó thì bỏ các dòng zstd. Thời gian là của một máy: chỉ thứ tự và tỉ lệ gấp bội đáng đọc, không phải con số tuyệt đối.

Hai giới hạn khác nhau

Giới hạn đếm. Có 2^n chuỗi dài đúng n bit nhưng chỉ có 1 + 2 + … + 2^(n−1) = 2^n − 1 chuỗi ngắn hơn. Một cách nén không mất dữ liệu phải gán cho mỗi đầu vào một đầu ra riêng, nên không thể rút ngắn mọi chuỗi n bit: ít nhất một chuỗi không ngắn đi. Mạnh hơn, chỉ có 2^(n−k+1) − 1 chuỗi dài tối đa n−k bit, nên tỉ lệ chuỗi n bit có thể rút bớt ít nhất k bit nhỏ hơn 2^−(k−1): dưới 0,8% với k = 8 (một byte), dưới 0,004% với k = 16. Đây là phép đếm, không phụ thuộc cách viết codec.

Giới hạn entropy (Shannon 1948). Với nguồn phát các ký hiệu độc lập, ký hiệu i có xác suất p_i, entropy là H = −Σ p_i · log₂ p_i bit mỗi ký hiệu. Bài báo của Shannon chứng minh (định lý 9) rằng có thể mã hóa để số bit trung bình tiến tới H với sai khác nhỏ tùy ý, và không thể thấp hơn. Ví dụ trong chính bài báo: nguồn bốn chữ cái A, B, C, D với xác suất 1/2, 1/4, 1/8, 1/8 có H = 7/4 bit mỗi ký hiệu, và mã 0, 10, 110, 111 đạt đúng trung bình 7/4. Entropy phụ thuộc mô hình của nguồn: Shannon ghi rằng một máy sinh các chữ số của π cho ra một dãy xác định, không có yếu tố ngẫu nhiên, và tiếng Anh thường có độ dư thừa khoảng 50% khi chỉ tính cấu trúc thống kê trong khoảng tám chữ cái. Vì vậy entropy bậc 0 của byte (chỉ đếm tần suất từng byte) là giới hạn cho nguồn có các byte độc lập; dữ liệu có cấu trúc đi xuống thấp hơn nhiều.

zlib và gzip dùng định dạng DEFLATE, mà RFC 1951 mô tả là kết hợp thuật toán LZ77 với mã Huffman, và có khối lưu nguyên (BTYPE = 00) giới hạn 65.535 byte cho dữ liệu không nén được. Bài không mô tả cấu tạo bên trong của bz2, lzma và zstd.

Lab: các hàm dùng chung

Tạo thư mục trống rồi lưu corpus.py. Mẫu văn bản là mã nguồn Python của 23 module thư viện chuẩn (xác định trong một bản Python), entropy() là entropy bậc 0 của chính mẫu, và size_with() kiểm mỗi lần nén đều giải nén ra đúng dữ liệu gốc.

import bz2
import importlib
import inspect
import lzma
import math
import zlib
from collections import Counter

from compression import zstd

MODULES = [
    "argparse", "ast", "collections", "dataclasses", "enum", "functools", "inspect",
    "json.decoder", "logging", "os", "pathlib", "re._parser", "shutil", "socket",
    "subprocess", "tarfile", "typing", "zipfile", "http.client", "urllib.request",
    "email.message", "unittest.case", "random",
]

CODECS = {
    "zlib-9": (lambda data: zlib.compress(data, 9), zlib.decompress),
    "bz2-9": (lambda data: bz2.compress(data, 9), bz2.decompress),
    "lzma-6": (lambda data: lzma.compress(data, preset=6), lzma.decompress),
    "zstd-3": (lambda data: zstd.compress(data, level=3), zstd.decompress),
    "zstd-19": (lambda data: zstd.compress(data, level=19), zstd.decompress),
}


def text_sample() -> bytes:
    """Mã nguồn Python của vài module thư viện chuẩn: văn bản thật, xác định trong một bản Python."""
    return b"".join(inspect.getsource(importlib.import_module(name)).encode() for name in MODULES)


def entropy(data: bytes) -> float:
    """Entropy bậc 0 (bit mỗi byte) của chính mẫu này."""
    counts = Counter(data)
    total = len(data)
    return -sum(c / total * math.log2(c / total) for c in counts.values())


def size_with(name: str, data: bytes) -> int:
    compress, decompress = CODECS[name]
    packed = compress(data)
    assert decompress(packed) == data
    return len(packed)

python3 -B -c "import corpus; print('OK', len(corpus.text_sample()))"

Lab: đếm chuỗi và dữ liệu ngẫu nhiên

Phần đầu liệt kê thật các chuỗi ngắn hơn n bit (với n đến 16) và so với 2^n, rồi tính cận tỉ lệ cho chuỗi 8.000 bit. Phần hai nén 2.000 chuỗi ngẫu nhiên dài 1.000 byte bằng năm cấu hình và đếm xem chuỗi nào nhỏ đi; lab dừng nếu có một chuỗi nhỏ đi.

import itertools
import random
import statistics
from fractions import Fraction

from corpus import CODECS, size_with

print("== Đếm chuỗi")
for n in (1, 2, 3, 8, 16):
    strings = 2**n
    shorter = sum(len(list(itertools.product("01", repeat=length))) for length in range(n))
    print(f"n={n:2}: {strings} chuỗi dài {n} bit nhưng chỉ có {shorter} chuỗi ngắn hơn: thiếu {strings - shorter}")
    assert shorter == strings - 1

BITS = 8000
print(f"tỉ lệ tối đa chuỗi {BITS} bit có thể nén bớt ít nhất k bit (cận 2^-(k-1)):")
for k in (1, 8, 16, 80):
    bound = Fraction(2 ** (BITS - k + 1) - 1, 2**BITS)
    print(f"  k={k:2}: tối đa {float(bound):.3e}")
    assert bound < Fraction(1, 2 ** (k - 1)) or k == 1
    assert bound < 1

print("== Chuỗi ngẫu nhiên 1000 byte")
rng = random.Random(9)
samples = [rng.randbytes(1000) for _ in range(2000)]
for name in CODECS:
    sizes = [size_with(name, data) for data in samples]
    shrunk = sum(size < 1000 for size in sizes)
    print(f"{name}: {shrunk}/2000 chuỗi nhỏ đi; kích thước trung bình {statistics.fmean(sizes):.1f}, nhỏ nhất {min(sizes)}")
    assert shrunk == 0
print("không codec nào làm nhỏ chuỗi ngẫu nhiên; đếm chuỗi khớp số đo")

python3 -B counting.py

== Đếm chuỗi
n= 1: 2 chuỗi dài 1 bit nhưng chỉ có 1 chuỗi ngắn hơn: thiếu 1
n= 2: 4 chuỗi dài 2 bit nhưng chỉ có 3 chuỗi ngắn hơn: thiếu 1
n= 3: 8 chuỗi dài 3 bit nhưng chỉ có 7 chuỗi ngắn hơn: thiếu 1
n= 8: 256 chuỗi dài 8 bit nhưng chỉ có 255 chuỗi ngắn hơn: thiếu 1
n=16: 65536 chuỗi dài 16 bit nhưng chỉ có 65535 chuỗi ngắn hơn: thiếu 1
tỉ lệ tối đa chuỗi 8000 bit có thể nén bớt ít nhất k bit (cận 2^-(k-1)):
  k= 1: tối đa 1.000e+00
  k= 8: tối đa 7.812e-03
  k=16: tối đa 3.052e-05
  k=80: tối đa 1.654e-24
== Chuỗi ngẫu nhiên 1000 byte
zlib-9: 0/2000 chuỗi nhỏ đi; kích thước trung bình 1011.0, nhỏ nhất 1011
bz2-9: 0/2000 chuỗi nhỏ đi; kích thước trung bình 1292.3, nhỏ nhất 1249
lzma-6: 0/2000 chuỗi nhỏ đi; kích thước trung bình 1060.0, nhỏ nhất 1060
zstd-3: 0/2000 chuỗi nhỏ đi; kích thước trung bình 1010.0, nhỏ nhất 1010
zstd-19: 0/2000 chuỗi nhỏ đi; kích thước trung bình 1010.0, nhỏ nhất 1010
không codec nào làm nhỏ chuỗi ngẫu nhiên; đếm chuỗi khớp số đo

Đọc kết quả:

  • Luôn thiếu đúng một chuỗi. Ở mọi n có 2^n chuỗi nhưng chỉ 2^n − 1 chuỗi ngắn hơn, nên một cách nén không mất dữ liệu không thể rút ngắn tất cả. Cận cho chuỗi 8.000 bit: tỉ lệ chuỗi nén bớt được ít nhất một byte nhỏ hơn 0,78%, ít nhất hai byte nhỏ hơn 0,003%, ít nhất mười byte nhỏ hơn 10⁻²³.
  • Đầu vào ngẫu nhiên chỉ có thể phình ra. Không chuỗi nào trong 2.000 chuỗi ngẫu nhiên 1.000 byte nhỏ đi ở cả năm cấu hình. Chi phí cố định khác nhau nhiều: thêm khoảng 10 byte (zstd), 11 byte (zlib), 60 byte (lzma) và khoảng 292 byte (bz2, gần 30% với chuỗi ngắn như vậy). Con số 11 byte của zlib khớp với một khối lưu nguyên (5 byte đầu khối) cộng phần đầu và phần cuối của định dạng zlib.

Lab: entropy của nguồn và các codec

Lab sinh bốn nguồn độc lập, mỗi nguồn 1.000.000 ký hiệu (mỗi ký hiệu một byte): nguồn dyadic bốn ký hiệu của ví dụ Shannon, nguồn nhị phân lệch 0,9/0,1, nguồn đều 16 ký hiệu và nguồn đều 256 ký hiệu. Với mỗi nguồn, lab in entropy lý thuyết H, entropy của chính mẫu và số bit mỗi ký hiệu mà từng cấu hình đạt được. Lab dừng nếu có cấu hình nào đạt thấp hơn 99,5% entropy của mẫu, hoặc nếu mã 0/10/110/111 không cho đúng trung bình bằng H.

import math
import random

from corpus import CODECS, entropy, size_with

N = 1_000_000
SOURCES = {
    "dyadic 4 ký hiệu (1/2, 1/4, 1/8, 1/8)": ([0, 1, 2, 3], [0.5, 0.25, 0.125, 0.125]),
    "nhị phân lệch 0,9/0,1": ([0, 1], [0.9, 0.1]),
    "đều 16 ký hiệu": (list(range(16)), [1 / 16] * 16),
    "đều 256 ký hiệu": (list(range(256)), [1 / 256] * 256),
}

dyadic = SOURCES["dyadic 4 ký hiệu (1/2, 1/4, 1/8, 1/8)"][1]
code_lengths = [1, 2, 3, 3]
average = sum(p * length for p, length in zip(dyadic, code_lengths))
h = -sum(p * math.log2(p) for p in dyadic)
print(f"mã 0/10/110/111 cho trung bình {average} bit mỗi ký hiệu, entropy H = {h}")
assert average == h == 1.75

rng = random.Random(5)
for name, (symbols, weights) in SOURCES.items():
    data = bytes(rng.choices(symbols, weights=weights, k=N))
    h = -sum(p * math.log2(p) for p in weights)
    h_sample = entropy(data)
    row = {codec: 8 * size_with(codec, data) / N for codec in CODECS}
    cells = " ".join(f"{codec} {value:.4f}" for codec, value in row.items())
    print(f"{name}: H = {h:.4f}, entropy của mẫu {h_sample:.4f} | {cells}")
    assert all(value >= 0.995 * h_sample for value in row.values())
    best_codec = min(row, key=row.__getitem__)
    print(f"    tốt nhất {best_codec} {row[best_codec]:.4f} bit mỗi ký hiệu = {row[best_codec] / h:.3f} lần H")
print("không codec nào xuống dưới entropy của nguồn")

python3 -B entropy.py

mã 0/10/110/111 cho trung bình 1.75 bit mỗi ký hiệu, entropy H = 1.75
dyadic 4 ký hiệu (1/2, 1/4, 1/8, 1/8): H = 1.7500, entropy của mẫu 1.7492 | zlib-9 2.1045 bz2-9 2.0604 lzma-6 1.9605 zstd-3 2.2887 zstd-19 1.7579
    tốt nhất zstd-19 1.7579 bit mỗi ký hiệu = 1.005 lần H
nhị phân lệch 0,9/0,1: H = 0.4690, entropy của mẫu 0.4687 | zlib-9 0.6522 bz2-9 0.5746 lzma-6 0.5767 zstd-3 0.9991 zstd-19 0.5817
    tốt nhất bz2-9 0.5746 bit mỗi ký hiệu = 1.225 lần H
đều 16 ký hiệu: H = 4.0000, entropy của mẫu 4.0000 | zlib-9 4.5590 bz2-9 4.0689 lzma-6 4.1589 zstd-3 4.1475 zstd-19 4.0095
    tốt nhất zstd-19 4.0095 bit mỗi ký hiệu = 1.002 lần H
đều 256 ký hiệu: H = 8.0000, entropy của mẫu 7.9998 | zlib-9 8.0025 bz2-9 8.0393 lzma-6 8.0009 zstd-3 8.0003 zstd-19 8.0003
    tốt nhất zstd-3 8.0003 bit mỗi ký hiệu = 1.000 lần H
không codec nào xuống dưới entropy của nguồn

Đọc kết quả:

  • Không codec nào xuống dưới entropy. Ở cả bốn nguồn, mọi cấu hình đều đạt từ entropy của mẫu trở lên, đúng phần ngược của định lý 9. Entropy của mẫu lệch khỏi H lý thuyết dưới 0,1% vì mẫu dài một triệu ký hiệu.
  • Tiến tới entropy có điều kiện. Ở nguồn đều 256 ký hiệu (không có gì để nén) tốt nhất là 1,000 lần H; ở nguồn đều 16 ký hiệu và nguồn dyadic, zstd mức 19 chỉ cao hơn H khoảng 0,2% và 0,5%. Cùng nguồn dyadic mà zlib mức 9 đạt 2,10 bit, tức cao hơn H khoảng 20%: bộ tìm chuỗi lặp của LZ77 tìm ra các khớp ngẫu nhiên trong dãy chỉ có bốn ký hiệu, và mỗi khớp tốn nhiều bit hơn mã từng ký hiệu (diễn giải từ số đo, bài không đọc mã nguồn zlib).
  • Nguồn lệch bộc lộ giới hạn của từng codec. Với nguồn nhị phân 0,9/0,1 (H = 0,469), không cấu hình nào dưới 0,574 bit, tức cao hơn 22,5%. zstd mức 3 đạt 0,999 bit mỗi ký hiệu: khớp với giới hạn “không dùng ít hơn 1 bit cho mỗi ký hiệu” của mã Huffman trên nguồn hai ký hiệu (bài không kiểm cấu tạo bên trong của zstd). Ví dụ thứ hai trong bài Shannon nói về đúng tình huống này (nguồn hai ký hiệu có một ký hiệu rất hiếm) và mô tả mã hóa theo đoạn giữa hai lần ký hiệu hiếm xuất hiện, thay vì mã từng ký hiệu.

Lab: loại dữ liệu

Bốn loại dữ liệu: 1 MB byte ngẫu nhiên, 300 KB là chuỗi abc lặp lại, mã nguồn Python (khoảng 1,5 MB) và chính mã nguồn đó sau khi nén bằng lzma. Lab in số bit mỗi byte của từng cấu hình và dừng nếu: dữ liệu ngẫu nhiên hay dữ liệu đã nén không phình trong khoảng 0 đến 1%; chuỗi lặp không nhỏ hơn 0,2% kích thước gốc; mã nguồn không đạt dưới entropy bậc 0.

import lzma
import random

from corpus import CODECS, entropy, size_with, text_sample

rng = random.Random(3)
DATA = {
    "ngẫu nhiên 1 MB": rng.randbytes(1_000_000),
    "'abc' lặp 300 KB": b"abc" * 100_000,
    "mã nguồn Python": text_sample(),
}
DATA["mã nguồn nén lzma"] = lzma.compress(DATA["mã nguồn Python"], preset=6)

sizes: dict[str, dict[str, int]] = {}
for label, data in DATA.items():
    h0 = entropy(data)
    sizes[label] = {codec: size_with(codec, data) for codec in CODECS}
    cells = " ".join(f"{codec} {8 * size / len(data):.3f}" for codec, size in sizes[label].items())
    print(f"{label:20} {len(data):>9} byte, H0 {h0:5.3f} bit/byte | bit/byte: {cells}")

for label in ("ngẫu nhiên 1 MB", "mã nguồn nén lzma"):
    n = len(DATA[label])
    assert all(n < size < 1.01 * n for size in sizes[label].values()), label
assert all(size < 0.002 * 300_000 for size in sizes["'abc' lặp 300 KB"].values())
text_h0 = entropy(DATA["mã nguồn Python"])
assert all(8 * size / len(DATA["mã nguồn Python"]) < text_h0 for size in sizes["mã nguồn Python"].values())
print("ngẫu nhiên và đã nén thì phình nhẹ; dữ liệu có cấu trúc xuống dưới entropy bậc 0")

python3 -B kinds.py

ngẫu nhiên 1 MB        1000000 byte, H0 8.000 bit/byte | bit/byte: zlib-9 8.003 bz2-9 8.039 lzma-6 8.001 zstd-3 8.000 zstd-19 8.000
'abc' lặp 300 KB        300000 byte, H0 1.585 bit/byte | bit/byte: zlib-9 0.008 bz2-9 0.001 lzma-6 0.005 zstd-3 0.001 zstd-19 0.001
mã nguồn Python        1557776 byte, H0 4.444 bit/byte | bit/byte: zlib-9 1.927 bz2-9 1.591 lzma-6 1.590 zstd-3 2.029 zstd-19 1.611
mã nguồn nén lzma       309516 byte, H0 7.999 bit/byte | bit/byte: zlib-9 8.003 bz2-9 8.047 lzma-6 8.002 zstd-3 8.000 zstd-19 8.000
ngẫu nhiên và đã nén thì phình nhẹ; dữ liệu có cấu trúc xuống dưới entropy bậc 0

Đọc kết quả:

  • Dữ liệu ngẫu nhiên và dữ liệu đã nén không nén thêm được. Byte ngẫu nhiên và bản lzma của mã nguồn đều có entropy bậc 0 gần 8 bit mỗi byte, và mọi cấu hình đều đưa ra 8,000 đến 8,047 bit mỗi byte, tức phình thêm 0,003% đến 0,6%. Nén hai lần chỉ tốn thêm thời gian và làm tệp phình thêm tới 0,6%. Ảnh JPEG, video và tệp đã mã hóa thuộc loại này (lập luận, bài không đo các định dạng đó).
  • Entropy bậc 0 không phải giới hạn của dữ liệu có cấu trúc. Chuỗi abc lặp có entropy bậc 0 là 1,585 bit mỗi byte nhưng chỉ còn khoảng 0,001 đến 0,008 bit mỗi byte sau khi nén (dưới 320 byte cho 300 KB), vì nó sinh ra từ một luật một dòng chứ không phải từ các byte độc lập; đây là ý của ví dụ chữ số π trong bài Shannon. Mã nguồn Python có entropy bậc 0 là 4,44 bit mỗi byte nhưng nén xuống 1,59 đến 2,03 bit mỗi byte, vì có nhiều cấu trúc lặp (diễn giải: tên hàm, thụt lề, cú pháp).

Lab: kích thước và tốc độ

Lab nén mẫu mã nguồn Python 1,5 MB bằng mười một cấu hình (zlib mức 1, 6, 9; bz2 mức 1, 9; lzma preset 0, 6; zstd mức 1, 3, 9, 19), lấy thời gian nhỏ nhất trong 5 lần đo, và dừng nếu: có lần giải nén không ra đúng dữ liệu gốc; mức cao hơn của cùng codec cho kết quả lớn hơn; lzma preset 6 hoặc zstd mức 19 không nhỏ hơn zlib mức 9; zstd mức 3 không nhanh hơn lzma preset 6 ít nhất 5 lần khi nén; hoặc có cài đặt zlib nằm trên biên không bị thống trị theo (kích thước, thời gian nén).

import bz2
import lzma
import time
import zlib

from compression import zstd
from corpus import text_sample

SETTINGS = [
    ("zlib-1", lambda d: zlib.compress(d, 1), zlib.decompress),
    ("zlib-6", lambda d: zlib.compress(d, 6), zlib.decompress),
    ("zlib-9", lambda d: zlib.compress(d, 9), zlib.decompress),
    ("bz2-1", lambda d: bz2.compress(d, 1), bz2.decompress),
    ("bz2-9", lambda d: bz2.compress(d, 9), bz2.decompress),
    ("lzma-0", lambda d: lzma.compress(d, preset=0), lzma.decompress),
    ("lzma-6", lambda d: lzma.compress(d, preset=6), lzma.decompress),
    ("zstd-1", lambda d: zstd.compress(d, level=1), zstd.decompress),
    ("zstd-3", lambda d: zstd.compress(d, level=3), zstd.decompress),
    ("zstd-9", lambda d: zstd.compress(d, level=9), zstd.decompress),
    ("zstd-19", lambda d: zstd.compress(d, level=19), zstd.decompress),
]
REPEATS = 5


def best_time(fn, argument) -> float:
    best = float("inf")
    for _ in range(REPEATS):
        start = time.perf_counter()
        fn(argument)
        best = min(best, time.perf_counter() - start)
    return best


data = text_sample()
megabytes = len(data) / 1e6
rows = {}
print(f"mẫu: {len(data)} byte mã nguồn Python")
print(f"{'cài đặt':8} {'kích thước':>10} {'bit/byte':>9} {'nén MB/s':>9} {'giải nén MB/s':>14}")
for name, compress, decompress in SETTINGS:
    packed = compress(data)
    assert decompress(packed) == data
    t_comp = best_time(compress, data)
    t_decomp = best_time(decompress, packed)
    rows[name] = (len(packed), t_comp, t_decomp)
    print(f"{name:8} {len(packed):10} {8 * len(packed) / len(data):9.3f} {megabytes / t_comp:9.1f} {megabytes / t_decomp:14.1f}")

size = {name: row[0] for name, row in rows.items()}
t_comp = {name: row[1] for name, row in rows.items()}
t_decomp = {name: row[2] for name, row in rows.items()}
assert size["zlib-1"] >= size["zlib-6"] >= size["zlib-9"]
assert size["bz2-1"] >= size["bz2-9"] and size["lzma-0"] >= size["lzma-6"]
assert size["zstd-1"] >= size["zstd-3"] >= size["zstd-9"] >= size["zstd-19"]
assert size["lzma-6"] < size["zlib-9"] and size["zstd-19"] < size["zlib-9"]
assert t_comp["zlib-1"] < t_comp["zlib-9"] and t_comp["zstd-3"] * 5 < t_comp["lzma-6"]
assert t_decomp["zstd-3"] < t_decomp["lzma-6"] and t_decomp["zlib-6"] < t_decomp["bz2-9"]
frontier = [
    name
    for name in rows
    if not any(
        size[other] <= size[name] and t_comp[other] <= t_comp[name] and (size[other], t_comp[other]) != (size[name], t_comp[name])
        for other in rows
    )
]
print("không bị thống trị theo (kích thước, thời gian nén):", ", ".join(frontier))
assert not any(name.startswith("zlib") for name in frontier)
print("không cài đặt zlib nào nằm trên biên (kích thước, thời gian nén) của mẫu này")
print("mức cao hơn nén nhỏ hơn và chậm hơn; kết quả khớp thứ tự dự kiến")

python3 -B speed.py

mẫu: 1557776 byte mã nguồn Python
cài đặt  kích thước  bit/byte  nén MB/s  giải nén MB/s
zlib-1       469425     2.411     201.9         1437.7
zlib-6       378645     1.945      59.2         1581.0
zlib-9       375214     1.927      12.9         1625.4
bz2-1        342625     1.760      29.6           84.5
bz2-9        309819     1.591      29.2           80.8
lzma-0       393032     2.018      53.3          120.3
lzma-6       309516     1.590       6.8          163.3
zstd-1       428838     2.202     620.5         2079.9
zstd-3       395038     2.029     451.6         1981.7
zstd-9       348564     1.790     110.8         2255.2
zstd-19      313753     1.611       7.5         2232.4
không cài đặt zlib nào nằm trên biên (kích thước, thời gian nén) của mẫu này
mức cao hơn nén nhỏ hơn và chậm hơn; kết quả khớp thứ tự dự kiến

Đọc kết quả (tốc độ là của một máy, chỉ nên đọc thứ tự và tỉ lệ gấp bội):

  • Mức cao hơn nén nhỏ hơn và chậm hơn. Trong cùng một codec, kích thước giảm dần theo mức và tốc độ nén giảm theo: zlib từ 2,41 xuống 1,93 bit mỗi byte khi nén chậm đi khoảng 16 lần (mức 1 sang mức 9), zstd từ 2,20 xuống 1,61 bit mỗi byte khi nén chậm đi khoảng 80 lần (mức 1 sang mức 19).
  • Ba nhóm theo kích thước. Nhỏ nhất (khoảng 1,59 đến 1,61 bit mỗi byte) là lzma preset 6, bz2 mức 9 và zstd mức 19; nhóm giữa (1,76 đến 1,95) có bz2 mức 1, zstd mức 9, zlib mức 6 và 9; các cài đặt còn lại (2,0 đến 2,4) gồm lzma preset 0, zstd mức 1 và 3, zlib mức 1, trong đó zstd mức 1 và 3 là hai cài đặt nén nhanh nhất (621 và 452 MB/s).
  • zlib không nằm trên biên trên mẫu này. Với mọi mức zlib đều có một cài đặt của zstd vừa nhỏ hơn vừa nén nhanh hơn: zstd mức 9 vừa nhỏ hơn (348.564 so với 375.214 và 378.645 byte) vừa nhanh hơn zlib mức 6 và 9, còn zstd mức 1 vừa nhỏ hơn vừa nhanh gấp 3 lần zlib mức 1. Điều này không loại zlib khỏi việc dùng: nó có mặt ở gzip, ZIP và HTTP, và bài không đo tính tương thích.
  • Nén chậm không có nghĩa giải nén chậm. zstd mức 19 nén chậm ngang lzma preset 6 (khoảng 7 MB/s) nhưng giải nén nhanh hơn khoảng 14 lần (2.232 so với 163 MB/s) với kích thước chỉ lớn hơn khoảng 1,4% (313.753 so với 309.516 byte). bz2 giải nén chậm nhất (khoảng 81 đến 85 MB/s) dù ở mức 9 nén nhanh gấp khoảng 4 lần lzma preset 6 với kích thước gần bằng nhau.
  • Bộ nhớ không được đo. Tài liệu Python ghi lzma ở preset cao đòi nhiều bộ nhớ (preset 9 có thể tới 800 MiB cho bộ nén) và khuyên dùng preset mặc định; tài liệu compression.zstd ghi mức trên 20 là “ultra” và đòi nhiều bộ nhớ hơn. Lab không đo mức dùng bộ nhớ.

Chọn codec theo phép đo

Tình huốngQuyết địnhCăn cứ trong bài
Dữ liệu ngẫu nhiên, đã mã hóa hoặc đã nén (JPEG, video, .xz)Đừng nén lần nữaPhình 0,003% đến 0,6%; chuỗi ngắn phình hơn (bz2: gần 30% ở 1.000 byte)
Nén một lần, đọc nhiều lần, cần nhỏ nhấtlzma preset 6, bz2 mức 9 hoặc zstd mức 19; chọn theo giải nén và bộ nhớCả ba cỡ 1,59 đến 1,61 bit mỗi byte; giải nén 163, 81 và 2.232 MB/s
Nén thường xuyên, cần nhanhzstd mức 1 đến 3450 đến 620 MB/s nén, 2,0 đến 2,2 bit mỗi byte
Cần cỡ nhỏ vừa phải với tốc độ vẫn caozstd mức 91,79 bit mỗi byte, 111 MB/s nén
Cần tương thích gzip hoặc ZIPzlib (mức 6)Là DEFLATE (RFC 1951); trên mẫu này bị zstd thống trị nhưng tương thích rộng
Muốn biết dữ liệu của bạn nén được tới đâuĐo trên chính dữ liệu đó, không suy từ entropy bậc 0Chuỗi lặp và mã nguồn xuống rất thấp dưới entropy bậc 0
Dữ liệu nhỏ vài trăm byteĐo riêng; chi phí cố định của từng codec chiếm phần lớnChi phí 10 đến 292 byte trên chuỗi ngẫu nhiên 1.000 byte

Giới hạn

  • Số đo thuộc Python 3.14.4 (zlib 1.2.12, libzstd 1.5.7) trên một máy macOS arm64; thư viện khác phiên bản, CPU khác hay nhiều luồng sẽ cho tốc độ khác. Bài đã chạy zstd vì có compression.zstd trong bản Python này, nhưng không đo Brotli, LZ4, Snappy, 7z hay các công cụ dòng lệnh tương ứng, và không suy kết quả cho chúng.
  • Chỉ một mẫu văn bản thật (mã nguồn Python, khoảng 1,5 MB) cho các so sánh kích thước và tốc độ. Văn bản tiếng Việt, JSON, log, CSV, ảnh và nhị phân khác có thể xếp hạng các codec khác; biên “không bị thống trị” cũng chỉ là của mẫu này và nhạy với nhiễu thời gian ở các cặp gần nhau (bài chỉ khẳng định về zlib, chênh lệch lớn).
  • Bài không đo mức dùng bộ nhớ, nén theo luồng, chế độ từ điển, nén song song, độ trễ của khối nhỏ, hay chi phí của gzip/ZIP bao quanh.
  • Entropy trong lab là của nguồn độc lập đã biết hoặc entropy bậc 0 của mẫu; bài không tính entropy bậc cao hay độ phức tạp thuật toán của dữ liệu.
  • Giải thích về cách zlib và zstd lệch khỏi entropy ở nguồn dyadic và nhị phân là diễn giải từ số đo; bài không đọc mã nguồn của các thư viện.
  • Lab không ghi tệp ngoài thư mục bạn đã tạo; xóa thư mục đó là dọn xong.

Học tiếp và nguồn

  • Đọc benchmark: số đo và ngoại suy: cách đọc số đo thời gian và tỉ lệ gấp bội mà không suy quá phép đo.
  • LSM-tree so với B-tree: nơi nén theo khối (SSTable) gặp đánh đổi ghi và đọc.
  • Claude E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, 1948 (bản in lại có sửa lỗi, đọc các mục 6 đến 10): công thức entropy, entropy của nguồn, định lý 9 và các ví dụ.
  • IETF, RFC 1951: DEFLATE Compressed Data Format Specification: LZ77 kết hợp Huffman và khối lưu nguyên.
  • Python 3.14, zlib: mức nén 0 đến 9 và -1 (mặc định, tương đương mức 6).
  • Python 3.14, bz2: compresslevel từ 1 đến 9, mặc định 9.
  • Python 3.14, lzma: preset từ 0 đến 9, mặc định 6, đánh đổi bộ nhớ.
  • Python 3.14, compression.zstd: module tùy chọn, mức mặc định 3, mức trên 20 là “ultra”.

Nguồn trực tuyến đọc ngày 2026-10-04; số đo thuộc Python 3.14.4 trên macOS arm64, không có nghiệm thu Linux hay thư viện khác.