Content deleted Content added
MeltBanana (talk | contribs) m sp. |
- added Krafts inequality |
||
Line 89:
Some data compression algorithms can compress files even smaller than [[Huffman compression]]. Generally this is because they don't use a code at all. They may represent "a" by one pattern of bits in one place in the compressed file, then use that same pattern of bits to represent a completely different letter later on, as in [[adaptive Huffman]] compression. They may use a short pattern of bits to represent several letters, as in [[LZW]] compression -- changing any one of those bits may completely change that block of letters. Or they may avoid mapping particular bits to particular letters (the definition of a code) in other creative ways, an in [[range encoding]].
=== existence of prefix codes / Krafts inequality ===
If we have a fixed number of symbols <math>|X|</math>(the alphabet size), then for any given list if codeword lenghts <math>(l_i)_{i=1...n}</math> a prefix code exists if and only if <math>\sum_{i=1}^{n}|X|^{-l_i}\le 1</math>. This is known as ''Krafts inequality''.
== error handling ==
| |||