Среди методов анализа информации, в данной статье представлен анализ распределения плотности информации в битовом блоке данных. Данный метод может быть ориентиром при разработке методов сжатия информации, так как дает оценки как распределена плотность информации в зависимости от состава блока, который определяется количеством нулей и единиц, формирующих битовый блок данных.
Задан входной поток с длиной CT бит. Далее определяется количество нулей и единиц в блоке, тогда можно определить количество комбинаций которые задает данный набор нулей и единиц при заданной длине блока по формуле подсчета перестановок:
N=CT!/(K0!·K1!) (1)
где
N — количество перестановок, определяющие количество комбинаций;
CT — длинна блока в битах, CT=K0+K1;
K1 — количество единиц в блоке;
K0 — количество нулей в блоке.
Данная формула определяет количество перестановок которые дают заданные количество нулей и единиц в битовом блоке.
Например, для 16 бит длины блока комбинации, представляются таблицей:
где
СТ - количество бит в блоке;
K0,K1 - количество нулей и единиц в блоке;
N - количество комбинаций, которые задают нули и единицы в блоке;
Log2(N) - двоичный логарифм, показывающий количество перестановок в битовом виде(данные в столбце округлены);
I% - процент от полного диапазона 2^CT, который занимают перестановки(данные в столбце округлены).
Для 32 бит длины блока оценка комбинации в таблице 2:
где
СТ - количество бит в блоке;
K0,K1 - количество нулей и единиц в блоке;
N - количество комбинаций, которые задают нули и единицы в блоке;
Log2(N) - двоичный логарифм, показывающий количество перестановок в битовом виде(данные в столбце округлены);
I% - процент от полного диапазона 2^CT, который занимают перестановки(данные в столбце округлены).
Данный график показывает, как распределена плотность информации в блоке длинной 32 бита и что основная часть информации в блоке распределена ближе к равенству количества нулей и единиц.
Оценка энтропии Шеннона и комбинаторного подхода
Энтропия Шеннона оценивается по вероятностям, но не учитывает длину блока. Если задать конкретную длину блока и количество нулей и единиц, и посчитать варианты в логарифмической шкале, то оценка будет расходиться с энтропией Шеннона.
Например:
1)Для блока длинной 32 бита и количеством единиц 4: количество комбинаций будет 35960 это ~15,13 бит.
2)Для блока длиной 16 бита и количества единиц 2:
количество комбинаций будет 120 это ~ 6,91 бит.
И при этом вероятности равны:
p(1){4,32}=4/32=0,125,
p(0){28,32}=28/32=0,875;
p(1){2,16}=2/16=0,125,
p(0){14,16}=14/16=0,875;
Расчет по формуле Шеннона:
I=-(0,125*log2(0,125)+0,875*log2(0,875))~ 0,5435 бит.
Значит, по оценке энтропии Шеннона для первого и второго случая энтропия одинаковая, так как вероятности одинаковые. Но в тоже время, если учитывать длину блоков исходных данных, количество информации будет разным.
И значит, количество информации зависит не только от количества нулей и единиц (что эквивалентно вероятности появления символов), но и от длинны блока содержащего их.
Анализ данных в битовом блоке и перестановки.
Блок длинной n бит содержит 2^n комбинаций, в данной статье приводится описание как в блоке информации длинной n бит распределена плотность информации в зависимость от количества нулей и единиц, которые формируют данный блок. В формуле (1) показано как оценить количество комбинаций которые формируются при заданной длине блока CT и количества составляющих нулей и единиц K0, K1. Показано, что максимальное количество комбинаций и значит плотность информации будет при K0=K1. И в отличии от подхода Шеннона, где количество информации характеризуется вероятностью появления символа, то в данном методе можно точно оценить количество информации для заданного входного блока бит.
И можно сделать вывод, что для битового блока длинной CT бит наиболее более плотное распределение информации при K0=K1 для K0+K1=CT.
Также можно сделать вывод, что количество комбинаций N для заданного K0,K1 меньше чем 2^CT. И значит, что если не было бы необходимости в хранении K0,K1 как исходных данных, то было бы возможно получать сжатие:
sz=(CT!/(K0!·K1!)) / (2^CT) (2)
И если в полном виде, то для сжатия можно сохранять информацию
K0,K1,NPR;
где K0-количество нулей в блоке,
K1-количество единиц в блоке,
NPR — номер перестановки из нулей и единиц для заданных K0,K1.
Функция преобразования битовой строки в номер перестановки
NPR=PR(CT,BSTR);
где
CT - длинна битовой строки BSTR,
BSTR — битовая строка,
NPR — номер перестановки.
Функция преобразования номера перестановки в битовую строку
BSTR=BS(K0,K1,NPR);
где
K0-количество нулей в блоке,
K1-количество единиц в блоке,
NPR — номер перестановки,
BSTR — битовая строка.
NPR будет лежать в диапазоне от 0 до CT!/(K0!·K1!) на чем можно получить сжатие в некоторых случаях.
И также можно задаться определенной длинной блока в кодере и декодере L, тогда, например, можно передавать только K1, а K0 получать по формуле K0=L-K1, что добавит степень сжатия исходных данных.
Вывод
На этих примерах и приемах можно построить сжатие в некоторых ситуациях для битового блока. И данный подход можно отнести к статистическим методам сжатия. Но в тоже время словарные методы тоже являются статистическими, и там часто повторяемые участки, хранятся в дополнительной памяти.
А также данный подход к оценкам, можно использовать как метод оценки количества информации в размерности количества перестановок и их изменениях.
