company_banner

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

    Знаменитый программист Фабрис Беллар представил свою новую разработку: программа для сжатия без потерь англоязычных сообщений по языковой модели 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 принадлежат ему. Другими словами, он настолько удачно запустил проект, что уже вскоре после запуска другие программисты вложили в него вдвое больше интеллектуальной собственности, чем сам автор!

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

    Комментарии 39

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

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

          0
          ну так ничего не мешает натравить ту же нейросеть для поиска часто повторяющихся кусков бинарных данных… вопрос то будет тот же что и у автора ниже, сколько будет весить архиватор для всего этого добра и какова будет скорость упаковки-распаковки
            0
            ZPAQ. Вот что тебе надо. Работает тоже на предсказании, но не через нейросети. Потенциально можно тюнинговать под любые данные.
              0
              В реальности надо сравнивать разные архиваторы, они могут заточены под конкретный тип файлов, остальные форматы они будет жать хуже. И проверять распаковку, могут и не распаковать.
                +1
                Особенность этого архиватора в том, что в каждый блок архивированых данных записывается алгоритм распаковки. Т.е. для каждого вида данных потенциально может быть свой препроцессор. Создатель сего архиватора вышел на пенсию и больше активно не занимается им. Но и в текущем состоянии он более чем юзабелен и часть его кода находится в паблик домейн, а часть в GPL.
            +6
            интересно включает ли распаковщик в себя те самые 345 миллионов параметров
            и если да то каков размер этого распаковщика
              +2
              Конечно включает.
              221 мегабайт запакованный размер самой маленькой языковой модели с 117 миллионами параметров.
              Вообще тема далеко не новая, для сжатия с потерями нейросети используются очень и очень давно. Здесь интересно, что сделано сжатие без потерь. Ну плюс трансформер, да, это очень мощная модель.
              Меня больше смущает скорость работы, хоть автор и говорит что " is quite fast." — quite может быть весьма расплывчатым понятием для трансформера применяющегося на CPU
                0

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


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


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

              0
              Интересно, иероглифы азиатских стран не наследие неких предков, которые сжимали таким образом свой праязык?
                +7
                Конечно, сжимали. Чтобы уместить побольше текста на маленькую глиняную табличку.
                  +1
                  Насколько помню — иероглифы азиатские это другая ветка развития традиционной пиктографической записи где использовали пиктограммы-образы. Если наши алфавиты в итоге пришли к фонетической записи, а пиктограммы преобразовались в знакомые нам простые символы, то у них наоборот, пиктограммы стали абстрагироваться от первоначального образа и количество их расти, значения множиться и усложняться связи между ними. Можно например в некоторых иероглифах китайских до сих пор увидеть первоначальные образы: гора(山), огонь(火), человек(人), дверь(門).
                    0
                    И у нас можно. А это перевернутая голова быка (алеф — бык -> альфа -> А или A).
                      0
                      Ну вот в случае кириллицы и латиницы даже я, со своей больной фантазией, никак не смогу увидеть в А — быка, а в Е — человека. Тут уже нужна работа специалистов.
                        +1
                        даже я, со своей больной фантазией, никак не смогу увидеть в А — быка

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


                        Вот так: --> ∀


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

                  +1
                  ITSumma
                  Забыли упомянуть еще один проект bellard.org/quickjs
                    +4
                    Удивительный человек! Спасибо ему.
                      +5

                      Ffmpeg — вещь

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

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

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

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

                                    0

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

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

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

                                      0

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

                                        0
                                        Простые слова — это когда понятна суть без профессиональных терминов и аббревиатур:)
                                        А у вас тут набор тегов для коллег)
                                    0
                                    Уникум.
                                      +1
                                      эффективный архиватор текста с учётом вероятности появления следующего слова

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


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

                                        0
                                        Наоборот — с учетом архихтипичности этой фразы, она сожмется лучше среднего.
                                        0
                                        сжимается всего в 10 символов
                                        видимо, 4-хбайтовых, то есть 40 байт?
                                          0
                                          Интересно, а он делает аббревиатуры и сокращения, например вместо Федеральная Служба Безопасности написать в ФСБ, процент сжатия посчитайте сами.
                                            0
                                            Угу, в место сценария игры престолов: «ну кароче там все рандомно умерли»)))

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

                                          Самое читаемое