Может ли gzip быть языковой моделью?

Сжатие — это предсказание

Подумаем о том, что делает компрессор. Он тратит мало байт на данные, которые он "ожидает", и много байт на данные, которые не ожидает. Если дать файл с буквой A, повторённой миллион раз, его можно описать одним предложением. А миллион случайных байт не имеют структуры, которую можно использовать, и практически не сжимаются.

Это не совпадение; это суть теории информации. Количество битов, необходимых для кодирования символа, равно $-\log_2 p$, где $p$ — вероятность, которую модель ему присваивает. Высокая вероятность означает мало битов. Таким образом, любой компрессор имеет спрятанную внутри вероятностную модель, независимо от того, записал ли кто-нибудь её явно.

gzip использует DEFLATE, который сжимает следующие байты, найдя совпадения с недавним текстом в скользящем окне размером 32 KiB. Если продолжение повторяет что-то уже находящееся в окне, DEFLATE кодирует это как дешёвую обратную ссылку вместо буквальных байт. Таким образом:

Продолжение, которое gzip "ожидал", потому что оно повторяет текст, уже находящийся в его окне, сжимается в практически ничего.

Это даёт нам оценку. Если есть некоторый контекст и нужно понять, насколько хорош кандидат на продолжение, достаточно измерить:

$$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$

Чем меньше длина сжатого текста, тем больше кандидат "предсказан". Чтобы инициализировать модель, корпус включается в окно gzip. Любое продолжение, похожее на корпус, сжимается небольшим размером, а любое продолжение, которое не похоже, сжимается большим размером.

Генерация поиском по лучу

Оценка — одно; генерация — другое. Наивный подход выбора единственного следующего байта, который сжимается лучше всего, работает плохо и по тонкой причине: gzip выдаёт только целую длину байта (без дробей). Добавление одного байта часто вообще не меняет длину сжатого текста, поэтому много кандидатов завязывают и сигнал теряется в шуме квантования.

Решение — заглянуть вперёд на целый промежуток, прежде чем фиксировать выбор. gzipt выполняет поиск по лучу по последовательностям байт. На каждом шаге текущий контекст:

окно корпуса + недавний хвост (подсказки + сгенерированные байты)

Затем gzipt пробует возможные следующие байты. Каждый кандидат на продолжение оценивается путём сжатия контекста + кандидата и проверки того, сколько байт занимает результат сжатия.

Цикл работает так:

1. Подсказка. Начните с подсказки пользователя как начального текста для продолжения. Нет начального токена; байты подсказки просто являются частью контекста, который видит gzip.
2. Контекст. Покажите gzip окно корпуса и недавний хвост сгенерированного текста или подсказки.
3. Поиск. Сохраняйте beam_width наиболее сжимаемых частичных продолжений. Расширьте каждое всеми байтами, которые встречаются в корпусе, оцените все их по длине сжатия и сократьте обратно до лучшего beam_width. Повторяйте для horizon байт.
4. Фиксация. Возьмите наиболее сжимаемый полный промежуток (или произведите выборку среди финалистов, если temperature положительная), добавьте его и начните цикл заново.

Один важный момент: только последние tail байт сгенерированного вывода остаются в контексте оценки. DEFLATE кодирует ближайшие совпадения дешевле, чем дальние, так что если бы gzip мог видеть всю свою историю, самое дешёвое, что делать — часто просто впасть в дословные циклы, многократно копируя текст, который он только что выдал.

Код полностью находится в стандартной библиотеке Python (только zlib). Исходный код доступен на GitHub, если хотите поэкспериментировать.