c20-3 (779625), страница 4
Текст из файла (страница 4)
These can then be encoded infewer bits than rarer input strings or symbols, giving a net average gain.There exist many, quite different, compression techniques, corresponding todifferent ways of detecting and using departures from equiprobability in input strings.In this section and the next we shall consider only variable length codes with definedword inputs. In these, the input is sliced into fixed units, for example ASCIIcharacters, while the corresponding output comes in chunks of variable size.
Thesimplest such method is Huffman coding [1], discussed in this section. Anotherexample, arithmetic compression, is discussed in §20.5.At the opposite extreme from defined-word, variable length codes are schemesthat divide up the input into units of variable length (words or phrases of English text,for example) and then transmit these, often with a fixed-length output code. The mostwidely used code of this type is the Ziv-Lempel code [2]. References [3-6] give theflavor of some other compression techniques, with references to the large literature.The idea behind Huffman coding is simply to use shorter bit patterns for morecommon characters.
We can make this idea quantitative by considering the conceptof entropy. Suppose the input alphabet has Nch characters, and that thesePoccur inthe input string with respective probabilities pi , i = 1, . . . , Nch , so thatpi = 1.Then the fundamental theorem of information theory says that strings consisting ofSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).CITED REFERENCES AND FURTHER READING:.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
