logo
Лекция_Представление_информации_в_компьютере1

Метод упаковки

Суть метода упаковки заключается в уменьшении количества бит, отводимых для кодирования символов, если в сжимаемом массиве данных присутствует только небольшая часть используемого алфавита.

Пример. Допустим, входной текст состоит только из десятичной записи целых чисел и знаков «минус», разделенных пробелами (например, «280 - 1296 48 40 365 - 159 13 777»). Множество символов, встречающихся в таком тексте, состоит всего из 12 символов (цифры от «0» до «9», знак «-» (минус) и пробел). Для кодирования такого количества символов достаточно всего четырех бит, целого байта для этого много. Если упаковать коды данных символов в 4 бита (например, так: «0» как «0000», «1» как «0001», ... «9» как «1001», «-» как «1110», пробел как «1111»), то можно будет кодировать по два символа входного текста одним байтом в выходном массиве. В результате получим двукратное сжатие данных. Формат записи чисел, при котором число записывается в десятичной системе, а цифры числа кодируются 4-битовыми кодами, называется BCD-форматом (Binary Coded Decimal, или двоично-десятичная запись). BCD-формат нередко используется в программировании для хранения целых чисел, например в базах данных.

Пример. Входной текст «КОЛ_ОКОЛО_КОЛОКОЛА» содержит всего 5 различных символов («К», «О», «Л», «А» и «_»), следовательно, каждый символ может быть закодирован тремя битами. Всего в исходном тексте 18 символов, так что потребуется 18 × 3 = 54 бита. Округлив это значение с избытком до целого числа байт, получим размер сжатого массива — всего 7 байт. Коэффициент сжатия равен 18/7 = 2,(571428) ≈ 2,6.

Одно из преимуществ метода упаковки заключается в том, что любой фрагмент сжатых данных можно распаковать, совершенно не используя предшествующие данные. Действительно, зная номер требуемого символа N и длину кодов символов М, можно вычислить местоположение кода символа в сжатом массиве данных:

Метод упаковки дает хорошие результаты, только если множество используемых символов невелико. Например, если в тексте используются только прописные русские буквы и знаки препинания, то текст может быть сжат всего на 25%: 33 русские буквы плюс пробел и знаки препинания — итого около 40 символов. Для их кодирования достаточно 6 бит. При упаковке текст уменьшится до 3/4 от первоначального объема.