Статья напичкана скучными непонятными формулами. Не обращайте внимание. Сам пока не разобрался.
Оглавление
На заре развития ПК, и в частности программного обеспечения, из-за дороговизны железа, для хранения большого количества информации умные люди придумали способы сжимать информацию без потерь. Так появились алгоритмы по сжатию информации, и собственно ПО реализующее эти алгоритмы - архиваторы.
Развитие сетей, в т.ч. интернета дало возможность этой самой информацией обмениваться. Интернет тоже вначале был не дешевым, поэтому сжатие информации (как при передаче файлов, так и при открытии сайта) пригодилось и тут.
Ну а как же кровавый интерпрайз, где потеря информации без права восстановления, грозила бизнесу большими убытками? Бекапы данных занимают много места. Спасибо алгоритмам архивации, они из здесь выручают.
Игровая индустрия гоняясь за длинным рублём выкатывает игрушки размером в сотни гигабайт. Но и эту проблему распухшего контента нам обещают скоро решить нейросжатием текстур…
Тема на первый взгляд не особо интересная: ничего нового нет, никакого развития, полная стагнация… Или, нет?
Давайте немного освежим знания. Тем более что в этой теме (к примеру у меня) познания остались где-то на уровне RLE.
>> Классические архиваторы
Любая информация: текст, фото, видео, аудио (и т.д. и т.п.) имеет избыточность, то есть повторяющиеся фрагменты, закономерности, паттерны. Это физически занимает драгоценное место: на диске, в ОЗУ, при передаче по сети (забивает канал передачи). Архиватор решает эту проблему, преобразуя повторяющиеся части в краткие записи - ссылки на уже встреченные точно такие же фрагменты. Но это не единственный алгоритм сжатия, есть и другие.
Классические архиваторы - это строгий алгоритм, как для сжатия, так и для распаковки. Давайте посмотрим примеры (мы не будем рассматривать алгоритмы сжатия с потерями, например JPEG).
Года напротив алгоритма - примерные даты начала применения, а не изобретения.
Определимся с исходной строкой для пояснения алгоритмов сжатия:
"в лесу родилась ёлочка, в лесу она росла".
Допустим, этот текст состоит из 8 битных символов в кодировке Windows-1251, (от "00000000" до "11111111" в двоичном представлении).
>> RLE (Run-Length Encoding), 1960-е года
Заменяет серию одинаковых символов. Исходную строку про ёлочку не сожмет. А вот такое "AAAAAABBBCC" сожмет до "A6B3C2". Т.е. заменяет подряд идущие одинаковые символы на пару "символ + количество".
Было: 11 символов.
Стало: 6 символов.
Отрицательное сжатие
Вариантов кодирования RLE несколько. Если рассмотреть строгое кодирование каждого символа количеством его повторений подряд, то выйдет отрицательное сжатие:
"в1 1л1е1с1у1 1р1о1д1и1л1а1с1ь1 1ё1л1о1ч1к1а1,1 1в1 1л1е1с1у1 1о1н1а1 1р1о1с1л1а1"
Было: 40 символов.
Стало: 80 символов.
>> Алгоритм Хаффмана (Частота), 1980-е года
Алгоритм считает частоту повторения символов, и составляет словарь: чем чаще встречается символ тем короче кодируется этот символ.
Фактически алгоритм строит бинарное дерево. Самые частые символы оказываются на вершине дерева (у них короткий путь), а редкие - на самых дальних ветках.
пробел встречается 7 раз: "в1лесу2родилась3ёлочка,4в5лесу6она7росла", поэтому записывается как "00" (2 бита).
буква "л" встречается 4 раза, записывается как "010" (3 бита)
и т.д.буква "о" встречается 4 раза, записывается как "011" (3 бита)
буква "а" встречается 4 раза, записывается как "100" (3 бита)
буква "с" встречается 3 раза, записывается как "101" (3 бита)
буква "е" встречается 2 раза, записывается как "1100" (4 бита)
Почему для пробела "00" (2 бита)? В 2 бита влезает четыре варианта: 00, 01, 10, 11. Если бы кроме пробела в тексте встречалась буква "л" тоже 7 раз, тогда она получила бы значение "01" и т.д.
Но почему сразу после "00" идет "010"? Потому что алгоритм работает без разделителей при распаковке: ни один код не должен быть началом (префиксом) другого кода. Если один символ закодирован "00", то мы не можем использовать "000", и "0000" и т.д. Префикс "00" уже занят. Но мы можем использовать для следующего символа "010", "011" и т.д., потому что они начинаются с префикса "01", а не с "00".
* / \ / \ / \ / \ / \ / \ 0 / \ 1 / \ * * / \ / \ 0 / \1 0 / \1 / \ / \ ПРОБЕЛ * * * 00 / \ / \ / \ 0/ \1 0/ \1 0/ \1 / \ / \ / \ Л О А С * 010 011 100 101 / \ 0/ \1 / \ Е ... 1100
Спускаемся по дереву сверху вниз:
До пробела: 0 > 0.
До буквы "л": 0 > 1 > 0
До буквы "о": 0 > 1 > 1
До буквы "а": 1 > 0 > 0
и тд.
Было: 40 символов (40 символов x 8 бит = 320 бит)
Стало: 152 бита (что соответствует 19 байтам ) …без учета словаря кодов. Не символа а бита. Ведь мы каждый символ закодировали битами разной длины.
>> Алгоритм Лемпеля и Зива - LZ77, 1985 год
Алгоритм бежит по строке, и если есть повтор - ставит метку где взять повтор и сколько символов. В исходном тексте видим совпадения: "[в лесу ]родилась ёлочка, [в лесу ]она росла". Результат:"в лесу родилась ёлочка, [24,7]она росла".
Где [24,7] - ссылка на предыдущие повторы: прыгни назад на 24 символа, скопируй 7 символов. Это буквально команда для распаковщика.
Было: 40 символов.
Стало 33 символа плюс ссылка на повторяющуюся последовательность.
>> DEFLATE, 1993 год
Сначала применяет LZ77 для поиска повторов, затем сжимает полученный поток двумя деревьями Хаффмана. Результат помещается в контейнер (ZIP, gzip, PNG), который добавляет метаданные и контрольные суммы.
Откройте форточку!
Остановимся на этих классических алгоритмах сжатия. Для вводной части этого, думаю достаточно.
>> Промежуточный вариант
Следующий этап развития статистических архиваторов: PAQ, и его продолжатель CMIX.
Основная идея PAQ - сжатие на основе вероятностных моделей данных: каждая модель пытается предсказать вероятность что следующий бит будет равен 1 для определенного типа данных (текст, exe, фото, видео и т.д.).
Модель данных - это алгоритм, оценивающий вероятность появления следующего бита.
Данные ↓ Несколько независимых моделей данных (текст, фото, видео, exe, jpeg и т.д.) ↓ Адаптивный смеситель (mixer) ↓ Коррекция вероятности (SSE) ↓ Арифметическое кодирование/декодирование
При архивации:
Архиватор считывает очередной бит из исходного файла
Все модели независимо оценивают вероятность того, что следующий бит будет равен 1
Адаптивный смеситель (mixer) объединяет прогнозы моделей в одну вероятность
Модуль коррекции вероятностей (SSE) уточняет полученную вероятность
Арифметический кодировщик, используя эту вероятность, записывает текущий бит в архив
Прочитанный бит передается всем моделям, которые обновляют свое состояние
Процесс повторяется для следующего бита
При распаковке:
Арифметический декодер запрашивает вероятность следующего бита
Все модели независимо оценивают вероятность того, что следующий бит будет равен 1
Адаптивный смеситель (mixer) объединяет прогнозы моделей в одну вероятность
Модуль коррекции вероятностей (SSE) уточняет полученную вероятность
Арифметический декодер, используя эту вероятность и данные архива, восстанавливает очередной бит
Восстановленный бит передается всем моделям, которые обновляют свое состояние
Процесс повторяется до полного восстановления файла
Объединение прогнозов (см. пункт 3 выше) всех моделей выполняет смеситель (mixer) - адаптивный линейный предсказатель который обучается в процессе сжатия информации. У него есть коэффициенты (веса), изменяющиеся после обработки каждого бита.
Математически он очень похож на один нейрон без скрытых слоев: 
где:
- прогнозы моделей;
- веса;
- сигмоида, математическая функция, преобразующая сумму взвешенных прогнозов моделей в вероятность от 0 до 1
Сигмоида выглядит так: 
Если преобразовать сигмоиду в формулу, смеситель будет выглядеть так: 
Модуль коррекции вероятностей SSE (Secondary Symbol Estimation) - это "доводчик" вероятности: он не вычисляет ее с нуля, а делает уже полученную оценку более точной на основе статистики предыдущих ошибок.
CMIX - дальнейшее развитие PAQ.
Если в PAQ множество моделей данных независимо оценивают вероятность следующего бита, а затем их прогнозы объединяются адаптивным смесителем.
То в CMIX (вместо адаптивного смесителя) используется более сложная система объединения прогнозов целым консилиумом из многослойных нейросетей, а коррекция вероятностей (SSE) превратилась в каскадную (многоступенчатую). Благодаря этому итоговая вероятность следующего бита получается точнее.
И всё это - очень упрощенное объяснение.
>> Нейроархиваторы
Классические архиваторы сжимают данные на основе локальных статистических закономерностей: частоты символов, повторяющиеся последовательности. Более современные алгоритмы (PAQ, CMIX) используют небольшие нейронные компоненты для объединения статистических моделей, однако сами модели данных остаются классическими.
А вот нейросетевые архиваторы, использующие полноценные языковые модели (Transformer, RNN и т.д.), строят вероятностную модель более высокого уровня, способную учитывать структуру языка, синтаксис, семантические закономерности и связи между словами.
Нейросетевой архиватор, с предобученной языковой моделью может опираться на знания, полученные при обучении, даже если конкретной фразы в файле еще не было. Например при сжатии, увидев фразу "в лесу родилась", модель с высокой вероятностью предскажет слово "ёлочка". Тогда как классический архиватор может использовать только закономерности, обнаруженные ранее в исходном файле.
Проще говоря: и те и другие работают со статистическими закономерностями, только нейросеть - это гораздо более богатая статистическая модель обученная на больших объемах данных. Благодаря этому она точнее предсказывает последовательность символов или токенов, что позволяет эффективнее сжимать данные.
>> NNCP Фабриса Беллара
А теперь "забудьте всё, чему вас учили раньше". NNCP (Neural Network Compression Program) - это другой подход к сжатию информации.
Да, его придумал тот самый Фабрис, французский программист, создавший FFmpeg и эмулятор QEMU.
Скрытый текст
Мы рассмотрим актуальную версию NNCP 3.3, использующую архитектуру Transformer. Первые версии NNCP были основаны на рекуррентной сети LSTM, однако начиная с версии 2 архиватор использует Transformer.
Во время архивации и распаковки NNCP создает нейронную сеть в ОЗУ. По мере обработки файла, нейронка обучается на уже прочитанных данных, все точнее предсказывая следующие байты (точнее токены) и помогает арифметическому кодировщику сжимать или восстанавливать файл. После завершения работы архиватора, нейронка исчезает без следа...
Данные ↓ Transformer (единая обучаемая модель) ↓ Арифметическое кодирование
Так как происходит реальное сжатие данных? Чем точнее модель предсказывает следующий токен, тем меньше бит потребуется арифметическому кодировщику для его записи. И наоборот: чем менее вероятным оказался следующий байт, тем больше бит придется потратить.
Вероятность следующего байта | Требуется бит |
|---|---|
0.99 | ≈ 0.01 бит |
0.90 | ≈ 0.15 бит |
0.50 | 1 бит |
0.25 | 2 бита |
0.01 | ≈ 6.64 бит |
Это классическая формула Шеннона для вычисления информационной энтропии:
, где:
- количество информации (или минимальное число бит, необходимое для кодирования события); 
- вероятность наступления этого события; 
- двоичный логарифм.
По такому же принципу работают PAQ и CMIX, но они предсказывают один бит за раз. А NNCP предсказывает токен из словаря токенов, который состоит из примерно 16000 штук. Первые 256 токенов (от 0 до 255) - прямо отражают все возможные значения байта. Остальные представляют собой часто встречающиеся последовательности байтов, сформированные алгоритмом BPE (Byte Pair Encoding): это могут быть части слов, целые слова, HTML-теги и другие повторяющиеся последовательности данных. Про BPE я уже писал здесь: https://habr.com/ru/articles/1017484/.
Однако у такого подхода есть несколько минусов:
Высокие требования к вычислительным ресурсам: обучение Transformer во время сжатия и распаковки требует большого объема оперативной памяти и значительной вычислительной мощности
Низкая скорость архивации: на обучение нейросети уходит значительно больше времени, чем на работу классических архиваторов, поэтому создание архива может занимать не то что бы минуты, но даже часы, дни, недели...
Высокая степень сжатия проявляется только на больших объемах данных. Нейронке требуется время, чтобы изучить закономерности конкретного файла, поэтому на небольших файлах ее преимущества практически незаметны. Наиболее эффективно NNCP работает с файлами объемом в сотни мегабайт и более.
А не проще было бы упростить нейросеть, и сохранять весА вместо закодированных вероятностей байт? Сделаем так что бы модель "зазубрила" данные, реализуем меморизацию данных! Ведь нам надо восстановить исходный файл без потерь.
Нет. Согласно Принципу Дирихле, для точного запоминания произвольных данных информационная емкость весов должна быть равна или даже больше чем в исходном файле. Добавим сюда накладные расходы на сохранение структуры модели (описание архитектуры, размеры тензоров, типы данных, метаданные и т.д.), и это уже - архиватор с отрицательной эффективностью.
Иоганн Петер Густав Лежён Дирихле, 1805–1859, математик XIX века. Его принцип звучит так: "Если
кроликов посадить в
клеток, то хотя бы в одной клетке будет сидеть минимум два кролика". В контексте сжатия информации через нейронку, веса (клетки) не могут быть меньше запоминаемой информации (кролики).
Не смотря на то что датасет (благодаря которому нейронка обучается), физически кратно превышает веса модели, размер датасета не означает его точную информационную ёмкость. 100 Терабайт текста - это не 100 Тб информации.
Например представьте датасет в котором миллион раз подряд написано слово "Кот".
Физический размер: несколько мегабайт.
Информационная емкость (энтропия): несколько байт (команда: «Вывести слово "Кот" 1 000 000 раз»).
Нейронка не создает в весах "сжатую копию" датасета (как это делает ZIP-архиватор). Она ищет скрытые паттерны, правила и закономерности, которые порождают этот датасет.
Весь выигрыш в размере архива и состоит в том, что NNCP сохраняет не обученные веса модели, а историю её ошибок при обучении. Чем лучше модель изучила закономерности данных, тем меньше информации приходится записывать в архив.
>> Архивируем ...инференсом
Давайте договоримся, что мы будем сжимать текст: "Мама мыла раму", а наша нейронка обучена русскому языку.
Для архивации / распаковки текста, нам нужен движок позволяющий загрузить модель локально. Модели доступные через API (по сети) нам не подходят. Почему? Проблема в том, что в процессе инференса от модели нам нужно получить логиты (числовые оценки предсказания токенов). А модель через API выдает уже готовый текст.
Поэтому будем использовать пакет LlamaSharp.
Мы знаем, что большие языковые модели работают не с текстом, а с токенами. Когда мы отправляем нейронке текст, токенизатор преобразует его в набор токенов, прежде чем модель начнет их обрабатывать. Токеном может быть как часть слова, так и само слово, и даже несколько слов.
В процессе инференса, модель вычисляет для каждого токена словаря числовую оценку - логит. Чем больше словарь токенов у модели - тем больше ресурсов требуется для этого действия. Словарь на 100 тысяч токенов? Значит при инференсе на предсказание каждого следующего токена модель дает 100 тысяч логитов. Затем эти логиты преобразуются в вероятности токенов посредством Softmax (функция превращающая числовые оценки в вероятности).
Как температура меняет инференс
Что интересно, температура - как раз и является рычагом внутри Softmax, который влияет на выбор токена из логитов:
где:
- логит 
-го токена
- температура
- вероятность этого токена после Softmax
Как это работает при изменении температуры:
- выбор токена с максимальным логитом
- распределение становится более "острым": наиболее вероятные токены получают еще большую вероятность, а менее вероятные - еще меньшую
— обычный Softmax: вероятности остаются такими, как их оценила модель
Но в данном случае температура не интересует. Мы не будем применять Softmax для выдачи готовых токенов.
По логитам можно определить ранг каждого токена - его место после сортировки по убыванию логитов. Ранг - это целое число от 0 до размера словаря. Чем лучше модель угадала токен, тем меньше ранг, и тем меньше бит требуется для его записи в архив, и тем меньше сам архив.
Пример "Мама мыла раму":
Ранг 0 (слово, или лучше токен "Мама") = модель угадала идеально, кодируется 1 бит
Ранг 10 ("мыла") = модель была близко, кодируется 7 бит
Ранг 1000 (внезапно "раму") = модель не угадала, кодируется 19 бит
Фраза хорошо подходит для демонстрации того как нейронка, обученная на русском тексте, предлагает для каждого последующего слова (токена) - вероятность появления всё ниже и ниже. На самом деле: какое слово вы ожидаете увидеть после "Мама"? А после "мыла"? Ну вот какая еще "раму" может быть после слова "мыла"?
Конечно, если бы нейронка была обучена на таком предложении из рекламы 2010х - то все токены получили бы высокие вероятности и ранги меньше 10.
Зачем нам нужен ранг, и почему именно 1, 7, 19 битов на этом примере? Ранг - это целое неотрицательное число, которое удобно закодировать в биты через алгоритм Голомба.
Алгоритм Голомба был предложен Соломоном Голомбом в 1966 году и широко используется в компрессии (например, именно его вариация Exponential-Golomb используется в видеокодеках H.264/H.265 для сжатия векторов движения и коэффициентов)
Алгоритм принимает на вход целое число(наш ранг) и настраиваемый параметр
(обычно степень двойки).
Как работает алгоритм:
Число
(в нашем случае - ранг) разбивается на две части с помощью деления:Частное (Quotient):
(целочисленное деление)Остаток (Remainder):
Кодирование частного Q (Унарный код)
Унарный код — это самый примитивный способ записи чисел: число записывается как последовательность единиц, заканчивающаяся нулем.
(1 бит)
(2 бита)
(3 бита)
(6 бит)
Чем больше
, тем длиннее цепочка единиц.Кодирование остатка R (Бинарный код)
Остаток
всегда находится в диапазоне от 
до 
. Он записывается как обычное двоичное число фиксированной длины 
бит. Символ 
означает округление вверх до ближайшего целого числа. В математике эта функция называется "потолок" (от английского ceiling).Если
(3 бита на остаток):Итоговый код: просто склеиваем код
и код
Параметр - это ожидаемое среднее значение рангов.
Если модель для сжатия очень хорошая (хорошо сжимает именно эти данные, например обучена на русском языке и надо сжать русский текст), средние ранги будут маленькими (например, 5-20). Тогда
нужно брать маленьким (например, 4, 8, 16).Если модель путается и средние ранги большие (например, 200), то
нужно увеличивать (например, 128, 256), иначе унарный код для раздуется до неприличия.
Параметр можно сделать адаптивным: при кодировании вычислять среднее последних 100 рангов, и динамически подстраивать под текущую "сложность" текста. Это может дать еще 10-15% к степени сжатия.
>> Сохраняем бит
Ок, инференс > логиты > ранги. Дальше то что? В чем собственно магия сжатия? Что там насчет алгоритма Голомба? Как ранг превращается в бит? И как потом эту кашу из сохраненных битов прочитать, что бы восстановить исходный файл? Границ между битами среди этой мешанины бит на первый взгляд нет.
Для преобразования рангов в готовые для сохранения биты, мы будем использовать адаптивный Exponential-Golomb, без параметра .
Общий алгоритм кодирования ранга:
Вычисляем число:
Находим старшую степень двойки в
. Если 
, то число занимает 
бит. 
в данном случае это порядок степени двойки которое которая помещается в наше число. 
(логарифм по основанию 2, округленный вниз до целого числа).Ставим
нулей в начало.Дописывам само число
в двоичном виде.
Допустим при инференсе трех слов, модель выдала логиты, которые были преобразованы в следующие ранги: 0, 10, 1000.
Ранг 0
Формируем код:
Префикс:
нулей → (пусто),Полезные данные: число
в двоичном виде → 1
Итого:
1(длина 1 бит)
Ранг 10
Формируем код:
Префикс:
нулей → 000,Полезные данные: число
в двоичном виде → 1011
Итого:
0001011(длина 7 бит)
Ранг 1000
Формируем код:
Префикс:
нулей → 000000000,Полезные данные: число
в двоичном виде → 1111101001
Итого:
0000000001111101001(длина 19 бит)
Вот он, результат: 1 0001011 0000000001111101001. Каша из единиц и нулей.
Было: "Мама мыла раму", каждый символ - 8 бит (в кодировке Windows-1251), т.е. 14 * 8 = 112 бит, ну или 14 байт.
Стало: 1 + 7 + 19 = 27 бит, ну или 27 / 8 
3 байта.
Степень сжатия: 112 / 27 = 4,148 раза без потерь.
>> Читаем бит
Это сейчас мы знаем что здесь закодировано три ранга (то есть логита, то есть токена, то есть слова). А как это прочитать правильно, различая эти ранги?
Общий алгоритм чтения ранга:
Считаем нули, пока не встретим первую единицу. Количество нулей =
.Читаем еще
бит (включая ту самую единицу). Это и есть закодированное число.Вычитаем единицу. Получаем ранг.
Ранг 1
Читаем биты: 1 00010110000000001111101001
Смотрим на первый бит потока: 100010110000000001111101001
Это единица. Значит, нулей перед ней было 0 (
).По правилу, читаем еще
бит (включая эту единицу).Считанный бинарный код:
1(это число 1 в десятеричной системе счисления).Вычитаем единицу:
. Мы получили Ранг 0.Указатель сдвинулся на 1 бит вправо. Остаток потока:
00010110000000001111101001
Ранг 2
Читаем биты: 000 1011 0000000001111101001
Смотрим на следующие биты:
0,0,0. (Три нуля).Смотрим на четвертый бит:
1. Единица.Нулей было 3 (
).По правилу, читаем еще
бита (включая эту единицу).Считанные 4 бита:
1011(это число 11 в десятеричной системе счисления).Вычитаем единицу:
. Мы получили Ранг 10.Указатель сдвинулся еще на 7 бит. Остаток потока:
0000000001111101001
Ранг 3
Читаем биты: 000000000 1111101001
Смотрим на следующие биты:
0,0,0,0,0,0,0,0,0. (Девять нулей).Смотрим на десятый бит:
1. Единица.Нулей было 9 (
).По правилу, читаем еще
бит.Считанные 10 бит:
1111101001(это число 1001 в десятеричной системе счисления).Вычитаем единицу:
. Мы получили Ранг 1000.Остаток потока: пуст. Конец файла.
>> Восстанавливаем текст
Тут я немного пропустил тот факт, что для начала инференса, модель в качестве первого токена должна получить специальный токен BOS (beginning of Sentence), и только потом те, что нужно сжать. Поэтому первый токен BOS так же должен быть сохранен в архив, для чтения при распаковке архива.
Итак. Нам нужно получить токен, при этом мы загрузили из файла ранг = . Отправляем, значит токен в модель. Получаем логиты. Сортируем ID токенов по убыванию их логитов. Берем элемент отсортированного массива на позиции равной рангу - это и будет ID нужного токена.
Инференс токена BOS. Ранг = 0.
Получаем логиты:
ID токена | Логит | Токен ----------|-------|-------- ... | ... | ... 5000 | 15.3 | "мама" 5001 | 12.1 | "папа" 5002 | 8.7 | "кот" ... | ... | ...Сортируем ID токенов по убыванию их логитов.
Позиция | ID токена | Логит | Токен --------|-----------|-------|-------- 0 | 5000 | 15.3 | "мама" ← БЕРЕМ ЭТОТ (ранг 0) 1 | 5001 | 12.1 | "папа" 2 | 5002 | 8.7 | "кот" ... | ... | ... | ...Инференс токена BOS + "мама". Ранг = 10.
Получаем логиты:
ID токена | Логит | Токен ----------|-------|-------- ... | ... | ... 5100 | 14.5 | "стирала" 5200 | 12.2 | "мыла" 5300 | 11.3 | "танцевала" ... | ... | ...Сортируем ID токенов по убыванию их логитов.
Позиция | ID токена | Логит | Токен ---------|-----------|-------|-------- 1 | 5100 | 14.5 | "стирала" ... | ... | ... | ... 10 | 5200 | 12.2 | "мыла" ← БЕРЕМ (ранг 10) ... | ... | ... | ... 33 | 5300 | 11.3 | "танцевала" ... | ... | ... | ...Инференс токена BOS + "мама" + "мыла". Ранг = 1000.
Получаем логиты:
ID токена | Логит | Токен ----------|-------|-------- ... | ... | ... 7300 | 16.7 | "раму" 7400 | 14.5 | "шпалы" 7500 | 17.1 | "голову" ... | ... | ...Сортируем ID токенов по убыванию их логитов.
Позиция | ID токена | Логит | Токен ----------|-----------|-------|-------- ... | ... | ... | ... 999 | 7500 | 17.1 | "голову" 1000 | 7300 | 16.7 | "раму" ← БЕРЕМ (ранг 1000) 1100 | 7400 | 14.5 | "шпалы" ... | ... | ... | ...
Конечно при каждом инференсе мы не передаем все предыдущие токены. Предыдущие токены хранятся в KV-кэше (Key-Value cache) внимания, т.е. остаются там как контекст.
В итоге, весь исходный текст восстановлен без потерь.
>> Итого
Весь код поместился в один файл. Необходимо добавить два пакета: LLamaSharp и LLamaSharp.Backend.Vulkan.Windows.
Program.cs
//https://github.com/virex-84 #pragma warning disable CS0618 using LLama; using LLama.Common; using LLama.Native; using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; class Program { static string? ModelPath; static string? FilenameIn; static string? FilenameOut; static string? CompressFile; static uint ContextSize = 128; static uint MaxContextTokens = ContextSize - 2; static void Main(string[] args) { // Включаем поддержку UTF-8 в консоли, чтобы русский текст не превратился в "кракозябры" Console.OutputEncoding = Encoding.UTF8; Console.InputEncoding = Encoding.UTF8; // Перехватываем логирование NativeLogConfig.llama_log_set((level, message) => { }); if (args.Length == 0) { PrintHelp(); return; } string? mode = null; bool outputSpecified = false; for (int i = 0; i < args.Length; i++) { switch (args[i].ToLower()) { case "-h": case "/?": PrintHelp(); return; case "-c": mode = "compress"; break; case "-d": mode = "decompress"; break; case "-i": RunInteractive(); return; case "-m": if (i + 1 < args.Length) ModelPath = args[++i]; break; case "-f": if (i + 1 < args.Length) FilenameIn = args[++i]; break; case "-o": if (i + 1 < args.Length) { FilenameOut = args[++i]; outputSpecified = true; } break; case "-a": if (i + 1 < args.Length) CompressFile = args[++i]; break; } } if (mode == null) { Console.WriteLine("Ошибка: не указан режим. Используйте -c, -d, -i или -h для справки."); return; } if (string.IsNullOrEmpty(ModelPath) || string.IsNullOrEmpty(FilenameIn)) { Console.WriteLine("Ошибка: в режимах -c и -d обязательны параметры -m (модель) и -f (файл)."); return; } if (!File.Exists(ModelPath)) { Console.WriteLine($"Ошибка: модель не найдена: {ModelPath}"); return; } if (!File.Exists(FilenameIn)) { Console.WriteLine($"Ошибка: файл не найден: {FilenameIn}"); return; } Console.WriteLine("╔═════════════════╗"); Console.WriteLine("║ NeuroArchInfer ║"); Console.WriteLine("╚═════════════════╝"); if (mode == "compress") { if (CompressFile == null) CompressFile = FilenameIn! + ".nai"; Console.WriteLine($"Модель: {ModelPath}"); Console.WriteLine($"Файл: {FilenameIn}"); Console.WriteLine($"Архив: {CompressFile}"); Compress(FilenameIn!, CompressFile); } else { if (CompressFile == null) CompressFile = FilenameIn; if (!outputSpecified) { string baseName = Path.GetFileNameWithoutExtension(CompressFile); string ext = Path.GetExtension(CompressFile); FilenameOut = baseName + ext; FilenameOut = GetUniqueFilename(FilenameOut!); } Console.WriteLine($"Модель: {ModelPath}"); Console.WriteLine($"Архив: {CompressFile}"); Console.WriteLine($"Восстановление: {FilenameOut}"); Decompress(CompressFile, FilenameOut!); } } static void RunInteractive() { Console.WriteLine("╔═════════════════╗"); Console.WriteLine("║ NeuroArchInfer ║"); Console.WriteLine("╚═════════════════╝"); Console.Write("Путь к модели: "); string? modelInput = Console.ReadLine()?.Trim(); if (!string.IsNullOrEmpty(modelInput)) ModelPath = modelInput; if (string.IsNullOrEmpty(ModelPath)) { Console.WriteLine("Ошибка: путь к модели не указан."); return; } Console.WriteLine(" 1. Сжатие"); Console.WriteLine(" 2. Восстановление"); Console.Write("Выберите режим [1/2]: "); string mode = Console.ReadLine()?.Trim() ?? "1"; if (mode == "1") { Console.Write("Исходный файл: "); FilenameIn = Console.ReadLine()?.Trim(); if (string.IsNullOrEmpty(FilenameIn)) { Console.WriteLine("Ошибка: имя файла не указано."); return; } string defaultArchive = FilenameIn + ".nai"; Console.Write($"Имя архива (Enter = {defaultArchive}): "); string? archiveInput = Console.ReadLine()?.Trim(); CompressFile = string.IsNullOrEmpty(archiveInput) ? defaultArchive : archiveInput; Compress(FilenameIn, CompressFile); } else { Console.Write("Архив для восстановления: "); FilenameIn = Console.ReadLine()?.Trim(); if (string.IsNullOrEmpty(FilenameIn)) { Console.WriteLine("Ошибка: имя файла не указано."); return; } CompressFile = FilenameIn; string defaultOutput = Path.GetFileNameWithoutExtension(FilenameIn); string defaultOutputChecked = GetUniqueFilename(defaultOutput); Console.Write($"Восстановленный файл (Enter = {defaultOutputChecked}): "); string? outputInput = Console.ReadLine()?.Trim(); FilenameOut = string.IsNullOrEmpty(outputInput) ? defaultOutputChecked : outputInput; Decompress(CompressFile, FilenameOut); } } static string GetUniqueFilename(string path) { if (!File.Exists(path)) return path; string dir = Path.GetDirectoryName(path) ?? ""; string baseName = Path.GetFileNameWithoutExtension(path); string ext = Path.GetExtension(path); for (int n = 1; ; n++) { string candidate = Path.Combine(dir, baseName + n + ext); if (!File.Exists(candidate)) return candidate; } } static void PrintModel(LLamaWeights weights) { var m = weights.Metadata; string arch = m.TryGetValue("general.architecture", out var a) ? a : "?"; string archPrefix = arch + "."; string name = m.TryGetValue("general.name", out var n) ? n : "?"; string sizeLabel = m.TryGetValue("general.size_label", out var s) ? s : "?"; string tokModel = m.TryGetValue("tokenizer.ggml.model", out var t) ? t : "?"; string tokPre = m.TryGetValue("tokenizer.ggml.pre", out var p) ? p : "?"; string vocabSize = m.TryGetValue(archPrefix + "vocab_size", out var v) ? v : "?"; Console.WriteLine(); Console.WriteLine( "┌─ Модель ────────────────────────────────"); Console.WriteLine($"│ {"Имя",-20} {name}"); Console.WriteLine($"│ {"Архитектура",-20} {arch}"); Console.WriteLine($"│ {"Размер",-20} {sizeLabel}"); Console.WriteLine($"│ {"Словарь (vocab)",-20} {vocabSize}"); Console.WriteLine($"│ {"Токенизатор",-20} {tokModel}"); Console.WriteLine($"│ {"Пре-токенизатор",-20} {tokPre}"); Console.WriteLine( "└──────────────────────────────────────────"); } static void PrintHelp() { Console.WriteLine("╔══════════════════════════════════════════╗"); Console.WriteLine("║ NeuroArchInfer - нейросетевой архиватор ║"); Console.WriteLine("╚══════════════════════════════════════════╝"); Console.WriteLine(); Console.WriteLine("Использование:"); Console.WriteLine(" Сжатие: NeuroArchInfer -c -m <модель> -f <файл> [-a <архив>]"); Console.WriteLine(" Декомпрессия: NeuroArchInfer -d -m <модель> -f <архив> [-o <восстановленный>]"); Console.WriteLine(" Интерактив: NeuroArchInfer -i"); Console.WriteLine(" Справка: NeuroArchInfer -h"); Console.WriteLine(); Console.WriteLine("Параметры:"); Console.WriteLine(" -m <путь> Путь к GGUF-модели"); Console.WriteLine(" -f <имя> Сжатие: исходный файл; Декомпрессия: архив (.nai)"); Console.WriteLine(" -o <имя> Восстановленный файл (по умолчанию: имя архива без .nai)"); Console.WriteLine(" -a <имя> Имя архива при сжатии (по умолчанию: <файл>.nai)"); Console.WriteLine(); Console.WriteLine("Режимы:"); Console.WriteLine(" -c Сжатие"); Console.WriteLine(" -d Декомпрессия"); Console.WriteLine(" -i Интерактивный режим"); Console.WriteLine(" -h, /? Подсказка"); Console.WriteLine(); Console.WriteLine("Примеры:"); Console.WriteLine(" Сжатие: NeuroArchInfer -c -m model.gguf -f document.txt"); Console.WriteLine(" NeuroArchInfer -c -m model.gguf -f document.txt -a my.nai"); Console.WriteLine(" Декомпрессия: NeuroArchInfer -d -m model.gguf -f document.txt.nai"); Console.WriteLine(" NeuroArchInfer -d -m model.gguf -f document.txt.nai -o out.txt"); } static int GetLogits(LLamaContext context, ref LLamaBatch batch, int token, int pos, float[] buffer) { batch.Clear(); int idx = batch.Add(token, (LLamaPos)pos, LLamaSeqId.Zero, logits: true); context.Decode(batch); var span = context.NativeHandle.GetLogitsIth(idx); span.CopyTo(buffer); return span.Length; } static int FindRank(float[] logits, int targetIndex, int length) { float targetValue = logits[targetIndex]; int rank = 0; for (int j = 0; j < length; j++) { if (logits[j] > targetValue || (logits[j] == targetValue && j < targetIndex)) rank++; } return rank; } static int FindTokenByRank(float[] logits, int[] indices, int targetRank) { int n = logits.Length; int left = 0, right = n - 1; while (left < right) { float pivotValue = logits[indices[right]]; int pivotIndex = indices[right]; int i = left; for (int j = left; j < right; j++) { float vj = logits[indices[j]]; if (vj > pivotValue || (vj == pivotValue && indices[j] < pivotIndex)) { (indices[i], indices[j]) = (indices[j], indices[i]); i++; } } (indices[i], indices[right]) = (indices[right], indices[i]); if (i == targetRank) return indices[i]; else if (i < targetRank) left = i + 1; else right = i - 1; } return indices[left]; } static void Compress(string inputFile, string outputFile) { Console.WriteLine("\n[1/4] Инициализация локального ИИ..."); // cоздаем минимальные параметры только для чтения метаданных var metaParams = new ModelParams(ModelPath!) { ContextSize = 1, BatchSize = 1, GpuLayerCount = -1 }; // загружаем веса (на этом этапе метаданные уже доступны) var weights = LLamaWeights.LoadFromFile(metaParams); PrintModel(weights); // динамически определяем ContextSize из прочитанных метаданных var contextKey = weights.Metadata.Keys .FirstOrDefault(k => k.EndsWith(".context_length", StringComparison.OrdinalIgnoreCase)); if (contextKey != null && weights.Metadata.TryGetValue(contextKey, out string ctxValue) && int.TryParse(ctxValue, out int maxContext)) { ContextSize = (uint)maxContext; MaxContextTokens = ContextSize - 2; } uint optimalBatchSize = Math.Min(512, ContextSize); // создаем финальные параметры контекста на основе полученных данных var contextParams = new ModelParams(ModelPath!) { ContextSize = ContextSize, BatchSize = optimalBatchSize, GpuLayerCount = -1 }; // инициализируем контекст с новыми, правильными параметрами var context = weights.CreateContext(contextParams); Console.WriteLine("[2/4] Чтение и токенизация исходного файла..."); string originalText = File.ReadAllText(inputFile); LLamaToken[] originalTokens = context.Tokenize(originalText, addBos: true, special: false); int[] tokenValues = originalTokens.Select(t => (int)t).ToArray(); Console.WriteLine($"Токенов: {tokenValues.Length}. Инференс..."); // определяем vocabSize через первый прогон var batch = new LLamaBatch(); batch.Add(tokenValues[0], (LLamaPos)0, LLamaSeqId.Zero, logits: true); context.Decode(batch); var probe = context.NativeHandle.GetLogitsIth(0); int vocabSize = probe.Length; float[] logitsBuffer = new float[vocabSize]; probe.CopyTo(logitsBuffer); List<int> ranks = new List<int>(tokenValues.Length - 1); int kvUsed = 1; ranks.Add(FindRank(logitsBuffer, tokenValues[1], vocabSize)); for (int i = 1; i < tokenValues.Length - 1; i++) { if (kvUsed >= ContextSize - 1) { int windowSize = Math.Min(i, (int)MaxContextTokens / 2); int start = i - windowSize; Console.Write($"\n[Окно] Очистка KV-кэша (позиция {i})... "); context.NativeHandle.MemoryClear(true); batch.Clear(); for (int j = 0; j < windowSize; j++) batch.Add(tokenValues[start + j], (LLamaPos)j, LLamaSeqId.Zero, logits: false); context.Decode(batch); kvUsed = windowSize; Console.WriteLine($"окно [{start}..{i - 1}], KV={kvUsed}"); } GetLogits(context, ref batch, tokenValues[i], kvUsed, logitsBuffer); kvUsed++; int rank = FindRank(logitsBuffer, tokenValues[i + 1], vocabSize); ranks.Add(rank); if (i % 100 == 0 || i == tokenValues.Length - 2) Console.Write($"\rПрогресс ИИ: {i + 1}/{tokenValues.Length - 1} (ранг: {rank}) "); } Console.WriteLine("\n[3/4] Битовое сжатие рангов алгоритмом Голомба..."); byte[] compressedPayload = RankCompressor.Compress(ranks); Console.WriteLine("[4/4] Запись архивного файла (.nai) на диск..."); using (var fs = new FileStream(outputFile, FileMode.Create, FileAccess.Write)) using (var writer = new BinaryWriter(fs)) { writer.Write(tokenValues.Length); writer.Write(tokenValues[0]); writer.Write(compressedPayload.Length); writer.Write(compressedPayload); } context.Dispose(); weights.Dispose(); Console.WriteLine($"Сжато! Исходный: {new FileInfo(inputFile).Length} байт. Архив: {new FileInfo(outputFile).Length} байт."); } static void Decompress(string inputFile, string outputFile) { Console.WriteLine("\n[1/4] Инициализация ИИ на приемной стороне..."); // cоздаем минимальные параметры только для чтения метаданных var metaParams = new ModelParams(ModelPath!) { ContextSize = 1, BatchSize = 1, GpuLayerCount = -1 }; // загружаем веса (на этом этапе метаданные уже доступны) var weights = LLamaWeights.LoadFromFile(metaParams); PrintModel(weights); // динамически определяем ContextSize из прочитанных метаданных var contextKey = weights.Metadata.Keys .FirstOrDefault(k => k.EndsWith(".context_length", StringComparison.OrdinalIgnoreCase)); if (contextKey != null && weights.Metadata.TryGetValue(contextKey, out string ctxValue) && int.TryParse(ctxValue, out int maxContext)) { ContextSize = (uint)maxContext; MaxContextTokens = ContextSize - 2; } uint optimalBatchSize = Math.Min(512, ContextSize); // создаем финальные параметры контекста на основе полученных данных var contextParams = new ModelParams(ModelPath!) { ContextSize = ContextSize, BatchSize = optimalBatchSize, GpuLayerCount = -1 }; // инициализируем контекст с новыми, правильными параметрами var context = weights.CreateContext(contextParams); Console.WriteLine("[2/4] Чтение заголовков архива..."); int totalTokensCount, firstToken; byte[] compressedPayload; using (var fs = new FileStream(inputFile, FileMode.Open, FileAccess.Read)) using (var reader = new BinaryReader(fs)) { totalTokensCount = reader.ReadInt32(); firstToken = reader.ReadInt32(); int payloadLength = reader.ReadInt32(); compressedPayload = reader.ReadBytes(payloadLength); } Console.WriteLine("[3/4] Битовое разжатие Голомба в ранги..."); List<int> ranks = RankCompressor.Decompress(compressedPayload, totalTokensCount - 1); Console.WriteLine($"Ранги: {ranks.Count} шт. Обратный инференс ИИ..."); int[] restoredTokenValues = new int[ranks.Count + 1]; restoredTokenValues[0] = firstToken; var batch = new LLamaBatch(); // определяем vocabSize через первый прогон batch.Add(firstToken, (LLamaPos)0, LLamaSeqId.Zero, logits: true); context.Decode(batch); var probe = context.NativeHandle.GetLogitsIth(0); int vocabSize = probe.Length; float[] logitsBuffer = new float[vocabSize]; probe.CopyTo(logitsBuffer); int kvUsed = 1; int[] sortBuffer = new int[vocabSize]; for (int j = 0; j < vocabSize; j++) sortBuffer[j] = j; for (int i = 0; i < ranks.Count; i++) { int targetRank = ranks[i]; for (int j = 0; j < vocabSize; j++) sortBuffer[j] = j; int restoredNextToken = FindTokenByRank(logitsBuffer, sortBuffer, targetRank); restoredTokenValues[i + 1] = restoredNextToken; if (kvUsed >= ContextSize - 1) { int targetPos = i + 1; int windowSize = Math.Min(targetPos, (int)MaxContextTokens / 2); int start = targetPos - windowSize; Console.Write($"\n[Окно] Очистка KV-кэша (позиция {targetPos})... "); context.NativeHandle.MemoryClear(true); batch.Clear(); for (int j = 0; j < windowSize; j++) batch.Add(restoredTokenValues[start + j], (LLamaPos)j, LLamaSeqId.Zero, logits: false); context.Decode(batch); kvUsed = windowSize; Console.WriteLine($"окно [{start}..{targetPos - 1}], KV={kvUsed}"); } GetLogits(context, ref batch, restoredNextToken, kvUsed, logitsBuffer); kvUsed++; if (i % 100 == 0 || i == ranks.Count - 1) Console.Write($"\rПрогресс восстановления ИИ: {i + 1}/{ranks.Count}"); } Console.WriteLine("\n[4/4] Детокенизация и сохранение файла..."); List<LLamaToken> tokenList = restoredTokenValues.Select(v => (LLamaToken)v).ToList(); string restoredText = context.DeTokenize(tokenList); File.WriteAllText(outputFile, restoredText); context.Dispose(); weights.Dispose(); Console.WriteLine($"Файл восстановлен: {outputFile}"); } public static class RankCompressor { public static byte[] Compress(List<int> ranks) { List<bool> bitBuffer = new List<bool>(); foreach (int rank in ranks) { if (rank < 0) throw new ArgumentException("Ранг не может быть отрицательным."); int val = rank + 1; int sigBits = 0; while ((val >> sigBits) > 1) { sigBits++; } for (int i = 0; i < sigBits; i++) bitBuffer.Add(false); for (int i = sigBits; i >= 0; i--) bitBuffer.Add(((val >> i) & 1) == 1); } return PackBitsToBytes(bitBuffer); } public static List<int> Decompress(byte[] compressedBytes, int totalCount) { List<bool> bits = UnpackBytesToBits(compressedBytes); List<int> ranks = new List<int>(); int bitIndex = 0; while (ranks.Count < totalCount && bitIndex < bits.Count) { int zeroCount = 0; while (bitIndex < bits.Count && !bits[bitIndex]) { zeroCount++; bitIndex++; } if (bitIndex >= bits.Count) break; int val = 0; for (int i = 0; i <= zeroCount; i++) { if (bitIndex >= bits.Count) break; val = (val << 1) | (bits[bitIndex] ? 1 : 0); bitIndex++; } ranks.Add(val - 1); } return ranks; } private static byte[] PackBitsToBytes(List<bool> bits) { int byteCount = (bits.Count + 7) / 8; byte[] bytes = new byte[byteCount]; for (int i = 0; i < bits.Count; i++) { if (bits[i]) bytes[i / 8] |= (byte)(1 << (7 - (i % 8))); } return bytes; } private static List<bool> UnpackBytesToBits(byte[] bytes) { List<bool> bits = new List<bool>(bytes.Length * 8); foreach (byte b in bytes) { for (int i = 7; i >= 0; i--) bits.Add(((b >> i) & 1) == 1); } return bits; } } }
Можно запускать программу с флагами, в том числе и в интерактивном режиме.
В интерактивном режиме
Достаточно скачать любую GGUF модель с Hugging Face, запустить программу и выбрать 1. Сжатие, или 2. Восстановление.
Но самое главное: создание архива и распаковка должна производится точно такой же моделью, с точно такой же квантизацией, иначе ...кина не будет ничего не получится. У разных моделей - разные словари токенов. Различия в квантизации влияют на значения логитов. Даже версия компонента LlamaSharp может влиять на детерминированность .
Исходный код: https://github.com/virex-84/NeuroArchInfer
>> Послесловие
Изначально, тема нейроархиватора была подсмотрена здесь: https://habr.com/ru/companies/ruvds/articles/1040026/.
Конечно же, первым делом после этой статьи я полез делать аналог NNCP с обучением через OpenCL (с помощью встройки AMD), но с условием, что я буду сохранять веса модели. И что-то даже получилось. Но это сложная тема.
самодельный аналог NNCP
И только после того как начал писать эту статью, немного начал понимать в чем собственно магия сжатия. Так появилась идея, что можно сжать данные через инференс любой локальной модели.
В качестве локальной модели пробовал взять самодельную микро модель GGUF размером 442 КБ из предыдущей статьи https://habr.com/ru/articles/1017484/. Если в исходном файле для сжатия будет текст на котором обучалась микро-модель - будет сжатие.
Скрытый текст
Надеюсь статья вам понравится. Честно, старался.
А на сегодня всё...
