там отдельные символы кодируются кодами Хаффмана, а где это возможно, даются ссылки на ранее встречавшиеся подстроки.
Если убрать коды Хаффмана, то это будет LZW-алгоритм или его модификации. Вещь древняя как мир, на него даже патент истёк.
А теперь я спокойно перестраиваю дерево, если вылезло за допустимую длину, а потом связываю листья и символы, вернее длины кодов и символы.
Если в конце концов между символами и листьями есть связь, то не понимаю, в чём вообще проблема. Если на дерево есть специальные ограничения, то и алгоритм должен быть соответствующим образом модифицирован. И тут совершенно не важно, ассоциировать ли символы и листья дерева сразу или в конце, главное, чтобы конечный результат был правильным. Я, правда, не вникал в тонкости такой реализации.
Если любопытно, то посмотрите мои малофункциональные, простые PNG-кодер и PNG-декодер.
Я некоторое время назад задался вопросом оптимизации PNG-файлов. Надо было для небольших спрайтов сделать максимально компактное base64 строковое представление для использования в HTML-игре. Направлений сжатия было три: 1) вырезать всю левую информацию, хранящуюся в необязательных тегах (типа когда и в какой программе создан файл); 2) урезать таблицу палитры (потому что некоторые глупые программы делают её размером 256, когда цветов в картинке не больше десятка); 3) перекодировать и пережать само содержимое изображения (без внесения искажений). Я нашёл две консольные программы и статьи, объясняющие как ими пользоваться. Первые два пункта делаются одной программой, третий — второй. Вторую программу можно заставить брутфорсом перебирать все доступные для PNG алгоритмы компрессии и выбрать тот, который даст наилучший результат. Думаю, после подобной обработки более компактную картинку уже не получится получить без дополнительного урезания количества цветов в ней. К сожалению, программы и ссылки на статьи остались на старом компьютере, который сейчас в полуразобранном состоянии.
-- 11.01.2021, 12:40 --Нашёл название второй программы:
PNGCrush. И
статью, наверное. Не уверен, что это та самая.
