Арифметическое кодирование для сжатия данных: различия между версиями

'''Теорема 2. В квазиарифметическом кодере, основанном на полном интервале [0, N), использующем корректные оценки вероятностей и исключающем очень большие и очень малые вероятности, количество бит на входное событие, при котором средняя длина кода, полученного квазиарифметическим кодером, превышает длину кода, полученного точным арифметическим кодером, составляет не более''' <math>\frac{4}{ln \; 2} \bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{N} + O \bigg( \frac{1}{N^2} \bigg) \approx \frac{0,497}{N} + O \bigg( \frac{1}{N^2} \bigg),</math>

'''а доля, на которую средняя длина кода, полученная квазиарифметическим кодером, превышает длину кода, полученную точным арифметическим кодером, не превышает''' <math>\bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg) \approx \frac{0,0861}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg).</math>