4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 103: | Строка 103: | ||
На шаге 2 необходимо вычислить только подынтервал, соответствующий событию <math>a_i</math>, которое | На шаге 2 необходимо вычислить только подынтервал, соответствующий событию <math>a_i</math>, которое фактически происходит. Для этого удобно использовать две «кумулятивные» вероятности: кумулятивную вероятность <math>P_C = \sum_{k = 1}^{i - 1} p_k</math> и следующую кумулятивную вероятность <math>P_N = P_C + p_i = \sum_{k = 1}^i p_k</math>. Новый подынтервал имеет вид <math>[L + P_C(H - L), L + P_N(H - L))</math>. Необходимость хранения и предоставления кумулятивных вероятностей требует от модели сложной структуры данных – например, как у Моффата [7] – особенно когда возможно намного больше двух событий. | ||
'''Моделирование''' | '''Моделирование''' | ||
Целью моделирования при статистическом сжатии данных является предоставление кодировщику вероятностной информации. Процесс моделирования состоит из структурного и вероятностного компонентов, каждый из которых может быть адаптивным (начиная с нейтральной модели, | Целью моделирования при статистическом сжатии данных является предоставление кодировщику вероятностной информации. Процесс моделирования состоит из структурного и вероятностного компонентов, каждый из которых может быть адаптивным (начиная с нейтральной модели, структура и вероятности постепенно наращиваются в зависимости от встречающихся событий), полуадаптивным (задается начальная модель, описывающая события, которые будут встречаться в данных, затем в процессе кодирования модель модифицируется так, чтобы она описывала только те события, которые еще предстоит закодировать) или статическим (задается начальная модель и используется без модификации в процессе кодирования). | ||
Кроме того, существуют две стратегии оценки вероятности. Первая заключается в индивидуальной оценке вероятности каждого события на основе частоты его встречаемости | Кроме того, существуют две стратегии оценки вероятности. Первая заключается в индивидуальной оценке вероятности каждого события на основе частоты его встречаемости во входной последовательности. Вторая представляет собой оценку вероятностей в совокупности, предполагая распределение вероятностей определенной формы и оценивая параметры распределения прямо или косвенно. При прямом оценивании можно по данным получить оценку параметра (например, дисперсии); при косвенном [5] можно начать с небольшого числа возможных распределений и вычислить длину кода, который будет получен при каждом из них, а затем выбрать распределение с наименьшей длиной кода. Этот метод является максимально общим и может быть использован даже для распределений из разных семейств, не имеющих общих параметров. | ||
Строка 117: | Строка 117: | ||
'''Теорема 1. Для всех входных файлов кодовая длина <math>L_A</math> адаптивного кода с начальными 1-весами равна кодовой длине <math>L_{SD}</math> полуадаптивного | '''Теорема 1. Для всех входных файлов кодовая длина <math>L_A</math> адаптивного кода с начальными 1-весами равна кодовой длине <math>L_{SD}</math> полуадаптивного декрементного кода плюс кодовая длина <math>L_M</math> входной модели, кодируемой в предположении, что все распределения символов равновероятны. Эта кодовая длина меньше <math>L_S = mH_0 + L_M</math> – кодовой длины статического кода с той же входной моделью. Иными словами, <math>L_A = L_{SD} + L_M < mH_0 + L_M = L_S</math>.''' | ||
Строка 127: | Строка 127: | ||
'''Инкрементный вывод.''' | '''Инкрементный вывод.''' | ||
Базовая реализация арифметического кодирования, описанная выше, имеет две основные трудности: уменьшение текущего интервала требует использования арифметики высокой точности, а вывод не производится до тех пор, пока не будет прочитан весь файл. Наиболее простым решением обеих этих проблем является вывод каждого старшего бита, как только он становится известен, а затем удвоение длины текущего интервала таким образом, чтобы он отражал только неизвестную часть конечного интервала. Виттен, Нил и Клири [11] добавили остроумный механизм, предотвращающий чрезмерное сокращение текущего интервала, когда конечные точки близки к <math>\frac{1}{2}</math>, но расходятся с <math>\frac{1}{2}</math>. В этом случае | Базовая реализация арифметического кодирования, описанная выше, имеет две основные трудности: уменьшение текущего интервала требует использования арифметики высокой точности, а вывод не производится до тех пор, пока не будет прочитан весь файл. Наиболее простым решением обеих этих проблем является вывод каждого старшего бита, как только он становится известен, а затем удвоение длины текущего интервала таким образом, чтобы он отражал только неизвестную часть конечного интервала. Виттен, Нил и Клири [11] добавили остроумный механизм, предотвращающий чрезмерное сокращение текущего интервала, когда конечные точки близки к <math>\frac{1}{2}</math>, но расходятся с <math>\frac{1}{2}</math>. В этом случае следующий бит вывода еще не известен – но, каким бы он ни был, ''следующий за ним'' бит будет иметь противоположное значение; можно просто отслеживать этот факт и расширять текущий интервал симметрично относительно <math>\frac{1}{2}</math>. Эта процедура может повторяться любое количество раз, так что размер текущего интервала всегда будет строго больше <math>\frac{1}{4}</math>. | ||
Строка 135: | Строка 135: | ||
'''Использование целочисленной арифметики.''' | '''Использование целочисленной арифметики.''' | ||
На практике арифметика может быть реализована путем хранения конечных точек текущего интервала в виде достаточно больших целых чисел, а не в виде чисел с плавающей точкой или точных рациональных чисел. Вместо того чтобы начинать с вещественного интервала [0, 1), начните с целочисленного интервала [0, N), где N неизменно является степенью 2. Процесс разбиения заключается в выборе непересекающихся целочисленных интервалов (длиной не менее 1) с длинами, примерно пропорциональными количествам | На практике арифметика может быть реализована путем хранения конечных точек текущего интервала в виде достаточно больших целых чисел, а не в виде чисел с плавающей точкой или точных рациональных чисел. Вместо того чтобы начинать с вещественного интервала [0, 1), начните с целочисленного интервала [0, N), где N неизменно является степенью 2. Процесс разбиения заключается в выборе непересекающихся целочисленных интервалов (длиной не менее 1) с длинами, примерно пропорциональными подсчитанным количествам. | ||
Строка 146: | Строка 146: | ||
Число возможных состояний (после применения процедуры расширения интервала) арифметического кодера, использующего целочисленный интервал [0, N), равно <math>3N^2/16</math>. Очевидным способом уменьшения числа состояний | Число возможных состояний (после применения процедуры расширения интервала) арифметического кодера, использующего целочисленный интервал [0, N), равно <math>3N^2/16</math>. Очевидным способом уменьшения числа состояний до такого, при котором использование таблиц поиска становится практичным, является уменьшение значения N. Двоичное квазиарифметическое кодирование приводит к незначительному увеличению длины кода по сравнению с чисто арифметическим кодированием. | ||
'''Теорема 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> | '''Теорема 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> | ||
Строка 160: | Строка 160: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Технические проблемы, связанные с арифметическим кодированием, полностью решены. Оставшиеся нерешенными | Технические проблемы, связанные с арифметическим кодированием, полностью решены. Оставшиеся нерешенными задачи связаны с моделированием – разложением входного набора данных на последовательность событий, причем набор событий, возможных в каждой точке набора данных, должен быть описан распределением вероятностей, пригодным для ввода в кодер. Вопросы моделирования полностью зависят от конкретного применения. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == |
правок