What does Lazy Tool Hubs conclude, in numbers, about “Building Huffman Trees: Many-Way Merging, Dummy Leaves and the Price of a Menu”?

Answer: A many-way Huffman tree must be padded with dummy leaves first; otherwise a 10-ary tree needs more than a quarter more decisions. On small instances the Huffman tree matched the exhaustive optimum in all 720 cases. Decisions are not tokens: each decision reads a menu, and the best branching factor in tokens is about 2.72 with zero hop cost and about 5.09 with a hop cost of 80 tokens. Yet this chapter has kept avoiding one question. A Huffman tree lumps cold tools together by frequency into a branch, so the model sees on its menu a node without a name. How is it to know that the tool it wants lies down that branch? The next chapter answers this, and puts a price on the answer.

Scope of the numbers: Selection accuracy lacks reliable peer-reviewed primary evidence and is demoted to an author's hypothesis. Marked boxes separate published evidence, runnable Python calculations (17 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 10, 2.72, 5.09, 80

ktokens HOP=0boundtokens HOP=80bound
2320.3318.6832.7828.4
3305.2301.5630.7623.2
4325.1318.6585.1573.5
5350.9343.0575.4562.6
6379.9369.8582.5567.0
8441.4424.8618.0594.7
10499.3479.6659.0633.0
16682.6637.2819.1764.7
321124.51019.51236.91121.5
flat menu of all 300 one-line entries: 7500 tokens
HOP=0: continuous optimum k* = 2.72
HOP= 80: continuous optimum k* = 5.09
HOP=400: continuous optimum k* = 11.26
Show the full program
# Chapter 2. p23: decisions are not tokens; the menu has to be read.
# Each routing decision reads a k-line menu (S tokens a line) and pays
# a fixed hop overhead HOP (call framing, reply envelope). Per lookup
# the router pays (HOP + k S) per decision, so the token bound is
# (HOP + k S) H / log2(k), not H. Shown for HOP = 0 and HOP = 80, with
# the padded k-ary Huffman tree on N = 300 Zipf(1) tools. The real
# optimum k solves k (ln k - 1) = HOP / S. S, HOP are illustrative.
import heapq
import math

N, S = 300, 25


def zipf(n, a):
    w = [1.0 / (i ** a) for i in range(1, n + 1)]
    t = math.fsum(w)
    return [x / t for x in w]


def entropy(p):
    return -math.fsum(x * math.log2(x) for x in p if x > 0)


def huff_l(p, k):
    items = [(x, i, (i,)) for i, x in enumerate(p)]
    seq, pad = len(p), 0
    while k > 2 and (len(items) + pad - 1) % (k - 1):
        pad += 1
    for _ in range(pad):
        items.append((0.0, seq, ()))
        seq += 1
    heapq.heapify(items)
    depth = [0] * len(p)
    while len(items) > 1:
        kids = [heapq.heappop(items) for _ in range(min(k, len(items)))]
        leaves = ()
        for c in kids:
            for i in c[2]:
                depth[i] += 1
            leaves += c[2]
        heapq.heappush(items, (math.fsum(c[0] for c in kids), seq, leaves))
        seq += 1
    return math.fsum(x * d for x, d in zip(p, depth))


def k_star(ratio):
    lo, hi = 1.0001, 1000.0
    for _ in range(200):
        mid = (lo + hi) / 2
        if mid * (math.log(mid) - 1) < ratio:
            lo = mid
        else:
            hi = mid
    return lo


p = zipf(N, 1.0)
h = entropy(p)
print(" k   tokens HOP=0  bound   tokens HOP=80  bound")
for k in (2, 3, 4, 5, 6, 8, 10, 16, 32):
    lk = huff_l(p, k)
    b = h / math.log2(k)
    print("%3d %10.1f %8.1f %12.1f %8.1f"
          % (k, lk * k * S, b * k * S, lk * (80 + k * S),
             b * (80 + k * S)))
print("flat menu of all %d one-line entries: %d tokens" % (N, N * S))
for hop in (0, 80, 400):
    print("HOP=%3d: continuous optimum k* = %.2f" % (hop, k_star(hop / S)))

Single source and citation

Fan, Y. (2026). A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees (Version 1.0.0), Chapter 2: Building Huffman Trees: Many-Way Merging, Dummy Leaves and the Price of a Menu. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-257 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026257,
  author    = {Fan, Yafu},
  title     = {A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book