Фабрис Беллар разработал эффективный архиватор текста с учётом вероятности появления следующего слова +46



Знаменитый программист Фабрис Беллар представил свою новую разработку: программа для сжатия без потерь англоязычных сообщений по языковой модели GPT-2.

Например, сообщение

This lossless compressor achieves a much higher compression rate on English texts than general purpose compressors (116 символов)

сжимается всего в 10 символов:

??????????

Средний уровень компрессии составляет 15?%.

Сжатие осуществляется с учётом вероятности появления следующего слова по языковой модели нейросети GPT-2, которую разработала компания OpenAI (на Хабре был обзор GPT-2 и новость про генератор текста). Это нейросеть с 345 млн параметров на архитектуре Transformer (Фабрис Беллар отмечает, что самая большая модель GPT-2 с 1,5 млрд параметров даёт весьма условное улучшение сжатия). Далее арифметический кодер генерирует битовый поток. В этой демонстрации каждый сжатый символ содержит 15 бит данных и для примера представлен в юникодовских диапазонах двух наборов символов: CJK (китайский-японский-корейский) и хангыль.

Демо реализовано с помощью библиотеки LibNC (ещё один проект Беллара) и работает на стандартном ПК. Можно скачать утилиту командной строки gpt2tc под Linux.

Уровни сжатия для некоторых известных бенчмарков архивирования текста указаны в документации.

File Model Original size Compr. size Ratio CMIX v18
#params (bytes) (bytes) (bpb) ratio (bpb)
book1 117M 768771 152283 1.58 1.82
book1 345M 768771 142183 1.48
book1 774M 768771 137562 1.43
book1 1558M 768771 134217 1.40

alice29.txt 117M 152089 23615 1.24 1.65
alice29.txt 345M 152089 20587 1.08
alice29.txt 774M 152089 19096 1.00
alice29.txt 1558M 152089 17382 0.91

enwik5 117M 100000 14875 1.19 1.60
enwik5 345M 100000 13511 1.08
enwik5 774M 100000 13240 1.06
enwik5 1558M 100000 12918 1.03

Фабрис Беллар также отмечает, что ту же языковую модель можно использовать для автозавершения текстовых сообщений (демо).

Например, фразу:

Habr' community is very

за несколько минут нейросеть дополняет в следующий текст (хотя скорее уместно сказать «сочиняет», а не «дополняет»):



На каждом запуске нейросеть выдаёт совершенно разные варианты.

Фабрис Беллар


Фабрис Беллар известен как автор ряда серьёзных проектов, среди которых FFmpeg, QEMU, загрузчик TinyCC и другие.

Список проектов Фабриса Беллара (здесь перечислена только малая часть):
1989: LZEXE
1996: Harissa
1997: Публикация формулы Беллара для вычисления разрядов числа Пи
1999: Linmodem
2000: Вычисление самого большого известного простого числа (исходный код всего 438 байт)
2000: FFmpeg
2001: Компилятор TCC (Tiny C Compiler или TinyCC)
2002: TinyGL
2002: QEmacs
2003: QEMU
2004: Загрузчик TinyCC
2005: Передатчик сигнала в формате DVB-T с компьютера на телевизор
2009: Мировой рекорд по вычислению числа Пи
2011: Эмулятор компьютера с Linux на JavaScript
2014: формат сжатия изображений Better Portable Graphics (BPG), основанный на подмножестве алгоритмов из видеокодека HEVC
2020: сжатие без потерь англоязычных сообщений с помощью GPT-2

Каждый из этих проектов мог бы стать венцом карьеры для любого разработчика, но Фабрис Беллар продолжает работать. Каждые несколько лет он осваивает новые области: сжатие данных, численные методы, обработка сигналов, медиаформаты, сейчас вот увлёкся нейросетями. Но при этом сохраняет тот же самый чистый C, уместные абстракции и приверженность открытым лицензиям, считают коллеги.

Беллар не склонен к саморекламе (например, вежливо отказывается от интервью), но армия программистов и пользователей широко использует созданные им продукты. Например, среди 654 указаний о копирайте в исходном коде одной из ранних версий QEMU 0.13.0 только 216 принадлежат ему. Другими словами, он настолько удачно запустил проект, что уже вскоре после запуска другие программисты вложили в него вдвое больше интеллектуальной собственности, чем сам автор!

