Concept

Weighted path length — where it appears

The sum, over a tree's leaves, of each leaf's weight times its depth — the quantity Huffman's construction minimises. It prices a merge fold only where every level costs the same, which is true of a prefix code and false of a fold whose charge grows with the mass beneath each node.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

The fold that minimises the wrong thing

A fold charges per level and a survivor pays the cuts on its path, so the bill looks like a weighted external path length — and Huffman's construction minimises that quantity by proof. Built and measured on thirty-two uneven shards it does minimise it, 181,407 against a balanced tree's 200,000, and leaves more damage than the tree does.

structures · Merge

A parameter that waits for another

Four merge fold shapes over thirty-two evenly loaded shards leave errors of 665, 667, 665 and 667 — a fifth of a per cent apart. Give the same four shapes shards whose loads span seventeen-fold and they leave 148, 183, 323 and 403. The parameter did nothing until a second parameter moved, and every measurement that fixed the second one saw nothing.

wrong · Merge

Named alongside it

The objects these essays reach for when they reach for this one.

Heavy hitter Merge tree Mergeable summary Misra–Gries Partition Shard Space-saving Trade off Benchmarking Counterexample Guarantee Huffman coding

All concepts