Verification of Minimum-Redundancy Prefix Codes

Author: Ahmed Belal and Amr Elmasry

ABSTRACT
We show that verifying a given prefix code for optimality requires \$\Omega(n\log{n})\$, indicating that the verification problem is not asymptotically easier than the construction problem. Alternatively, we give linear-time verification algorithms for several special cases that are either typical in practice or theoretically interesting.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-38.ps.gz