Это значит, что Беллар способен невероятно успешно запускать проекты. Что характерно, он делает это в одиночку, общаясь с миром практически только через интернет.




Комментарии (38):

  1. Cheater
    /#21827454 / +1

    Отдам все деньги тому, кто придумает такой алгоритм для бинарных данных :) Объёмы непакованного plain text — капля в море

    • Hardcoin
      /#21827554 / +4

      Отдайте их разработчикам AV1. Видео — основной трафик в интернете.

    • Desavian
      /#21827640

      ну так ничего не мешает натравить ту же нейросеть для поиска часто повторяющихся кусков бинарных данных… вопрос то будет тот же что и у автора ниже, сколько будет весить архиватор для всего этого добра и какова будет скорость упаковки-распаковки

    • Yaong
      /#21828018

      ZPAQ. Вот что тебе надо. Работает тоже на предсказании, но не через нейросети. Потенциально можно тюнинговать под любые данные.

      • borovichok13
        /#21829030

        В реальности надо сравнивать разные архиваторы, они могут заточены под конкретный тип файлов, остальные форматы они будет жать хуже. И проверять распаковку, могут и не распаковать.

        • Yaong
          /#21830824 / +1

          Особенность этого архиватора в том, что в каждый блок архивированых данных записывается алгоритм распаковки. Т.е. для каждого вида данных потенциально может быть свой препроцессор. Создатель сего архиватора вышел на пенсию и больше активно не занимается им. Но и в текущем состоянии он более чем юзабелен и часть его кода находится в паблик домейн, а часть в GPL.

  2. AAbrosov
    /#21827492 / +6

    интересно включает ли распаковщик в себя те самые 345 миллионов параметров
    и если да то каков размер этого распаковщика

    • shellenberg
      /#21827594 / +2

      Конечно включает.
      221 мегабайт запакованный размер самой маленькой языковой модели с 117 миллионами параметров.
      Вообще тема далеко не новая, для сжатия с потерями нейросети используются очень и очень давно. Здесь интересно, что сделано сжатие без потерь. Ну плюс трансформер, да, это очень мощная модель.
      Меня больше смущает скорость работы, хоть автор и говорит что " is quite fast." — quite может быть весьма расплывчатым понятием для трансформера применяющегося на CPU

      • aamonster
        /#21830710

        А что такого в сжатии без потерь? Если модель выдаёт вероятности следующего символа или слова, дальше просто включается в работу арифметический энкодер. Разновидность ppm алгоритма, я так понимаю.


        Весь интерес – именно в качестве модели. Надо будет посмотреть статистику по архиваторам и сравнить (но в них обычно модель учится с нуля на входящем потоке).


        По скорости – учитывая, что модель обучать на лету не надо, она может быть довольно высока.

  3. evr1ka
    /#21827658

    Интересно, иероглифы азиатских стран не наследие неких предков, которые сжимали таким образом свой праязык?

    • tester12
      /#21827916 / +7

      Конечно, сжимали. Чтобы уместить побольше текста на маленькую глиняную табличку.

    • Yaong
      /#21827980 / +1

      Насколько помню — иероглифы азиатские это другая ветка развития традиционной пиктографической записи где использовали пиктограммы-образы. Если наши алфавиты в итоге пришли к фонетической записи, а пиктограммы преобразовались в знакомые нам простые символы, то у них наоборот, пиктограммы стали абстрагироваться от первоначального образа и количество их расти, значения множиться и усложняться связи между ними. Можно например в некоторых иероглифах китайских до сих пор увидеть первоначальные образы: гора(?), огонь(?), человек(?), дверь(?).

      • Keyten
        /#21830320

        И у нас можно. А это перевернутая голова быка (алеф — бык -> альфа -> А или A).

        • Yaong
          /#21830838

          Ну вот в случае кириллицы и латиницы даже я, со своей больной фантазией, никак не смогу увидеть в А — быка, а в Е — человека. Тут уже нужна работа специалистов.

          • Wesha
            /#21833848

            даже я, со своей больной фантазией, никак не смогу увидеть в А — быка

            Да ёктель! Кверху ногами переверните!


            Вот так: --> ?


            Видите сужающуюся книзу морду и рога?

  4. /#21827842 / +1

    ITSumma
    Забыли упомянуть еще один проект bellard.org/quickjs

  5. /#21827938 / +4

    Удивительный человек! Спасибо ему.

  6. /#21828218 / +5

    Ffmpeg — вещь

  7. Nikobraz
    /#21828466 / +3

    А можно просто переводить на китайский. Сжатие достаточное, и не нужно разархивировать

    • Oplkill
      /#21828572 / +1

      так как это будут потери, иногда сильные

      • Nikobraz
        /#21828584

        а насколько устойчив к потерям данных алгоритм из сей статьи?

        • shiru8bit
          /#21828624 / +2

          Алгоритм из статьи работает без потерь.

  8. namikiri
    /#21828488 / +3

    Фабрис крутой! Сколько у него проектов, тут вот выше показали ссылку на QuickJS — последний релиз был четыре дня назад! Откуда у него столько эмоциональных и физических сил на всё это? Честь и хвала таким людям.

    • perfect_genius
      /#21833232 / +1

      Видимо, ему не надо зарабатывать на еду.

  9. WST
    /#21828518

    Из всего, что я пробовал, лучше всего сжимало тексты (впрочем, как и любые другие данные) оно, но, увы, достигнуто это доведённым до абсурда потреблением памяти и отсутствием распараллеливания.

  10. borovichok13
    /#21828760

    Когда-то увлекался сравнением уровня сжатия архиваторов. Не самый шустрый и достаточно старый Nanozip сжимает текстовый файл до 15 %. Сразу возникает вопрос скорости сжатия архива? Обычно, чем лучше жмет — тем дольше работает архиватор.
    Для теста использована модель enwik5, хотя сейчас принято тестировать enwik9 (на 4 порядка больше файл). Есть даже приз 500000 евро кто сожмет лучше всех.
    Кстати, cmix v18 сжимает enwik9 до 11.6% (http://mattmahoney.net/dc/text.html — там большая таблица архиваторов приведена)

  11. jedecuz
    /#21828762

    Реинкарнация архиватора ha.com?
    Помнится в свое время его в книжной файлэхе использовали потому что он лучше всего голый текст жал.

    • Dolios
      /#21829514

      ha.com — это же Хаффман банальный.

      • aamonster
        /#21830720

        Нет. Это ppm (не помню, с хаыфманом или с арифметическим энкодером в качестве финального шага), с контекстом в 4 символа, емнип.

  12. vrangel
    /#21828868

    Очень крутой проект Фабриса — Amarisoft.com. Правда, коммерческий. Но крутой.

    • x67
      /#21830450

      Расскажите подробнее, а то выглядит как кликбейтный коммент)
      Зашел на сайт и в 4 ночи не понял, что конкретно они делают

      • vrangel
        /#21836172

        Если простыми словами: lte epc, lte enb с подключенным sdr. Также всякие сопутствующие штуки, типа эмулятора UE

        • x67
          /#21848818

          Простые слова — это когда понятна суть без профессиональных терминов и аббревиатур:)
          А у вас тут набор тегов для коллег)

  13. drWhy
    /#21829808

    Уникум.

  14. Wesha
    /#21830302 / +1

    эффективный архиватор текста с учётом вероятности появления следующего слова

    Варкалось. Хливкие шорьки пырялись по наве, и хрюкотали зелюки, как мюмзики в мове.


    (Кажется, я сломал архиватор ;)

    • DoubleW
      /#21831282

      Наоборот — с учетом архихтипичности этой фразы, она сожмется лучше среднего.

  15. maxzhurkin
    /#21833492

    сжимается всего в 10 символов
    видимо, 4-хбайтовых, то есть 40 байт?

  16. Diordna
    /#21838636

    Интересно, а он делает аббревиатуры и сокращения, например вместо Федеральная Служба Безопасности написать в ФСБ, процент сжатия посчитайте сами.