编码：区分彼此与信息压缩传递

信息

2024年8月8日 · ·

引言

编码是信息压缩与传递的基础。在信息论中，编码是将信息转换为另一种形式的过程，以便在传输或存储时更有效地使用资源。好的编码方式可以有效的减少信息的冗余度，以便更有效地传递或存储信息。在这篇文章中，我们将讨论编码的基本原理，以及编码在信息压缩和传递中的应用。

编码的本质

编码技术是计算机科学的基础，是将信息转换为适合作传输、存储和处理的形式的过程。编码技术可以应用于多种领域与目的，如信息识别、信息压缩、信息传递等。

在信息论中，编码通常指的是将信息转换为二进制形式的过程。二进制编码是一种将信息转换为 0 和 1 序列的方法，以便更有效地传输或存储信息。在二进制编码中，每个 0 或 1 称为一个比特（bit），是计算机中最小的信息单位。

区分彼此

编码的本质就是将信息转换为可以用于唯一地标识不同对象或类别的过程，即区分彼此。

在计算机中，编码过程就是信息被转换为二进制序列，然后用于网络的传输或存储设备的存储。在接收端，接收到的二进制序列被解码为原始信息。

最常见的例子是使用唯一标识符表示一个具体的对象（如 UUID）。

如何生成唯一的用户 ID？

import uuid

def generate_user_id():
    return str(uuid.uuid4())

# 示例
user_id = generate_user_id()
print(f"生成的用户ID：{user_id}")

任何对象都可以通过对它们编号来区分，而在计算机中，任何编号方式都等价于二进制编码。

编码的抽象作用

编码不仅限于对具体的个体对象（如用户、数据块）进行编码，也可以应用于对非实体对象（如目标、路径、流程等）进行分层次编码，这样有助于我们将这些抽象的事物的管理、处理和优化做到极致。我们可以通过如下两个示例来感受抽象和编码思想是如何解决实际问题的。

黄金分割问题

假设雇主雇用工人干七天工作量的活，雇主答应一共支付一根金条作为报酬，但是工人要求每天支付他 1/7 的工资。那么，如何在金条上切两刀，保证每天正好能支付工人 1/7 的工资。

通过巧妙的编码和数学思维来解决。

分析与编码思考

我们将金条分成长度分别为 1/7、2/7 和 4/7 的三段。通过这些段 (1、2、4) 的组合，可以得到 $2^3$ 一下的所有支付金额。

1. 第一天：支付 1/7。
2. 第二天：收回 1/7，支付 2/7。
3. 第三天：支付 1/7（此时工人手上有 2/7 和 1/7）。
4. 第四天：收回 1/7 和 2/7，然后支付 4/7。
5. 第五天：支付 1/7（此时工人手上有 4/7 和 1/7）。
6. 第六天：收回 1/7，然后支付 2/7（此时工人手上有 4/7 和 2/7）。
7. 第七天：支付 1/7（此时工人手上有 4/7、2/7 和 1/7，即完整的 7/7）。

通过这种组合支付方式，确保每天能准确支付工人 1/7 的工资。

Python 实现：

def gold_bar_cutting():
    # 切分位置
    cuts = [1/7, 2/7, 4/7]

    # 每天的支付情况
    actions = [
        "Day 1: Pay 1/7",
        "Day 2: Take back 1/7, Pay 2/7",
        "Day 3: Pay 1/7",
        "Day 4: Take back 1/7 and 2/7, Pay 4/7",
        "Day 5: Pay 1/7",
        "Day 6: Take back 1/7, Pay 2/7",
        "Day 7: Pay 1/7"
    ]

    return cuts, actions

cuts, actions = gold_bar_cutting()
print(f"切分位置（相对于金条总长度）：{cuts}")
for action in actions:
    print(action)

通过巧妙的定位辅助标记实现资源的等分与分配，体现了编码在数据切分和组合上的应用。

小白鼠试验问题

有 64 瓶药，其中 1 瓶有毒，其他 63 瓶是无毒的。试验的小白鼠喝了有毒的药三天后会死掉，喝了其他的药（包括同时喝几种无毒混合的药）都无碍，一只小白鼠只能参与一次试验。假设只剩下三天时间，那么最少需要多少只小白鼠才能试出哪瓶药有毒?

分析与编码思考

我们可以利用二进制编码的思想来解决这个问题。64 瓶药可以用 6 位二进制数编码，从 000000 到 111111。我们可以用 6 只小白鼠来进行试验，每只小白鼠代表一个二进制位。

1. 编号为 (i) 的药用 0 或 1 表示第(j)位，0 表示不让编号为(i)的小白鼠尝试，1 表示让编号为(i)的小白鼠尝试。
2. 通过编码每一瓶药，如果药有毒，那么在三天后会死掉的鼠的组合可以组成这瓶药的编号。
3. 这样只需要 6 只小白鼠即可确定 64 瓶药中的哪瓶是有毒的。

Python 实现：

