Алгоритм быстрого вычисления энтропии шеннона на малых выборках для длинных кодов биометрии с существенно зависимыми разрядами

Оценка энтропии длинных кодов по Шеннону является задачей высокой экспоненциальной вычислительной сложности при увеличении длины бинарной кодовой последовательности. Параллельно быстро растет объем выборки, на котором нужно оценивать вероятности появления редких событий. Целью статьи является упрощение вычислений за счет перехода в логарифмические пространства вероятностей появления редких событий и логарифма длины анализируемого кода. Показано, что в пространстве двойных логарифмов для кодов с зависимыми разрядами хорошо работает линейная экстраполяция. Это в конечном итоге и позволяет ускорить оценку энтропии длинных кодов за счет отказа от обработки больших объемов исходных данных по формуле Шеннона. По классической формуле Шеннона необходимо оценивать вероятность появления тех или иных кодовых состояний, что приводит к усложнению задачи при росте длины кода. Приходится ждать появления редких событий. Предложено упростить задачу за счет симметризации корреляционной матрицы анализируемых кодов. Исходная асимметричная корреляционная матрица произвольных кодов заменяется на эквивалентную ей, в которой все коэффициенты корреляции вне диагонали положительны и одинаковы. Коэффициенты симметризованной матрицы получены усреднением модулей коэффициентов корреляции исходной асимметричной матрицы. Оценка коэффициентов корреляции является задачей, имеющей квадратичную вычислительную сложность. То есть оценка энтропии по предложенному алгоритму вместо экспоненциальной вычислительной сложности имеет квадратичную вычислительную сложность. Приведена номограмма связи логарифма вероятности ошибок второго рода (эквивалента энтропии Шеннона) с длиной кодовой последовательности коэффициентов корреляционной сцепленности ее разрядов $r = \{0.0, 0.2, 0.3, \dots, 0.8\}$. Алгоритм работоспособен на малых выборках объемом от $16$ до $32$ примеров анализируемых кодовых последовательностей.