Поліноміальне представлення двійкових дерев ентропійних бінарних кодів

Анотація

Важливою складовою потокового обміну великими об'ємами інформації є алгоритми стискання інформаційного потоку, які своєю чергою поділяють на алгоритми стискання без втрат (ентропійні) --- Шенона, Хафмана, арифметичне кодування, умовно стискаючі - LZW та інші бієкції інформаційного конусу, алгоритми стискання з втратами, наприклад, mp3, jpeg та низка інших.

Під час побудови алгоритму стискання з втратами важливим є дотримуватись певної формальної стратегії. Сформулювати її можна таким чином: після опису множини об'єктів, які є атомарними елементами обміну в інформаційному потоці, необхідно побудувати абстрактну схему цього опису, що дозволить визначити межу для абстрактних зрізів цієї схеми, за якою починаються допустимі втрати.

Підходи до виявлення абстрактної схеми, що породжує алгоритми стискання з допустимими втратами, можуть бути отримані з контексту предметної області. Наприклад, алгоритм стискання аудіопотоку може розділяти сигнал на прості гармоніки та залишає серед них ті, що розташовані в певному діапазоні сприйняття. Таким чином, отриманий на виході сигнал є певною абстракцією вхідного, що містить важливу інформацію згідно з контекстом слухового сприйняття аудіопотоку та представлений меншою кількістю інформації. Подібний підхід використовується в форматі mp3, який є стискаючим представленням.

На відміну від алгоритмів стискання з втратами, ентропійні алгоритми стискання не вимагають аналізу контексту, а можуть бути побудовані згідно з частотною картиною. Серед відомих алгоритмів побудови таких кодів можна згадати алгоритм Шеннона-Фано, алгоритм Хафмана та арифметичне кодування.

Знаходження інформаційної ентропії для заданого коду Шеннона є тривіальною задачею. Обернена задача, а саме пошук відповідних кодів Шеннона, що мають наперед задану ентропію та з невизначеними ймовірностями, що є від'ємними цілими степенями двійки, є достатньо складною. Вона може бути вирішена прямим перебором, але суттєвим недоліком цього підходу є його обчислювана складність. У цій статті запропоновано альтернативний підхід до пошуку таких кодів. Описана техніка поліноміального представлення двійкових дерев бінарних кодів Шеннона з імовірностями, що є від'ємними цілими степенями двійки, дає змогу будувати відповідні коди за відомим значенням інформаційної ентропії.