def identify_poisonous_bottle():
    n = 64  # Number of bottles
    k = 6   # Number of mice (ceil(log2(64)))

    # 创建药瓶到各只小白鼠的编码
    def encode_bottles(n, k):
        encodings = []
        for i in range(n):
            bin_str = format(i, f'0{k}b')  # Convert number to binary string of length k
            encodings.append(bin_str)
        return encodings

    encodings = encode_bottles(n, k)

    # 模拟的一组小白鼠实验 (1表示该鼠需要尝试该瓶药)
    test_plan = {i: [] for i in range(k)}
    for bottle_index, code in enumerate(encodings):
        for bit_index in range(k):
            if code[bit_index] == '1':
                test_plan[bit_index].append(bottle_index)

    return test_plan

test_plan = identify_poisonous_bottle()
for mouse, bottles in test_plan.items():
    print(f"小白鼠 {mouse+1} 喝的药瓶编号：{bottles}")

将二进制编码的思想应用到实验设计中，以最小代价实现目标辨识，通过编码优化试验规模和成本。

信息压缩与传递

信息压缩是编码的一个重要应用。信息压缩是将信息转换为更紧凑的形式，以便更有效地传输或存储信息。信息压缩通常通过减少信息的冗余度来实现。冗余度是指信息中的重复或不必要的部分。通过去除冗余度，信息压缩可以减少信息的大小，从而减少传输或存储所需的资源。

信息压缩有两种基本类型：有损压缩和无损压缩。有损压缩是通过牺牲一些信息的质量来实现更高的压缩率。无损压缩是通过保留所有信息的质量来实现较低的压缩率。在信息压缩中，通常会根据应用的需求选择适当的压缩方法。

信息压缩（Information Compression）

编码技术可以用于将数据在保证信息完整的前提下尽量压缩。例如常用的霍夫曼编码（Huffman Coding）就是一种无损压缩算法。

如何使用霍夫曼编码压缩一段文本？

import heapq
from collections import defaultdict, Counter

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    freq = Counter(text)
    heap = [HuffmanNode(char, freq) for char, freq in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged = HuffmanNode(None, node1.freq + node2.freq)
        merged.left = node1
        merged.right = node2
        heapq.heappush(heap, merged)

    return heap[0]

def generate_codes(node, prefix="", codebook=None):
    if codebook is None:
        codebook = {}
    if node:
        if node.char is not None:
            codebook[node.char] = prefix
        generate_codes(node.left, prefix + "0", codebook)
        generate_codes(node.right, prefix + "1", codebook)
    return codebook

# 示例
text = "this is an example for huffman encoding"
root = build_huffman_tree(text)
codes = generate_codes(root)
print(f"生成的霍夫曼编码：{codes}")

信息传递（Information Transmission）

在信息传递中，编码用于将信息转换为适合传输或存储的形式。以便通过通信信道传输。在接收端，接收到的编码序列被解码为原始信息。

信息传递中的编码有多种类型，包括线性编码、循环编码、卷积编码等。这些编码方法在不同的应用中有不同的特点和优势。在信息传递中，通常会根据通信信道的特性和传输要求选择适当的编码方法。

编码技术在通信中至关重要，是数据在传输过程中确保可靠性和有效性的关键。一个典型的应用是海明码（Hamming Code），可以用于错误的检测和纠正。

如何生成用于纠错的海明码？

def calc_parity_bits(data_bits):
    n = len(data_bits)
    r = 0
    while (2**r) - 1 < n + r:
        r += 1
    return r

def generate_hamming_code(data):
    data_bits = [int(bit) for bit in data]
    r = calc_parity_bits(data_bits)
    hamming_code = [-1] * (len(data_bits) + r)

    j = 0
    for i in range(1, len(hamming_code) + 1):
        if (i & (i - 1)) == 0:
            hamming_code[i - 1] = 0  # Parity bit (temporary)
        else:
            hamming_code[i - 1] = data_bits[j]
            j += 1

    for i in range(r):
        pos = 2 ** i
        parity = 0
        for j in range(1, len(hamming_code) + 1):
            if j & pos:
                parity ^= hamming_code[j - 1]
        hamming_code[pos - 1] = parity

    return ''.join(map(str, hamming_code))

# 示例
data = "1101"
hamming_code = generate_hamming_code(data)
print(f"生成的海明码：{hamming_code}")

结语

编码的本质是区分彼此。此外，编码的抽象作用不仅限于字符和数据，还能够扩展到对目标、路径、流程的分层次的抽象编码，从而使事物的处理效率达到极致。

编码是信息压缩与传递的基础。通过编码，信息可以更有效地传输或存储。在信息压缩中，编码可以减少信息的冗余度，从而减少传输或存储所需的资源。在信息传递中，编码可以将信息转换为适合传输或存储的形式。

人对目标的编码是一个渐渐演变所得到的结果，以方便为目的；而计算机的编码要争取一次性尽可能考虑清楚所有情况，以效率为目的。它们之间经常需要一座桥梁来连接。

---

PS：感谢每一位志同道合者的阅读，欢迎关注、点赞、评论！