Differences between current version and revision by previous author of ArithmeticEncoding.
Other diffs: Previous Major Revision, Previous Revision, or view the Annotated Edit History
Newer page: | version 2 | Last edited on Friday, October 10, 2003 12:35:03 am | by StuartYeates | |
Older page: | version 1 | Last edited on Monday, September 1, 2003 9:07:56 am | by GreigMcGill | Revert |
@@ -1,4 +1,10 @@
-An arithmetic
encoder takes a string
of symbols as input
and produces a rational number
in the interval
[,1) as output
. As each symbol
is processed,
the encoder will restrict the output to a smaller interval
.
+An encoding of all binary strings in the range to all [Binary] strings in the domain, based on an expected probability distribution of bitstings. The encoder starts with the range [,1) and to encode reach bit the
encoder takes the expected distribution
of the bit (maybe 20/80)
and divides the range
in those proportions and throws away
the portion the bit didn't fall into (in this case either [
[,.2) or [[.8
,1) )
. When all bits have been seen the range
is sent as
the encoding
.
-----
-Note: Cut and Pasted definition
. Someone with
a math background might like
to AddToMe.
+ArithmeticDecoding is the reverse process
.
+
+ArithmeticEncoding has been shown to be the asymototical optimal way to encode such
a string (only asymototical optimal because of the need
to round up the range to the nearest bit).
+
+ArithmeticEncoding and ArithmeticDecoding are used in bzip2(1) and but zip(1).
+
+
+
AddToMe.