2004-38: Verification of Minimum-Redundancy Prefix Codes

DIMACS TR: 2004-38

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

DIMACS Home Page