请输入您要查询的字词:

 

单词 ArithmeticEncoding
释义

arithmetic encoding


Arithmetic coding is a technique for achieving near-optimal entropy encoding.

An arithmetic encoder takes a string of symbols as input and produces a rational number in the interval [0,1) as output. As each symbol is processed, the encoder will restrict the output to a smaller interval.

Let N be the number of distinct symbols in the input; let x1,x2xN represent the symbols, and let P1,P2PN represent the probability of each symbol appearing. At each step in the process, the output is restricted to the current interval [y,y+R). PartitionPlanetmathPlanetmath this interval into N disjoint subintervals:

I1=[y,y+P1R)
I2=[y+P1R,y+P1R+P2R)
IN=[y+i=1N-1PiR,y+R)

Therefore the of Ii is PiR. If the next symbol is xi, then restrict the output to the new interval Ii.

Note that at each stage, all the possible intervals are pairwise disjoint. Therefore a specific sequenceMathworldPlanetmath of symbols produces exactly one unique output range, and the process can be reversed.

Since arithmetic encoders are typically implemented on binary computers, the actual output of the encoder is generally the shortest sequence of bits representing the fractional part of a rational number in the final interval.

Suppose our entire input string contains M symbols: then xi appears exactly PiM times in the input. Therefore, the size of the final interval will be

Rf=i=1NPiPiM

The number of bits necessary to write a binary fraction in this range is

-log2Rf=-log2i=1NPiPiM
=i=1N-log2PiPiM
=i=1N-PiMlog2Pi

By Shannon’s theoremMathworldPlanetmath, this is the total entropyMathworldPlanetmath of the original message. Therefore arithmetic encoding is near-optimal entropy encoding.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 22:11:30