24 December 2009

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

Website development
В одном будущем проекте встала задача передавать и хранить данные в формате 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
Tags:ЮникодSCSUBOCU-1сжатие
Hubs: Website development
+46
2.7k 26
Comments 23