24 декабря 2009 в 16:47

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

В одном будущем проекте встала задача передавать и хранить данные в формате 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
Денис Потапов @PatapSmile
карма
264,0
рейтинг 0,0
Обо всём и ни о чём
Похожие публикации
Самое читаемое Разработка

Комментарии (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 раза. Если нет ограничения на размер словаря то можно и и все трехбуквенные слова в него внести, и четырех и т.д.

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