Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Categories:

Мерси, BOCU-1.

Все из читающих, кто знаком с программированием, наверняка знают, что такое Unicode.
Диапазон значений символа юникод - 0 - 0x10FFFF. То есть, для записи одного символа не достаточно даже двух байт. Нужно три. Исходя из технических соображений, использовать три байта для записи нецелесообразно. Приходится четыре.

А это значит, что одна строчка на русском языке, записагная в несжатом юникоде, должна занимать в четыре раза больше, чем она же, записанная в кодировках KOI-8R или WIN-1251, повсеместно распространённых в интернете. Разумеется, это совсем не дело. Выход номер один даёт ныне лидирующая кодировка под названием UTF-8. Цимес кодировки заключается в том, что для счастливого жителя американскоанглийских земель она работает один к одному, как ставшая привычной за десятилетия существования, US-ASCII. Но не только и не столько в высокомерии американскоанглийских товарищей кроется секрет успеха UTF-8, сколько в том, что с UTF-8 должен без глюков работать софт, писаный тогда, когда про Unicode никто слыхом не слыхивал. Хорошая кодировка, в принципе. Один байт на символ для латиницы, два байта на символ для коротких алфавитов (типа кириллицы) и по три байта на символ для Unihan-a и Hangul-a. (Китайские и корейские иероглифы соответственно.)

Хороша она примерно до тех пор, пока не начинаешь общаться по аське через GPRS, где оплачивается каждый байт. И никакое General Purpose сжатие не поможет сжать сообщения - они слишком короткие.

И тут я задумался, нету ли альтернатив UTF-8. Сразу напал на стандарт под названием SCSU. Замечательный пример виртуозной реализации топорного подхода. Авторы поступили очень прямо - решили в каком-то смысле просто использовать систему со сменяющимеся кодовыми страницами, но при этом сделать это элегантно. В итоге получается совершенно монструозная система, имеющая больше недостатков, чем преимуществ. Невозможность бинарной сортировки, MIME-несовместимость, несовместимость с C-style строками, невозможность быстрой конкатенации, недетерминированность кодирования (одну строку можно записать разными способами), а значит, невозможность быстрого сравнения. Извращенский подход. И при этом, виртуозная реализация. :)

Второе, что я нашел, оказалось го-ораздо интересней. Это назвается BOCU. Детерминированность, возможность очень быстрой конкатенцаии, быстрого сравнения, бинарная упорядоченность в соответствии с порядком Unicode и компактность, эквивалентная SCSU (+/-3%). То есть, почти также компактно, как национальные кодовые страницы. На букву уходит по байту, на знак препинания - по два байта. Это очень небольшая плата за такие качества кодировки.
Однако, прямое использование BOCU не решает проблем совместимости с C-style строками и MIME.

Для решения этих проблем, разработан алгоритм BOCU-1. Проблемы он решает, позитивные качества сохраняет, да и ущерб компактности небольшой. Кодирование и декодирование, правда, усложняются.
Идилическую картину нарушает то, что стандарт сырой, как недоделаный творог.
Стандарта, собственно, и нету. Там написано так: "Вот вам код энкодера и декодера на Си. Он и есть стандарт." Стандартом уже два года никто не занимается. Все бросили, не нужно никому. :(

Для того, чтобы понять, что там как, мне пришлось заниматься reverse-ingeneering'ом около часа. Комментарии в том исходнике тоже считаются плохим тоном, как я понял.
Ну так вот, когда я всё-же разобрал исходник, я как-то довольно быстро заметил, что стандарту BOCU он и не соответствует. Про одну фичу забыли и на знак препинания уходило три байта, вместо двух. Починил, степень сжатия на пробных текстах увеличилась на 2.8%.

Сегодня днём в трамвае пришла идея. Всю дорогу я ехал, смотря в одну точку и считая. Как дошел до дому - не помню. :)

Идея состояла в том, что удлинив энкодер и декодер на полстранички кода, можно влёгкую добиться XML-совместимости. То бишь, того, что если на вход декодеру подать чистый ASCII, он его корректно декодирует. Кроме того, получилась такая фишечка, что любой ASCII-символ кодируется самим собой. Хотя, если перед ним стоял не ASCII-символ, а символ из другого набора, ему будет предшествовать байт 0x01. Это удобно, например тем, что в старых программах ASCII-содержимое файла будет видно. Это имеет смысл, например, в исходниках программ, где код всё-равно ASCII, а вот комментарии могут быть и не на английском.

Абсолютно никаких негативных последствий такое изменение алгоритма не несёт.
Получается MIME-совместимая, C-style-string-совместимая, xml-совместимая, бинарно отсортированая, детерминированная, и весьма эффективная для малых строк система кодирования Unicode.

Замечательно и круто, но, увы, никому не нужно. Экономить память при сегодняшних низких ценах на неё, нужно только там, где используемые объёмы действительно чудовищны. При этом, какое бы то ни было сжатие допустимо только там, где операции с текстом редки. Скажем, если в базе данных постоянно проводят поиск, хранить информацию там будут скорее всего даже не в UTF-8, а в UTF-16.
Если тексты цельные (например, интернет-библиотека какая-нибудь), сжатие каким-нибудь GP-алгоритмом типа Burrows-Wheeler даст несравнимо лучшие результаты, чем любой формат кодирования.

Таким образом, остаются, кажется, всего два случая, когда такая кодировка нужна:
1) Пересылка маленьких пакетов. Например, аська, емайл, html-страницы.
2) Когда имеется некий большой массив строк, к которым требуется лишь доступ (не требуется проведения частого поиска), но доступ быстрый и GP-сжатие не подходит.

И тут кодировка не найдёт применения. Потому что:
1) Она представляет интерес только для неамериканцев. Для американцев идентичные результаты даёт UTF-8.
2) Плюсы от введения кодировки даже близко не окупят труда, который требуется для её введения.

(А тут и пост у человека как-раз о трудах введения как-раз к обеду: http://www.livejournal.com/users/themactep/26418.html)

Некоторым образом понимаю людей, которые не дописали стандарт BOCU-1 до конца. Хотя, всё-же жалко. Хоть для отчётности нужно было довести дело до конца, чтобы на сайте unicode.org можно было написать, что существует со всех сторон удобная и компактная система записи.
Subscribe

  • (no subject)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments

  • (no subject)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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