(Наверно, это глупая идея. Но иногда даже самые глупые идеи приводят к неожиданным результатам.)
Текст шекспировской трагедии «Ромео и Джульетта» состоит примерно из 146 тысяч символов. Благодаря английскому алфавиту каждый символ можно описать одним байтом. Так что размер текстового файла в обычном Unicode составляет примерно 142 КБ.
В статье Adventures With Compression её автор JamesG размышляет о соревнованиях по сжатию текста и предлагает интересную мысль:
Закодировать текст в виде изображения и сжать это изображение. Мне понадобится алгоритм сжатия изображений без потерь. Использование RGB увеличит количество значений, связанных с каждым словом. Возможно, стоит преобразовать изображение в оттенки серого? А может, эту идею и не стоит исследовать.
Алгоритмы компрессии изображений обычно очень неплохо справляются с поиском паттернов в изображениях и с их сжатием. Поможет ли нам сжатие изображений, если мы преобразуем текст в картинку?
Английский язык и его пунктуация не особо сложны, так что пьеса содержит всего 77 уникальных символов. Значение ASCII каждого символа находится в интервале от 0 до 127. Давайте создадим изображение в оттенках серого, в котором каждый пиксель имеет тот же уровень серого, что и значение ASCII символа.
Вот как это выглядит после сжатия в PNG без потерь:
Размер снизился до 55 КБ! Это примерно 40% от размера исходного файла. Это чуть меньше, чем ZIP, и примерно на 9 байтов больше, чем сжатие Brotli.
Файл можно считывать следующим кодом на Python:
from PIL import Image
image = Image.open("ascii_grey.png")
pixels = list(image.getdata())
ascii = "".join([chr(pixel) for pixel in pixels])
with open("rj.txt", "w") as file:
file.write(ascii)Но маловероятно, что даже при помощи самых современных алгоритмов сжатия изображений его можно сжать ещё сильнее — картинка похожа на случайный шум. Да, мы с вами знаем, что в ней хранятся данные. И специалист по статистике, вычислив энтропию, вероятно, определит, что файл содержит читаемые данные. Но алгоритмы сжатия изображений работают в другой сфере. Они ищут блоки одного цвета, предсказуемые градиенты или другие статистические признаки.
Но всё-таки у нас получилось! Сжатое без потерь изображение — довольно эффективный способ сжатия текста ASCII.
Комментарии (30)
ednersky
17.01.2024 08:28+4не помню точно, но в районе 2010 на какой-то конфе (может хайлоад, а может РИТ) один чудик докладывался, что они взяли формат GIF без сжатия и передавали в его страницах html, js, css и так далее. А потом на стороне клиента всё это в JS распаковывали.
Время тогда было такое, что динамических сайтов ещё почти не было и вот чувак придумал такой вот бандл.
belch84
17.01.2024 08:28Благодаря английскому алфавиту каждый символ можно описать одним байтом
Английский язык и его пунктуация не особо сложны, так что пьеса содержит всего 77 уникальных символов. Значение ASCII каждого символа находится в интервале от 0 до 127
Первое утверждение немного противоречит второму (более точному), для английского достаточно семи бит
Metotron0
17.01.2024 08:28Но ведь одним байтом можно описать, два не требуется. В чём противоречие?
belch84
17.01.2024 08:28+2Благодаря английскому алфавиту каждый символ можно описать одним байтом
Можно сравнить это с утверждением:
Благодаря русскому алфавиту каждый символ можно описать одним байтом,
то же будет справедливым, по-видимому, для любого европейского языка. Неточность эта не бог весть какая серьезная, но все же фраза не вполне логична, особенно когда речь идет о сжатии текста
querta
17.01.2024 08:28-4Сравнить утверждения можно, но в ваше - заведомо ложное.
В английской латинице 1 символ = 1 байту. В русской кириллице 1 символ занимает 2 байта. Так что, эта фраза не будет справедлива для других языков. А в некоторых странах в латинице есть дополнительные символы. Например ł, å, ø - каждый весит по 2 байта
belch84
17.01.2024 08:28+11Сравнить утверждения можно, но в ваше - заведомо ложное.
Надеюсь, вы осознаете, что ваше утверждение является слишком уж безапелляционным? Вы что-нибудь слышили об однобайтовых кодировках Windows-1251, КОИ-8?
В русской кириллице 1 символ занимает 2 байта.
Вам не кажется. что это утверждение ложно до тех пор, пока не указано, о какой кодировке идет речь?
querta
17.01.2024 08:28-5При чем тут windows-1251 или кои-8 если в статье речь идет о Unicode?
Zara6502
17.01.2024 08:28+8автор сначала сделал ложное (или точнее - кривое) утверждение, а только потом выбрал Unicode.
в латинском 26 букв, так что достаточно 5 бит, это известно всем, кто хоть что-то читал по кодированию английских символов. даже добавляя знаки препинания и цифры трудно выбраться за 6 бит, не говоря о 7.
утверждение автора про "уникальность" английского и требование всего одного байта является несуразным допущением, так как к свойству английского это вообще не относится.
более корректно было бы написать, что так как английских символов, цифр и знаков препинания сильно меньше чем 256, то можно использовать 1 байт для кодирования такой информации. Но эта фраза для меня, человека из 80-х, сама по себе режет слух не хуже изначальной авторской, так как история ПК и расцвет в 8-битную эпоху как бы намекает, что "256 символов хватит всем".
Metotron0
17.01.2024 08:28+1Байты файла интерпретировали не как буквы, а как точки? С некоторой степенью упрощения, игнорируя формат записи данных в png, можно сказать, что содержимое файла не поменялось, лишь добавились картиночные заголовки?
В png есть однобайтный монохромный формат, или там всегда RGB в три байта? А то можно было три буквы в одну точку собрать. Картинка бы визуально уменьшилась.
Ещё нужно решить проблему определения того, что текст уже кончился, а до заполнения прямоугольника картинки ещё есть место. Нужно отдельно сохранять длину.
binque
17.01.2024 08:28+7Так ведь формат PNG использует тот же алгоритм сжатия Deflate, что и ZIP. То есть по сути можно было просто записать текст в семибитной кодировке как битовый массив, а потом сжать обычным архиватором. И так размер должен получиться еще немного меньше, так как не потребуется заголовок PNG. Разве нет?
Vladislav_Dudnikov
17.01.2024 08:28+4Я вот тоже не понял, зачем нам вообще преобразовывать текст в картинку, да ещё и драгоценные бит терять на каждом символе.
Nikolaev_Nikolay
17.01.2024 08:28-1А как текст в картинку превратить!? Есть утилиты!? Разные шпионы и нехорошие люди кидались в дру друга картинками.
Metotron0
17.01.2024 08:28Берётся код символа, которые заведомо меньше 256, и рисуется точка с яркостью, равной этому значению.
Только нужно подобрать ширину и высоту картинки такие, чтобы остался как можно меньший пустой хвост. То есть, найти такие A и B, чтобы (A x B - textLength) было нулевым или положительным, но минимальным из возможных.
wmlab
17.01.2024 08:28Самый сильная компрессия текста достигается с помощью языковых моделей (наподобие ChatGPT). См. "LOSSLESS TEXT COMPRESSION USING LARGE LANGUAGE MODELS". Основная идея - в предсказании следующего токена. В примерах было 0.77 бит на символ. Для сравнения, у Zlib - 2.55.
Metotron0
17.01.2024 08:28Есть некоторое подозрение, что словарь, который нужно при этом таскать вместе с распаковщиком, превзойдёт по размеру любые несжатые файлы. Проще будет оставить файл с исходным текстом.
Vest
17.01.2024 08:28Ваш комментарий напомнил мне «архиватор Бабушкина». Там никакие словари не нужны.
Metotron0
17.01.2024 08:28Это два числа, которые нужно поделить друг на друга, чтобы в дробной части получить исходный набор байтов?
А ещё можно задать начальную позицию в числе пи и длину и просто взять оттуда нужный файл.
Или тоже делить, но хранить не сами числа, а начало и длину в числе пи и то же самое в числе e.
wmlab
17.01.2024 08:28Если бы только словарь токенов - это полбеды, это всего лишь алгоритм Хаффмана. Более популярные токены - короткий код, редкие - длинный. LLAMA требует огромные ресурсы для предсказания следующего токена и это сжимает гораздо лучше Хаффмана. Например, 1 (один бит), если следующий токен совпал с предсказанным и 0+ID токена, если не совпал. Настоящий алгоритм сложнее, но не суть. Да, требуется неординарная вычислительная мощность и память для сжатия и распаковки, но это максимально плотное сжатие текстов, превосходящее все, что было до сих пор. Практически, разумеется, малоприменимо.
Milliard
17.01.2024 08:28+2Английский язык и его пунктуация не особо сложны, так что пьеса содержит всего 77 уникальных символов. Значение ASCII каждого символа находится в интервале от 0 до 127. Давайте создадим изображение в оттенках серого, в котором каждый пиксель имеет тот же уровень серого, что и значение ASCII символа.
Непонятно, почему точки на изображении имеют яркость в диапазоне 0-127, а не 0-77. Если точнее, то в Пейнте нашел точки с яркостью от 10 до 117, но ширина диапазона все равно больше, чем 77.
LordDarklight
17.01.2024 08:28Ключевая ошибка автора тут в том, что тексты явно стоит сжимать не по буквам, а по словам - т.е. надо сначала составить словарь слов - перекодировать им текст, и только потом уже думать о преобразовании текста в изображение - т.е. условно говоря работать с палитрой.
Более того, в тексте ещё и разные сочетания слов любят повторяться - их тоже можно пытаться представить разными цветами. Причём тут ещё интересна тема того, что есть достаточно большое множество случаев, когда несколько подряд идущих - 3 или 4 часто в одном и том же тексте имеют не так уж много вариаций различного сочетания - их можно выявлять и кодировать очень сжатой форме - номер группы сочетания и подномер варианта.
Отдельная тема - знаки препинания - их формат кодирования должен иметь отличия и их нужно выносить на отдельный слой кодирования.
Но вообще - моё мнение - узкоспециализированный алгоритм сжатия текста, учитывающий специфику построения текстовых данных - сожмёт всегда лучше, чем какой-либо алгоритм другой направленности! Если говорить об обычном ёмком тексте, а не случайно сгенерированной тарабарщине, или каких-то очень специфических тексах, требующих для сжатия очень специфических подхода!
Но другое дело - это вопросы криптографии и стенографирования - тут уже другие критерии выходят на первое место, но вопрос сжатия тут тоже стоит очень остро
yamifa_1234
17.01.2024 08:28А как насчёт сжатия в jpg? На если текст упаковать в картинку а потом в сохранить аак в jpg, а затем обратно развернуть в текст то как сильно испортится текст?
Metotron0
17.01.2024 08:28У JPEG при сжатии можно выбрать качество. Если выбрать совсем мало, то испортится очень сильно.
foxyrus
Заранее прошу прощения у своего ДИБ ????
В свое время нужно было скачать JAR общедоступной библиотеки (мавен зависимость), но в локальном Nexus ее не было (нужно было ждать добавления), а все попытки (переименование, архивирование, с паролем) переслать jar через почту резались антивирусом. Тогда на помощь пришла утилита конвертации в PNG.
novoselov
Не нужна никакая утилита, пакуете файл в zip и вызываете
На выходе файл output.png который выглядит как исходная картинка, а при переименовании в output.zip "превращается" в архив с исходным файлом
foxyrus
Не фортануло: