Среди методов анализа информации, в данной статье представлен анализ распределения плотности информации в битовом блоке данных. Данный метод может быть ориентиром при разработке методов сжатия информации, так как дает оценки как распределена плотность информации в зависимости от состава блока, который определяется количеством нулей и единиц, формирующих битовый блок данных.
Задан входной поток с длиной CT бит. Далее определяется количество нулей и единиц в блоке, тогда можно определить количество комбинаций которые задает данный набор нулей и единиц при заданной длине блока по формуле подсчета перестановок:
N=CT!/(K0!·K1!) (1)
где
N — количество перестановок, определяющие количество комбинаций;
CT — длинна блока в битах, CT=K0+K1;
K1 — количество единиц в блоке;
K0 — количество нулей в блоке.
Данная формула определяет количество перестановок которые дают заданные количество нулей и единиц в битовом блоке.
Например, для 16 бит длины блока комбинации, представляются таблицей:
![Таблица 1 — Информация блока длинной 16 бит Таблица 1 — Информация блока длинной 16 бит](https://habrastorage.org/getpro/habr/upload_files/e7a/b65/89c/e7ab6589ce69c057a422d4f072679992.png)
где
СТ - количество бит в блоке;
K0,K1 - количество нулей и единиц в блоке;
N - количество комбинаций, которые задают нули и единицы в блоке;
Log2(N) - двоичный логарифм, показывающий количество перестановок в битовом виде(данные в столбце округлены);
I% - процент от полного диапазона 2^CT, который занимают перестановки(данные в столбце округлены).
Для 32 бит длины блока оценка комбинации в таблице 2:
![Таблица 2 — Информация блока 32 бита Таблица 2 — Информация блока 32 бита](https://habrastorage.org/getpro/habr/upload_files/a2d/9ca/5df/a2d9ca5df1b2806bd453f6df297820d1.png)
где
СТ - количество бит в блоке;
K0,K1 - количество нулей и единиц в блоке;
N - количество комбинаций, которые задают нули и единицы в блоке;
Log2(N) - двоичный логарифм, показывающий количество перестановок в битовом виде(данные в столбце округлены);
I% - процент от полного диапазона 2^CT, который занимают перестановки(данные в столбце округлены).
![Рисунок 1 - График распределения количества комбинаций в 32х битном блоке в зависимости от количества единиц в 32х битном блоке. Рисунок 1 - График распределения количества комбинаций в 32х битном блоке в зависимости от количества единиц в 32х битном блоке.](https://habrastorage.org/getpro/habr/upload_files/b05/629/d46/b05629d46f5dd9365913bb0ac3efbc77.png)
Данный график показывает, как распределена плотность информации в блоке длинной 32 бита и что основная часть информации в блоке распределена ближе к равенству количества нулей и единиц.
Оценка энтропии Шеннона и комбинаторного подхода
Энтропия Шеннона оценивается по вероятностям, но не учитывает длину блока. Если задать конкретную длину блока и количество нулей и единиц, и посчитать варианты в логарифмической шкале, то оценка будет расходиться с энтропией Шеннона.
Например:
1)Для блока длинной 32 бита и количеством единиц 4: количество комбинаций будет 35960 это ~15,13 бит.
2)Для блока длиной 16 бита и количества единиц 2:
количество комбинаций будет 120 это ~ 6,91 бит.
И при этом вероятности равны:
p(1)(4,32)=4/32=0.125
p(1)(2,16)=2/16=0.125
Значит, по оценке энтропии Шеннона для первого и второго случая энтропия одинаковая, так как вероятности одинаковые. Но в тоже время, если учитывать длину блоков исходных данных, количество информации будет разным.
И значит, количество информации зависит не только от количества нулей и единиц (что эквивалентно вероятности появления символов), но и от длинны блока содержащего их.
Анализ данных в битовом блоке и перестановки.
Блок длинной 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.
Вывод
На этих примерах и приемах можно построить сжатие в некоторых ситуациях для битового блока. И данный подход можно отнести к статистическим методам сжатия. Но в тоже время словарные методы тоже являются статистическими, но там часто повторяемые участки, хранятся в дополнительной памяти.
А также данный подход к оценкам, можно использовать как метод оценки количества информации в размерности количества перестановок и их изменениях.
Комментарии (9)
AmartelRU
16.08.2024 09:28Что такое эта Ваша "плотность информации"?
Битовый блок длины n, целиком состоящий из нулей, существует в единственном экземпляре, а состоящих из нулей наполовину блоков той же длины будет C(n, n/2) (почему бы Вам тоже не использовать число сочетаний непосредственно, не расписывая все эти факториалы?). Однако, это всё разные блоки информации, в каждом информация своя - какие-то уникальные n бит. Исходя из чего Вы эти блоки агрегируете по количеству нулей\единиц, не очень понятно.Столбцы N в таблицах - это же просто строки треугольника Паскаля для k = 16 и k = 32 соответственно, просто набор биномиальных коэффициентов.
Словарные методы сжатия НЕ являются статистическими. В статистических методах символы в строке считаются случайными и независимыми, вероятности их появления оцениваются относительными частотностями и наиболее "частым" символам назначаются наиболее короткие кодовые последовательности. В словарных методах, напротив, предполагается, что в строке встречаются не произвольные последовательности символов, а некий определённый набор этих последовательностей ("слова"). И предлагается не кодировать отдельные символы слов, а сразу целому слову назначать отдельный код. При этом никакого подсчёта количества появлений слова или учёта его длины зачастую не производится (т.е. та самая статистика не собиратся), да и назначаемые коды являются кодами фиксированной длины (хотя с ростом словаря она может иногда увеличиваться).
Ну и вообще, информацию же нельзя сжать (без потерь). Можно сжать данные, сократив избыточность кодирования содержащейся в них информации.
/
eevg Автор
16.08.2024 09:28Что такое эта Ваша "плотность информации"?
Битовый блок длины n, целиком состоящий из нулей, существует в единственном экземпляре.Оценивается не количество экземпляров, а сколько вариантов задают количество нулей и единиц в блоке. Если в блоке только нули, то количество вариантов один. А если к, примеру, в блоке 20 бит и 19 нулей и 1 единица, то эти характеристики задают 20 возможных вариантов перестановок, а это и есть количество информации. И соответственно в том варианте, где количество информации в блоке одинакового размера больше, там и выше плотность информации.
Словарные методы сжатия НЕ являются статистическими.
Словарные методы и статистические по сути не отличаются, идея в том чтобы часто повторяющиеся последовательности задать меньшим количеством бит. А приведенный в статье анализ показывает, что меньшее количество бит будет использовано ближе к случаю, когда количество единиц равно количеству нулей.
AmartelRU
16.08.2024 09:28а это и есть количество информации
К сожалению, нет. Информации в обоих вариантах по 20 бит.
Рассмотрим для простоты блок поменьше, из 2 бит. Всего существует четыре различных блока такой длины: 00, 01, 10, 11. Если Вы будете передавать какой-либо из этих блоков, то передать Вам понадобится в каждом случае одни и те же два бита - чтобы получатель знал, чему точно равен первый бит блока и чему равен второй.
Т.е. Ваш блок информации из n бит и будет содержать n бит информации, вне зависимости от того, какие конкретно значения битов в этом блоке.
eevg Автор
16.08.2024 09:28Анализ на 2 битовом блоке не очень удобный.
Суть в том что, если в канале количество нулей и единиц приблизительно равно по количеству, то в канале передается больше информации, чем когда преимущественно нули или единицы.
eevg Автор
16.08.2024 09:28И еще если, например, когда в блоке количество единиц и нулей равны, но этот диапазон не используется, то туда можно переложить данные из других соотношений нулей и единиц, которые в сумме с разметкой влазят в свободный диапазон.
Что может быть эквивалентно кодированию более длинных последовательностей определенной конфигурации, более короткими определенной конфигурации.
vilgeforce
Не изобрели ли вы энтропию Шеннона?
eevg Автор
Энтропия Шеннона оценивается по вероятностям, но не учитывает длину блока. Если задать конкретную длину блока и количество нулей и единиц, и посчитать варианты в логарифмической шкале, то ОЦЕНКА БУДЕТ РАСХОДИТЬСЯ С ЭНТРОПИЕЙ ШЕННОНА.
eevg Автор
Например:
Для блока длинной 32 бита и количеством единиц 4: количество комбинаций будет 35960 это ~15,13 бит.
Для блока длиной 16 бита и количества единиц 2:
количество комбинаций будет 120 это ~ 6,91 бит.
И при этом вероятности равны:
p(1)(4,32)=4/32=0.125
p(1)(2,16)=2/16=0.125
eevg Автор
И значит количество информации зависит не только от количества нулей и единиц (что эквивалентно вероятности появления символов), но и от длинны блока содержащего их.