两份 Huffman 码表长得不一样，为什么都可能一样省？

"""Huffman ties: different valid codes can have the same optimal bit cost."""
import heapq
import itertools
import json
from functools import lru_cache


def build_codes(weights, reverse_ties=False):
    if len(weights) > 64 or any(not isinstance(k, str) or len(k) != 1 for k in weights):
        raise ValueError("at most 64 single-character symbols")
    if any(type(v) is not int or v <= 0 for v in weights.values()):
        raise ValueError("positive integer frequencies required")
    if not weights:
        return {}
    serial = itertools.count()
    heap = [(weights[k], next(serial), k) for k in sorted(weights, reverse=reverse_ties)]
    heapq.heapify(heap)
    while len(heap) > 1:
        wa, _, a = heapq.heappop(heap)
        wb, _, b = heapq.heappop(heap)
        heapq.heappush(heap, (wa + wb, next(serial), (a, b)))
    codes = {}
    def visit(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix or "0"  # Explicit single-symbol convention.
        else:
            visit(node[0], prefix + "0")
            visit(node[1], prefix + "1")
    visit(heap[0][2], "")
    return codes


def decode(bits, codes):
    if any(bit not in "01" for bit in bits):
        raise ValueError("non-binary payload")
    if not codes:
        if bits:
            raise ValueError("payload without codebook")
        return ""
    trie = {}
    for symbol, code in codes.items():
        if not code or any(c not in "01" for c in code):
            raise ValueError("invalid code")
        node = trie
        for bit in code:
            if "symbol" in node:
                raise ValueError("prefix conflict")
            node = node.setdefault(bit, {})
        if node:
            raise ValueError("duplicate or prefix conflict")
        node["symbol"] = symbol
    result, node = [], trie
    for bit in bits:
        if bit not in node:
            raise ValueError("unknown prefix")
        node = node[bit]
        if "symbol" in node:
            result.append(node["symbol"])
            node = trie
    if node is not trie:
        raise ValueError("truncated code")
    return "".join(result)


def exhaustive_tree_cost(weights):
    # Independent oracle: enumerate every root split of the symbol set.
    # Each split increases every descendant depth by one; no greedy merging.
    values = tuple(weights.values())
    if len(values) > 6:
        raise ValueError("oracle limited to six symbols")
    @lru_cache(None)
    def cost(mask):
        if mask & (mask - 1) == 0:
            return 0
        first, sub, choices = mask & -mask, (mask - 1) & mask, []
        while sub:
            if sub & first and sub != mask:
                choices.append(cost(sub) + cost(mask ^ sub))
            sub = (sub - 1) & mask
        total = sum(v for i, v in enumerate(values) if mask >> i & 1)
        return total + min(choices)
    if len(values) <= 1:
        return sum(values)  # Match the explicit one-bit singleton convention.
    return cost((1 << len(values)) - 1)


def main():
    checks, cases = 0, 0
    def check(ok):
        nonlocal checks
        if not ok:
            raise AssertionError("Huffman check failed")
        checks += 1
    for n in range(1, 6):
        for values in itertools.product((1, 2, 3), repeat=n):
            weights = dict(zip("ABCDE", values))
            message = "".join(k * v for k, v in weights.items())
            target = exhaustive_tree_cost(weights)
            for reverse in (False, True):
                codes = build_codes(weights, reverse)
                bits = "".join(codes[k] for k in message)
                check(len(bits) == target)
                check(decode(bits, codes) == message)
                check(all(not b.startswith(a) for i, a in enumerate(codes.values())
                          for j, b in enumerate(codes.values()) if i != j))
            cases += 1
    check(build_codes({}) == {})
    check(decode("", {}) == "")
    check(build_codes({"Q": 5}) == {"Q": "0"})
    for weights in [{"A": 0}, {"A": True}, {"AB": 2}]:
        try:
            build_codes(weights)
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid frequency accepted")
    for bits, codes in [("1", {"A": "0"}), ("0", {"A": "00", "B": "01"}),
                        ("x", {"A": "0"}), ("0", {"A": "0", "B": "01"})]:
        try:
            decode(bits, codes)
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid bitstream or codebook accepted")
    weights = {"A": 1, "B": 1, "C": 1, "D": 1}
    forward, reverse = build_codes(weights), build_codes(weights, True)
    check(forward != reverse)
    print(json.dumps({"checks_passed": checks, "frequency_cases": cases,
                      "forward_ties": forward, "reverse_ties": reverse,
                      "bit_costs": [sum(len(c[k]) * v for k, v in weights.items())
                                    for c in (forward, reverse)],
                      "singleton": build_codes({"Q": 5}),
                      "scope": "payload bit cost only; codebook storage excluded; not a DEFLATE codec"}, indent=2))


if __name__ == "__main__":
    main()