de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Codes: Unequal Probabilities, Unequal Letter Cost

MPS-Authors

Altenkamp,  Doris
Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Altenkamp, D., & Mehlhorn, K. (1980). Codes: Unequal Probabilities, Unequal Letter Cost. Journal of the ACM, 27, 412-427.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AF62-2
Abstract
The construction of alphabetic prefix codes with unequal letter costs and unequal probabilities is considered. A variant of the noiseless coding theorem is proved giving closely matching lower and upper bounds for the cost of the optimal code. An algorithm is described which constructs a nearly optimal code in linear time.