4430
правок
Сжатие целочисленных последовательностей и множеств: различия между версиями
Материал из WEGA
Сжатие целочисленных последовательностей и множеств (посмотреть исходный код)
Версия от 11:42, 27 февраля 2018
, 27 февраля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Основные результаты == | == Основные результаты == | ||
Основное ограничение на статические коды выражается неравенством Крафта-Макмиллана | Основное ограничение на статические коды выражается неравенством Крафта-Макмиллана [13]: если кодовое слово для символа x имеет длину <math>\ell_x \;</math>, то необходимо выполнение неравенства <math>\sum_{x = 1}^U 2^{- \ell_x} \le 1</math> для того, чтобы код был декодируемым слева направо и ни одно кодовое слово не было префиксом любого другого кодового слова. Еще одним важным ограничением является комбинаторная стоимость описания множества. Если подмножество из n элементов множества 1, ..., U выбирается случайным образом, то для описания этого подмножества требуется <math>log_2 \; \binom{U}{n} \approx n \; log_2 \; \frac{U}{n}</math> бит. | ||
'''Унарный и бинарный код''' | '''Унарный и бинарный код''' | ||
В качестве первого примера рассмотрим метод унарного кодирования, в котором символ x представлен в виде x - 1 бит в значении «1», после которых идет один бит в значении «0». К примеру, три первых символа сообщения | В качестве первого примера рассмотрим метод ''унарного кодирования'', в котором символ x представлен в виде x-1 бит в значении «1», после которых идет один бит в значении «0». К примеру, три первых символа сообщения <math>M_1 \;</math> будут кодироваться последовательностью «0-110-0»; дефисы здесь имеют исключительно иллюстративную цель и не являются частью кодированного представления. Поскольку унарный код символа x имеет длину ровно x бит, для этого способа кодирования крайне предпочтительны небольшие целые числа; он имеет соответствующее идеальное распределение вероятностей появления символов (распределение, для которого данный конкретный шаблон длин кодовых слов позволяет получить минимальную длину сообщения), задаваемое формулой <math>Prob(x) = 2^{-x} \;</math>. | ||
У унарного кода есть полезное свойство – бесконечная длина. Однако, за исключением случаев, когда сообщение M состоит главным образом из небольших целых чисел, унарный код является достаточно дорогостоящим. В частности, представление сообщения M = | У унарного кода есть полезное свойство – бесконечная длина. Однако, за исключением случаев, когда сообщение M состоит главным образом из небольших целых чисел, унарный код является достаточно дорогостоящим. В частности, представление сообщения <math>M = \langle s_1, ..., s_n \rangle</math> в виде унарного кода требует <math>\sum_i s_i \;</math> бит, а если M представляет собой представление подмножества 1...U с пробелами, его длина может составить U бит. | ||
Лучшим известным кодом для вычислений считается бинарный (или двоичный). Если | Лучшим известным кодом для вычислений считается ''бинарный'' (или ''двоичный''). Если <math>2^{k - l} < U \le 2^k \;</math> для некоторого целого k, то символы <math>1 \le s_i \le U \;</math> могут быть представлены <math>k \ge log_2 \; U</math> битами каждый. В этом случае код является ''конечным'', а идеальное распределение вероятности задается формулой <math>Prob(x) = 2^{-k} \;</math>. В случае <math>U = 2^k \;</math> имеет место соотношение <math>Prob(x) = 2^{-log_2 \; n} = 1/n</math>. | ||
Если U точно известно и не является степенью двойки, | Если U точно известно и не является степенью двойки, <math>2^k — U \;</math> кодовых слов можно сократить до длины k — 1 бит, получив ''минимальный двоичный код''. Символам 1 • • • 2k — U удобно присвоить короткие кодовые слова. При этом кодовые слова для оставшихся символов, (2k — U + 1) • • • U, по-прежнему будут иметь длину k бит. | ||
