Сжатие Юникод данных

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

    Было несколько вариантов:
    1. Использовать традиционные кодировки (для кириллицы — CP1251).
    2. Использовать форматы сжатия Юникода. На сегодняшний день это — SCSU и BOCU-1. Детальное описание этих двух форматов привожу ниже.
    3. Использовать универсальные алгоритмы сжатия (gzip).

    Красивый, но бесполезный, график результатов:
    image


    Входные данные


    Визитная карточка в формате VCard 3.0 (длина 260 символов):

    BEGIN:VCARD
    VERSION:3.0
    N:Пупкин;Василий
    FN:Василий Пупкин
    ORG:ООО «Рога и Копыта»
    TITLE:Самый главный
    TEL;TYPE=WORK,VOICE: +380 (44) 123-45-67
    ADR;TYPE=WORK:;1;Крещатик;Киев;;01001;UKRAINE
    EMAIL;TYPE=PREF,INTERNET:vasiliy.pupkin@example.com
    END:VCARD
    

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

    Вариант с использованием CP1251 отпал сразу. Несмотря на маленький размер готовых файлов его использование (как и любой другой традиционной кодировки) сильно ограничивает возможности сервиса.

    SCSU


    Стандартная схема сжатия (The Standard Compression Scheme for Unicode, SCSU) основана на разработке Рейтер.

    Основная идея SCSU — определение динамических окон на пространстве кодов Юникод. Символы, принадлежащие к небольшим алфавитам (например, кириллице) могут быть закодированы одним байтом, который указывает индекс символа в текущем окне. Окна предустановленны к блокам, которые чаще всего используются, так что кодировщику не приходиться их задавать.

    Для больших алфавитов, включая Китайский язык, SCSU позволяет переключаться между однобайтовым и «Юникод режимом», который на самом деле является UTF-16BE.

    Управляющие байты («теги») вставляются в текст, чтобы изменять окна и режимы. Теги экранирования («quote» tags), используются для переключения в другое окно только для следующего символа. Это полезно для кодирования одного символа вне текущего окна, или символа, который конфликтует с тегами.

    Пример

    … N  :    П   у  п  к  и  н  … F  N  :  В  а  с  и  л  и  й  …
    … 4E 3A 12 9F C3 BF BA B8 BD … 46 4E 3A 92 B0 C1 B8 BB B8 B9 …
    

    Перед первой кириллической буквой кодер использует тег SC2 (шестнадцатеричное 12), чтобы переключиться в динамическое окно №2, которое предустановленно на кириллический блок символов. При повторном использовании кириллических символов, тег не используется.

    Преимущества

    • текст, закодированный в SCSU, в основном занимает столько же места, сколько и в традиционной кодировке. Накладные расходы на теги относительно незначительны.
    • SCSU декодер легко реализовать, в сравнении с универсальными алгоритмами сжатия.

    Недостатки

    • SCSU использует контрольные символа ASCII, не только как теги, но и как часть обычных символов. Это делает SCSU неподходящим форматом для таких протоколов как MIME, которые интерпретируют контрольные символы без их декодирования.


    BOCU-1


    Концепция бинарно упорядоченного сжатия (The Binary Ordered Compression for Unicode, BOCU) была разработана в 2001 году (by Mark Davis and Markus Scherer for the ICU project).

    Основанная идея BOCU-1 — кодировать каждый символ как разницу (расстояние в таблице Юникод) к предыдущему символу. Небольшие разницы занимают меньшее количество байт, чем большие. Кодируя разницы, BOCU-1 достигает одинакового сжатия для небольших алфавитов, в каком бы блоке они не находились.

    BOCU-1 дополняет концепцию следующими правилами:
    • Предыдущее или базовое значение выравнивается по середине блока, во избежание больших прыжков из начала блока в конец.
    • 32 контрольных символа ASCII, а также пробелы не изменяться при кодировании, для совместимости с электронной почтой и для сохранения бинарного порядка
    • Пробел не вызывает изменения базовой величины. Это означает что при кодировании нелатинских слов разделенных пробелами, нет необходимости делать большой скачок до U+0020 и назад.
    • контрольные символы ASCII сбрасывают базовую величину, что делает соседние строки в файле независимыми.


    Пример

    … N  :    П   у  п  к  и  н    ;     В   … F  N  :    В   а  с  и  л  и  й  …
    … 9e 8a d3 d3 93 8f 8a 88 8d 4c 11 d3 c6 … 96 9e 8a d3 c6 80 91 88 8b 88 89 …
    

    На каждую смену блока (переход из кириллицы в латиницу) кодеру необходимо два байта (d3 – для переключения в кириллический блок, 4c – для двоеточия).

    Преимущества

    • Контрольные символы ASCII остаются при кодировании
    • Как и SCSU, BOCU-1 требует небольших накладных расходов в сравнении с традиционными кодировками


    Недостатки

    • Латинские буквы (и все ASCII символы, кроме контрольных) меняют свое значение при кодировании. Так, например, XML парсер должен получить информацию о BOCU-1 кодировке из протокола более высокого уровня.
    • Алгоритм BOCU-1 нигде формально не описан, кроме программного кода сопровождающего UTN #6.


    Универсальные алгоритмы сжатия


    Для сравнения эффективности был выбран алгоритм сжатия gzip. Для больших текстов gzip показывает большую степень сжатия в сравнении SCSU и BOCU-1 (так как количество разных символов даже в многоязычных документах ограничено). На небольших текстах, как VCard в примере, однозначный результат получить сложно.

    Существенным недостатком универсальных алгоритмов сжатия есть сложность реализации компрессора и декомпрессора.
    Вопрос о двухэтапном сжатии (например, SCSU + gzip) для меня остается открытым.

    Результаты


    Результаты работы алгоритмов SCSU и BOCU-1 для исходных данных в сравнении с CP1251 и UTF8 показаны в первой колонке.

    Вторая колонка представляет количество байт выданных непосредственно кодером (без Ма́ркер поря́дку ба́йт, BOM, который указывает на тип представления Юникод в файле).

    Третья колонка представляет файл сжатый gzip

    Четвертая колонка показывает количество байт данных в gzip архиве (без заголовка, 18 байт).

    Файл Файл без BOM В архиве Длина данных в архиве
    CP1251 260 260 258 240
    SCSU 267 264 266 248
    BOCU-1 278 275 273 255
    UTF8 329 326 299 281

    Все файлы в архиве (5 кб).

    Применение


    SQL Server 2008 R2 использует SCSU для хранения nchar(n) и nvarchar(n). Symbian OS использует SCSU для сериализации строк.

    Для работы с SCSU и BOCU-1 можно использовать ICU или SC UniPad
    .

    Меня очень удивило, что ни один из распространенных ридеров штрих кодов не распознает SCSU или BOCU-1.

    Что еще почитать


    Unicode Technical Note #14. A Survey of Unicode Compression
    Unicode Technical Standard #6. A Standard Compression Scheme for Unicode
    Unicode Technical Note #6. BOCU-1:MIME-Compatible Unicode Compression
    Метки:
    Поделиться публикацией
    Похожие публикации
    Комментарии 22
    • +1
      Судя по описаниям, SCSU — самое оно. Особенно для собственного клиента.
      Правда не совсем понял что такое:
      SCSU неподходящим форматом для таких протоколов как MIME

      Можешь привести пример возможных конфликтов?
      • 0
        Нет, пример привести не могу. В спецификации MIME заголовков указанно, что внутри поля заголовка не должны встречаться символы CR и LF, а результатом SCSU кодирования не латинских символов могут быть как раз CR (0x0A) и LF (0x0D).
        • +1
          Так в MIME-заголовках и так только ASCII может быть (по крайней мере так интерпретируют большинство софтописателей).

          Возможно, вы имели в виду, что перекодирование CR/LF внутри тела письма зависит от заголовка Content-transfer-encoding (не перекодируется только в случае binary и base64) и особенностей конкретного почтового ПО(?)…
      • +1
        Применение архиватора общего назначения, когда объем данных меньше килобайта, редко дает положительный результат. Возможно, имеет смысл рассмотреть схему с внешним словарем.
        • 0
          Согласен. Вполне можно, кстати, подобрать свое дерево хафмана с соотв. кодами для оптимального сжатия.
          • 0
            Где можно почитать примеры реализации (или уже готовые библиотеки) для сжатия данных со внешним словарем?

            Впереди маячит задача когда клиент и сервер передают друг другу плохо упаковываемые данные но содержащие много данных, передаваемых в прошлых запросах, пока есть идеи используя технологию binary diff — высылается разница между неким шаблоном и самим сообщением. Однобокое решение требует допиливания (шаблонов много, какой использовать решить нетривиально и данные в сообщении могут перемешиваться, что не отлавливается этим методом).
            • 0
              Я не занимался этим вопросом применительно к тексту, к сожалению. Думаю, в случае с VCARD должна неплохо работать схема из PPM + Хаффман (либо арифметическое кодирование). Особенность в Вашем случае в том, что словарь для Хаффмана можно тренировать один раз на некотором наборе сэмплов, а не для каждого файла. Т.к. данные достаточно однородные, проигрыш в сжатии не должен быть очень большим, зато можно не передавать словарь каждый раз. Кроме того, думаю, похожую идею можно применить и к PPM.
          • +2
            А можно, собственно, уточнить — какая именно задача оптимизации ставилась? Карточки будут передаваться/сжиматься для передачи по одной? Какие мощности будут в распоряжении передающей/принимающей стороны? Сколько времени и ресурсов можно позволить себе потратить на сжатие/разжатие?
            • +1
              Для этого конкретного случая — хранение визитки в двумерном штрихкоде. Считывание мобильными устройствами. На мобильных телефонах можно устойчиво распознавать штрихкоды содержащие до 500 байт.

              При таких исходных данных, юникод компрессия может показывать результат лучше чем универсальные алгоритмы.

              • 0
                Теперь понятно — тогда полностью согласен, что для такой задачи это будет оптимальное решение. А то всё гадал, для чего это может понадобиться ужимать _один_ пакет на сотню байт. Любые сетевые передачи, о которых я думал, упирались в размер пакета порядка килобайта — экономия сотни байт здесь вряд ли что-то радикально дала бы. Хотя, если MTU до 576 опускать — может тогда и здесь было бы тоже актуально…

                В таком случае, наверное, еще полезно было бы сжать VCARD сам по себе: убрать максимум метаинформации, перейти к обозначению полей какими-нибудь бинарными тэгами и т.п.
                • 0
                  Тут изначально задумка была получить VCard, который смогут читать сторонние штрих-читатели, судя по
                  Меня очень удивило, что ни один из распространенных ридеров штрих кодов не распознает SCSU или BOCU-1.
                  • 0
                    Ридеры штрих-кодов выдают байтовый поток — зачем им что-то с ним делать? А вот то, куда ридер подключен — там можно и раскодировать этот поток, и сделать lookup в базу, и еще много чего, как правило.

                    Даже для standalone ридеров — как правило, есть какая-то возможность их программировать — сколько правда их видел — они почему-то все под DOS были: туда через COM-порт передается com/exe/bat-файл, который может вызываться и что-то там с полученными данными делать.
                  • 0
                    Да рассматривал и вариант изменения VCARD (пример). Но во-первых, кто еще, кроме меня, будет поддерживать мой велосипед. А во-вторых, VCARD (особенно 3.0) интересен сам по себе: многоязычные визитки, версии и источник визитки. Придумывать самому, обязательно бы что-то пропустил.
                    • 0
                      Гм, а кто-то уже поддерживает сканирование и дальнейшее использование VCard с визитки? Может действительно проще ужать формат VCard и сделать что-то свое?
              • 0
                Спасибо за обзор. Проблема актуальна, особенно в WEB.
                • +1
                  В классическом вебе уже давно (очень давно) применяется и gzip и bzip алгоритмы сжатия потока… Даже из вышеприведенных графиков непонятен смысл сжатия дважды в web.
                  • 0
                    Может пригодиться в будущем Bluetooth low energy.

                    А при хранении nchar в SQL Server в SCSU экономия пространства составляет от 15% до 50%.
                    • 0
                      «А при хранении nchar в SQL Server ...» — А если взять базу, шринкнуть и запаковать в какой-нибуд 7z архив… вот там экономия… но ведь это не относится к вебу, не так ли?

                      Равно как и блутувз — оно, конечно, очень (наверно) будет круто съкономить чуть-чуть энергии в блутувс модуле на передачу, при этом потратив б0льшее количество (наверняка) энергии на сжатие\распаковку.
                • 0
                  Интересно, что за проект )
                  Вообще VCard нормально хранится в Latin-1 с использованием для UTF-8 кодирования Quoted-Printable. Обычно полей не с латиницей одно-два, и это очень эффективно.
                  Кроме того, обычно при работе с карточками интересно бывает работать с отдельными полями. А архивирование карточки целиком сильно усложняет дело.
                  • 0
                    Проект — VCard в двумерном штрихкоде (см. выше)
                    • 0
                      А, класс! Да, но QP всё равно может пригодиться. Опять же для стандартных полей можно использовать «сжатие» с заменой названий на короткие из статического словаря.
                  • 0
                    Как вариант, может быть стоит попробовать VCard перевести в base64 encoding (т.е. получить всего всего 64 различных символа) и построить статический словарь для метода Хаффмана или арифметического метода. После перевода в base64 размер текста увеличится на 30%, но статический словарь из одних двухбуквенных слов уже позволит эти 130% уменьшить в 2 раза. Если нет ограничения на размер словаря то можно и и все трехбуквенные слова в него внести, и четырех и т.д.

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