Сжатие по Хаффману - теоретический вопрос.

[s-andriano]

Хотелось бы узнать мнение программистов по следующему вопросу:
Можно ли реализовать алгоритм сжатия Хаффмана, считая атомом (минимальной неделимой единицей информации) байт?

Под атомом подразумевается именно неделимая единица информации, а не атом в смысле Лиспа и не атомарная операция.

Для определенности будем считать, что сжимать нужно текст на естественном языке в однобайтовой кодировке (избыточность 80-85%).

Вопрос возник из теоретического спора.

Если будут наброски в коде/псевдокоде, хотелось бы видеть их в стиле Паскаль/Делфи.

PS. Не обнаружил на форуме разделав по алгоритмам либо общим вопросам программирования, поэтому с учетом последнего замечания размещаю тему здесь.

[evg_m]

смотрим исходный алгоритм

видим есть битовые N-граммы текста (байт, знак ASCII это просто 8 бит).
и есть битовое же дерево.

1. меняем исходную однобайтовую маркировку на маркировку N-грамм текста (N байт), чему д.б. равно N? в принципе любым >=2.
2. меняем двоичное дерево (узел - две ветви) на "байтовое" (узел - 256 ветвей).
ВСЕ! Получили теоретический алгоритм для неделимого байта.

Вопрос возник из теоретического спора.

[s-andriano]

Правильно ли я понимаю, что это будет алгоритм сжатия по Хаффману?

[evg_m]

Правильно ли я понимаю, что это будет алгоритм сжатия по Хаффману?

если в ссылке описан именно он, то почему бы и нет.

Это действительно Хаффман, или что-то другое?
С N-граммами вопросов нет, N-грамма в разных алфавитах (бит/байт) все равно остается N-граммой. (=>Хаффман)
Весь вопрос в замене двоичного дерева на байтовое дерево.
Если после замены это останется тот же алгоритм (не реализация), то почему бы и нет.
Если же алгоритм изменится, то получаем модифицированный алгоритм.

Предвижу теоретический (скорее философский) спор о том что считать одним алгоритмом, что считать модификацией алгоритма, и как различить разные, но похожие алгоритмы (т.е. когда модификация алгоритма превращается в новый алгоритм).

Или же вы о том каков будет коэффициент сжатия при таком алгоритме?

Сжатие будет мы каждые N байт исходного файла заменяем на разное кол-во байт от 1 до log256(M) (логарифм по основанию 256 от числа различных встреченных N-грамм)
Хаффман классический 8 бит (байт) на 1 .. log2 (M) бит (М -число различных байт (битовые 8-граммы).

Можно предложить немного другую версию алгоритма (это уж точно будет модифицированный алгоритм).
1 байт длина последующей кодовой последовательности + кодовая последовательность.

если Хаффман это :
звучит так
замена N-граммы на разные по длине коды в зависимости от частоты встречаемости данной N-граммы.
то предложенный алгоритм полностью укладывается в оное!

[s-andriano]

Спасибо.
Надо будет попробовать.