Мне нужна помощь, чтобы проанализировать этот метод программирования для сжатия массива

Я надеюсь, читатели знакомы с теорией информации Шеннона, в которой говорится, что информационное содержание, связанное с событием a с вероятностью p(a), равно -log(p(a)). С точки зрения непрофессионала, если вам нужно представить число в диапазоне от 0 до 7, вам потребуется как минимум -log (1/8) = log (8) (где основание равно 2), т.е. 3 бита.

Предположим, имеется массив целых чисел в диапазоне от 0 до 255. Вместо того, чтобы хранить массив в виде 8-битных чисел, я сначала отсортирую массив в порядке возрастания (конечно, сохраняя резервную копию). Вместо того, чтобы кодировать каждый элемент массива как 8-битное целое число, я выведу его позицию в отсортированном массиве. Теперь проблема состоит в том, чтобы сообщить декодеру или приемнику этот отсортированный массив. Я выведу первое (наименьшее) целочисленное значение как 8-битное число, затем к этому числу будет добавлено приращение и вскоре. Сначала весь отсортированный массив, за которым следует порядок элементов, то есть значения позиции.

Пример: исходный массив-> 231 , 3 , 45 , 0 , 23 , 32 , 78

отсортированный массив-> 0,3,23,32,45,78,231

закодированная информация равна 0 ( первый элемент отсортированного массива как 8-битное число), затем 3 (это увеличение на 0), затем 20, затем 9, затем 13, затем 33, затем 153.

после отправки первого числа и последующих дельт я отправлю заказ i.е, поскольку здесь 7 целых чисел, мне понадобится трехбитное число для порядка, 3 (позиция 0 в исходном массиве), затем 1 (позиция 3), затем 4 (позиция 23), затем 5 (позиция 32), затем 2 (позиция 45), затем 6 (позиция 78), затем 0 (позиция 231).

т. е. значения позиций теперь равны 3 , 1 , 4 , 5 , 2 , 6 , 0

Анализ, чтобы увидеть, будет ли эта схема сжимать:

первое число -> 8 бит (на самом деле может потребоваться меньше битов так как это наименьший)

следующие 6 чисел -> 5 бит (проблема в том, что мы можем кодировать 0,3,20,9,13 с 5 битами, но не 33 и 153, которые нам, возможно, придется кодировать как 31 (максимум для 5 бит))

7 позиций по 3 бита в каждой->21 бит

всего->8+6*5+21=59. что больше, чем 56 бит, которые нам потребовались бы для кодирования 7 чисел по 8 бит каждое, и мы добились расширения, а не сжатия, и наша схема имеет потери, поскольку некоторые большие числа мы не смогли правильно представить.

Усложним эту схему.

Я буду кодировать первый 0 как 8-битное число, за которым сразу же следует код последнего числа 231.Затем я отправлю код для 3, следующее увеличение на 0, затем код для 153, уменьшение на 231, затем 20, затем 33, 9,13

, т.е. я отправил в другом порядке-> вместо 0,3,20,9, 13,33,153 я отправлю как 3,153,20,33,9,13

то, что я получаю, это последовательное уменьшение динамического диапазона вы видите, что мы отправили 0, затем 231, затем 3, затем 153 к этому времени диапазон значений уменьшает, я имею в виду, что следующее приращение до 3, которое будет 20, не может быть больше, чем предпоследнее число, т.е. 78, а число 20 не может превышать 75 (если оно идет, то третье число (3 + 76 (скажем)) будет больше, чем 78 явное нарушение нашего предположения о сортировке.

Если вы до сих пор поняли идею, у меня есть дальнейшая улучшенная схема использования идеи бинарного поиска для дальнейшего сокращения динамического диапазона и поставить эту технику на стероиды. Вот отсортированный массив

0 , 3 , 23 , 32 , 45 , 78 , 231

обратите внимание, что отсортированный массив имеет 7 чисел, а средний — 32. Итак, теперь мы закодируем эти 32 с помощью 8 бит. тогда мы отправим дельты по предварительному заказу. то есть следующее число после 32 будет 3, которое будет закодировано как 29 (т.е. 32-3), а следующее будет 78 закодировано как 46 (78-32), затем 0 закодировано как 3 (3-0), затем 23 закодировано как 20 (23-3), затем 45, закодированный как 33(78-45), затем последний 231, закодированный как 153(231-78).

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

мы будем отправлять отсортированный массив как 32 (диапазон 0–255, т. е. 8 бит), 29 (диапазон 0–32, т. е. 6 бит), 46 (диапазон 32–255, т. е. 8 бит), 3 (диапазон 0–3). 2 бита), 20 (диапазон 3-32, 5 бит), 33 (диапазон 32-78, 6 бит), 153 (78-255, 8 бит)

, всего 8+6+8+2+ 5 + 6 + 8 = 43, что без потерь и больше, чем наша первоначальная оценка 38 (8 бит + 5 * 6 бит), поэтому это добавлено с 7 значениями позиций по три бита каждый, всего 43 + 21 = 64 больше, чем 56 , Наша схема все еще расширяется.

Что можно улучшить с номерами позиций, которые состоят из 21 бита. Поскольку каждый раз, когда мы отправляем информацию о позиции, количество позиций уменьшается на единицу, если у нас есть 7 позиций для отправки, тогда количество битов равно log(7)+log(6)+log(5).... Это тогда log(fact (7)) бит, где все логарифмы по основанию 2.

Заметьте, что я использовал формулу log(a)+log(b)=log(ab)

Это равно 12,299, что при добавлении к 43 равно 55.299, что чуть ниже 56. Но это не практично. Нам нужно как минимум 3(диапазон 7)+3(диапазон 6)+3(диапазон 5)+2 (диапазон 4) + 2 (диапазон 3) + 1 (диапазон 2) + 0 (диапазон 1) = 14, что при добавлении к 43 дает 57, что является расширением.

Целью этих усилий является уменьшение размера данных по крайней мере на 1 бит. Если мы сожмем 56 бит в 55 без каких-либо предположений о данных, то мы можем взять выход из 55 бит и снова сжать его до 54 бит и скоро. Это выглядит невозможным, и идея похожа на вечные машины. Теперь задача состоит в том, чтобы увидеть, что мешает нам сжать больше.

Мне нужно проанализировать пример большего массива, чтобы увидеть, могут ли 43 бита отсортированного массива быть меньше 43. Также в чем преимущество разделения массива на множество частей и кодирования каждой части отдельно. Также цель состоит в том, чтобы найти формулу для расчета количества битов, необходимых для представления отсортированного массива. т.е. учитывая размер массива и диапазон элементов массива, как найти числа, подобные 43.

Давайте снова возьмем эти 3,1,4,5,2,6,0 как несортированный массив и заметим, что эта последовательность является одной из 5040. перестановки семи чисел от 0 до 6. Мы можем представить это как 13-битное число (12,299, как предполагает теория).

Мне нужно знать, можно ли еще больше сжать этот массив.