Codes for the World Wide Web

We introduce a new family of simple, complete instantaneous codes for positive integers, called zeta codes, which are suitable for integers distributed as a power law with small exponent (smaller than 2). The main motivation for the introduction of zeta codes comes from web-graph compression: if nodes are numbered according to URL lexicographical order, gaps in successor lists are distributed according to a power law with small exponent. We give estimates of the expected length of zeta codes against power-law distributions, and compare the results with analogous estimates for the more classical gamma delta and variable-length block codes.