Английское название метода - Enumerative Coding, или ENUC.

Цель - сжатие блока Л-битовых элементов в предположении, что у него есть одна важная характеристика С, которую выгодно сжимать отдельно от остальных.

Такой характеристикой С может быть, например, сумма всех элементов блока (или же произведение), или максимальное значение элемента, а менее важной - вклад конкретных элементов в эту сумму (произведение), или по­ложение элемента с максимальным значением внутри блока.

Основная идея состоит в том, чтобы формировать два блока: сохра­няющий самую важную характеристику С и содержащий остальные данные D (необходимые для восстановления исходного блока) - так, чтобы все ком­бинации D были почти равновероятны. И далее обрабатывать эти блоки раз­дельно: их характеристики существенно различны.

Например, сжимая блок из 3- битов (Л=1, длина 1=3), метод сохраняет сумму битов 5", 0< S <3 (для ее"записи требуется уже 2 бита), а также запи­сывает положение единицы Z_u если 5=1, положение нуля Z₀, если 5=2, или ничего, если 5=0 или 5=3.

И далее считаем, что все 3 значения Z₀ равновероятны, а также все 3 зна­чения Z\ - равновероятны.

Аналогично при сжатии блока X из 7 бит: сохраняем его сумму 0£ 5 <П в 3 бита и далее, в зависимости от этой суммы, номер к-й комбинации битов (во множестве всех возможных К&к], считающихся равновероятными), которая описывает текущий блок X известной длины Ь=П с известной суммой 5.

■ Если 54) или 5=7, сохранять к не нужно.

■ Если 5=1 или 5=6, есть 7 вариантов для к.

■ Если 5=2 или 5=5, есть 21 вариант.

■ Если 5=3 или 5=4, есть 35 вариантов.

В общем случае, если длина битового блока L, а сумма его битов 5, то вариантов для к существует

V=L\/(S\-(L-S)\ ),

т. е. (1-(5-1))-(1-1)...1/(1-2-3...5)

Как легко заметить, при любых L и 5 числитель дроби кратен знаменате­лю и деление будет без остатка. Произведение первых л сомножителей чис­лителя кратно произведению первых п сомножителей знаменателя.

Номера вариантов метод ENUC считает равновероятными.

Таким образом, всего требуется log₂(X+l) бит для записи S (в данном примере самая важная характеристика С - это S, сумма битов блока) плюс log₂(0 бит для записи остальных (равновероятных) данных D (в нашем примере - это У, вычисляемая по формуле (1.4)).

Если требуется сжать блок R-битовых элементов X[i], известно два
подхода: ,_?

1. Преобразовать его в блок битов В, помещая в В на каждом j-m шаге X[i] нулей и одну единицу (или, наоборот, Х[/] единиц и один нуль).

2. Преобразовать его в R блоков битов: в первом блоке - старшие биты, во втором - следующие (возможно, сортированные по первым, методом сортировки параллельных блоков), затем третьи по старшинству и т. д., до R-x (всеу'-е можно сортировать по всем предыдущим, старшим (/-1) битам элементов блока X).

Размер данных в результате применения ENUC уменьшается, если дан­ные соответствуют ENUC-модели: важна одна характеристика, значения ос­тальных равновероятны.

Методы этой группы являются трансформирующими и блочными

(т. е. могут применяться только в том случае, когда задана длина блока с данными, подлежащими сжатию).

В общем случае скорость работы компрессора равна скорости деком­прессора и зависит и от размера данных и от их содержания. Оба идут по создаваемому множеству вариантов К^к]: компрессор - чтобы найти к -положение сохраняемого варианта (его номер) в создаваемом множестве К& декомпрессор - чтобы найти вариант, зная его номер к.

Впрочем, если сжимаемых блоков много, скорость работы декомпрессо­ра выше скорости компрессора. Скорость обоих выше (и уже не зависит от содержания данных), поскольку не требуется каждый раз создавать множе­ство вариантов. Но памяти необходимо больше, так как требуется хранить описания множеств.

Грейферы для металлолома: ломовоз. Ford CARGO, всегда в наличии.

Так, в рассмотренном выше случае сжатия 7-битового блока это будет три массива: из 7, 21 и 35 элементов. Если сжимаем поток 7-битовых бло­ков, имеет смысл один раз создать эти 3 массива К|[7], К₂[21], К₃[35]. Ком­прессор будет делать поиск заданной комбинации битов W в этих К_ь К₂, К₃ и сохранять номер к, а декомпрессор, получая к, восстанавливать исходную комбинацию W. С целью еще более повысить скорость можно сделать все 3 массива длиной 2⁷=128.