Even-Rodeh coding Contents Encoding Examples See also References Navigation menu"Economical encoding of commas between strings"10.1145/359460.359480e
Lossless compression algorithms
universal codeShimon EvenMichael Rodehnon-negative integer
Even-Rodeh code is a universal code encoding the non-negative integers developed by Shimon Even and Michael Rodeh.[1]
Contents
1 Encoding
2 Examples
3 See also
4 References
Encoding
To code a non-negative integer N in Even-Rodeh coding:
- If N is not less than 4 then set the coded value to a single
0
bit. Otherwise the coded value is empty. - If N is less than 8 then prepend the coded value with 3 bits containing the value of N and stop.
- Prepend the coded value with the binary representation of N.
- Store the number of bits prepended in step 3 as the new value of N.
- Go back to step 2.
To decode an Even-Rodeh-coded integer:
- Read 3 bits and store the value into N.
- If the first bit read was
0
then stop. The decoded number is N. - If the first bit read was
1
then continue to step 2.
- If the first bit read was
- Examine the next bit.
- If the bit is
0
then read 1 bit and stop. The decoded number is N. - If the bit is
1
then read N bits, store the value as the new value of N, and go back to step 2.
- If the bit is
Examples
Number | Encoding | Implied probability |
---|---|---|
0 | 000 | 1/8 |
1 | 001 | 1/8 |
2 | 010 | 1/8 |
3 | 011 | 1/8 |
4 | 100 0 | 1/16 |
5 | 101 0 | 1/16 |
6 | 110 0 | 1/16 |
7 | 111 0 | 1/16 |
8 | 100 1000 0 | 1/256 |
9 | 100 1001 0 | 1/256 |
︙ | ||
15 | 100 1111 0 | 1/256 |
16 | 101 10000 0 | 1/512 |
︙ | ||
2761 | 100 1100 101011001001 0 | 1/1,048,576 |
︙ |
See also
- Elias omega (ω) coding
References
^ Even, Shimon; Rodeh, Michael (April 1978). "Economical encoding of commas between strings". Communications of the ACM. 21 (4): 315–317. doi:10.1145/359460.359480..mw-parser-output cite.citationfont-style:inherit.mw-parser-output .citation qquotes:"""""""'""'".mw-parser-output .citation .cs1-lock-free abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-subscription abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registrationcolor:#555.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration spanborder-bottom:1px dotted;cursor:help.mw-parser-output .cs1-ws-icon abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center.mw-parser-output code.cs1-codecolor:inherit;background:inherit;border:inherit;padding:inherit.mw-parser-output .cs1-hidden-errordisplay:none;font-size:100%.mw-parser-output .cs1-visible-errorfont-size:100%.mw-parser-output .cs1-maintdisplay:none;color:#33aa33;margin-left:0.3em.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-formatfont-size:95%.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-leftpadding-left:0.2em.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-rightpadding-right:0.2em