Ещё один велосипед: храним юникодные строки на 30-60% компактнее, чем UTF-8



    Если вы разработчик и перед вами стоит задача выбора кодировки, то почти всегда правильным решением будет Юникод. Конкретный способ представления зависит от контекста, но чаще всего тут тоже есть универсальный ответ — UTF-8. Он хорош тем, что позволяет использовать все символы Юникода, не тратя слишком много байт в большинстве случаев. Правда, для языков, использующих не только латиницу, «не слишком много» — это как минимум два байта на символ. Можно ли лучше, не возвращаясь к доисторическим кодировкам, ограничивающим нас всего 256 доступными символами?

    Ниже предлагаю ознакомиться с моей попыткой дать ответ на этот вопрос и реализацию относительно простого алгоритма, позволяющего хранить строчки на большинстве языков мира, не добавляя той избыточности, которая есть в UTF-8.

    Дисклеймер. Сразу сделаю несколько важных оговорок: описанное решение не предлагается как универсальная замена UTF-8, оно подходит только в узком списке случаев (о них ниже), и его ни в коем случае нельзя использовать для взаимодействия со сторонними API (которые о нём и знать не знают). Чаще всего для компактного хранения больших объемов текстовых данных подойдут алгоритмы сжатия общего назначения (например, deflate). Кроме того, уже в процессе создания своего решения я нашёл существующий стандарт в самом Юникоде, который решает ту же задачу — он несколько сложнее (и нередко хуже), но всё-таки является принятым стандартом, а не собранным на коленке. О нём я тоже расскажу.

    О Unicode и UTF-8


    Для начала — несколько слов о том, что вообще такое Unicode и UTF-8.

    Как известно, раньше имели популярность 8-битные кодировки. С ними всё было просто: 256 символов можно занумеровать числами от 0 до 255, а числа от 0 до 255 очевидным образом представимы в виде одного байта. Если возвращаться к самым истокам, то кодировка ASCII и вовсе ограничивается 7 битами, поэтому самый старший бит в её байтовом представлении равен нулю, и большинство 8-битных кодировок с ней совместимы (они различаются только в «верхней» части, где старший бит — единица).

    Чем же от тех кодировок отличается Юникод и почему с ним связано сразу множество конкретных представлений — UTF-8, UTF-16 (BE и LE), UTF-32? Разберёмся по порядку.

    Основной стандарт Юникода описывает только соответствие между символами (а в некоторых случаях — отдельными компонентами символов) и их номерами. И возможных номеров в этом стандарте очень много — от 0x00 до 0x10FFFF (1 114 112 штук). Если бы мы хотели положить число в таком диапазоне в переменную, ни 1, ни 2 байт нам бы не хватило. А так как под работу с трехбайтовыми числами наши процессоры не очень заточены, мы были бы вынуждены использовать целых 4 байта на один символ! Это и есть UTF-32, но именно из-за этой «расточительности» этот формат не пользуется популярностью.

    К счастью, символы внутри Юникода упорядочены не случайно. Всё их множество разделено на 17 «плоскостей», каждая из которых содержит 65536 (0x10000) «кодовых точек». Понятие «кодовой точки» тут — это просто номер символа, присвоенный ему Юникодом. Но, как было сказано выше, в Юникоде занумерованы не только отдельные символы, но также их компоненты и служебные пометки (а иногда и вовсе номеру ничего не соответствует — возможно, до поры до времени, но для нас это не так важно), поэтому корректнее всегда говорить именно про число самих номеров, а не символов. Однако далее для краткости я часто буду употреблять слово «символ», подразумевая термин «кодовая точка».

    Плоскости Юникода. Как видно, большая часть (плоскости с 4 по 13) всё ещё не использована.
    Плоскости Юникода. Как видно, большая часть (плоскости с 4 по 13) всё ещё не использована.

    Что самое замечательное — вся основная «мякотка» лежит в нулевой плоскости, она называется "Basic Multilingual Plane". Если строчка содержит текст на одном из современных языков (включая китайский), за пределы этой плоскости вы не выйдете. Но отсекать остальную часть Юникода тоже нельзя — например, эмодзи в основном находятся в конце следующей по счёту плоскости, "Supplementary Multilingual Plane" (она простирается от 0x10000 до 0x1FFFF). Поэтому UTF-16 поступает так: все символы, попадающие в Basic Multilingual Plane, кодируются «как есть», соответствующим им двухбайтовым числом. Однако часть чисел в этом диапазоне вообще не обозначают конкретные символы, а указывают на то, что следом за этой парой байт нужно рассмотреть ещё одну — скомбинировав значения этих четырёх байт вместе, у нас получится число, охватывающее весь допустимый диапазон Юникода. Такое представление называется «суррогатными парами» — возможно, вы о них слышали.

    Таким образом, UTF-16 требует два или (в очень редких случаях) четыре байта на одну «кодовую точку». Это лучше, чем постоянно использовать четыре байта, но латиница (и другие ASCII-символы) при таком кодировании расходует половину занимаемого места на нули. UTF-8 призван это поправить: ASCII в нём занимает, как раньше, всего один байт; коды от 0x80 до 0x7FF — два байта; от 0x800 до 0xFFFF — три, а от 0x10000 до 0x10FFFF — четыре. С одной стороны, латинице стало хорошо: вернулась совместимость с ASCII, да и распределение более равномерно «размазано» от 1 до 4 байт. Но алфавиты, отличные от латинского, увы, никак не выигрывают по сравнению с UTF-16, а многие и вовсе теперь требуют трёх байт вместо двух — диапазон, покрываемый двухбайтовой записью, сузился в 32 раза, с 0xFFFF до 0x7FF, и в него не попадает уже ни китайский, ни, к примеру, грузинский. Кириллице и ещё пяти алфавитам — ура — повезло, 2 байта на символ.

    Почему так выходит? Давайте посмотрим, как UTF-8 представляет коды символов:

    Непосредственно для представления чисел тут использованы биты, помеченные символом x. Видно, что в двухбайтовой записи таких бит лишь 11 (из 16). Ведущие биты тут несут только служебную функцию. В случае с четырёхбайтовой записью и вовсе под номер кодовой точки отведён 21 бит из 32 — казалось бы, тут хватило бы и трёх байт (которые дают суммарно 24 бита), но служебные маркеры съедают слишком много.

    Плохо ли это? На самом деле, не очень. С одной стороны — если мы сильно заботимся о занимаемом пространстве, у нас есть алгоритмы сжатия, которые легко устранят всю лишнюю энтропию и избыточность. С другой — целью Юникода было дать максимально универсальное кодирование. Например, закодированную в UTF-8 строчку мы можем доверить коду, который раньше работал только с ASCII, и не бояться, что он там увидит символ из ASCII-диапазона, которого там на самом деле нет (ведь в UTF-8 все байты, начинающиеся с нулевого бита — это именно ASCII и есть). А если мы захотим вдруг отрезать маленький хвост от большой строки, не декодируя её с самого начала (или восстановить часть информации после повреждённого участка) — нам несложно найти то смещение, где начинается какой-то символ (достаточно пропустить байты, имеющие битовый префикс 10).

    Зачем же тогда выдумывать что-то новое?


    В то же время, изредка бывают ситуации, когда алгоритмы сжатия вроде deflate плохоприменимы, а добиться компактного хранения строк хочется. Лично я столкнулся с такой задачей, размышляя о построении сжатого префиксного дерева для большого словаря, включающего слова на произвольных языках. С одной стороны — каждое слово очень короткое, поэтому сжимать его будет неэффективно. С другой — реализация дерева, которую я рассматривал, была рассчитана на то, что каждый байт хранимой строки порождал отдельную вершину дерева, так что минимизировать их количество было очень полезно. В моей библиотеке Az.js (как и в pymorphy2, на котором она основана) подобная проблема решается просто — строки, упакованные в DAWG-словарь, хранятся там в старой доброй CP1251. Но, как нетрудно понять, это хорошо работает только для ограниченного алфавита — строчку на китайском в такой словарь уже не сложить.

    Отдельно отмечу ещё один неприятный нюанс, который возникает при использовании UTF-8 в такой структуре данных. На картинке выше видно, что при записи символа в виде двух байт, биты, относящиеся к его номеру, не идут подряд, а разорваны парой бит 10 посередине: 110xxxxx 10xxxxxx. Из-за этого, когда в коде символа переполняются младшие 6 бит второго байта (т.е. происходит переход 1011111110000000), то меняется и первый байт тоже. Получается, что буква «п» обозначается байтами 0xD0 0xBF, а следующая за ней «р» — уже 0xD1 0x80. В префиксном дереве это приводит к расщеплению родительской вершины на две — одной для префикса 0xD0, и другой для 0xD1 (хотя вся кириллица могла бы кодироваться только вторым байтом).

    Что у меня получилось


    Столкнувшись с этой задачей я решил поупражняться в играх с битами, а заодно чуть лучше познакомиться со структурой Юникода в целом. Результатом стал формат кодирования UTF-C («C» от compact), который тратит не более 3 байт на одну кодовую точку, а очень часто позволяет тратить лишь один лишний байт на всю кодируемую строчку. Это приводит к тому, что на многих не-ASCII алфавитах такое кодирование оказывается на 30-60% компактнее UTF-8.

    Я оформил примеры реализации алгоритмов кодирования и декодирования в виде библиотек на JavaScript и Go, вы можете свободно использовать их в своём коде. Но я всё же подчеркну, что в некотором смысле этот формат остаётся «велосипедом», и я не рекомендую его использовать без осознания того, зачем он вам нужен. Это всё-таки больше эксперимент, чем серьёзное «улучшение UTF-8». Тем не менее, код там написан аккуратно, лаконично, с большим числом комментариев и покрытием тестами.

    Результат выполнения тестов и сравнение с UTF-8
    Результат выполнения тестов и сравнение с UTF-8

    Ещё я сделал демо-страничку, где можно оценить работу алгоритма, а далее я расскажу подробнее о его принципах и процессе разработки.

    Устраняем избыточные биты


    За основу я взял, конечно, UTF-8. Первое и самое очевидное, что в нём можно поменять — уменьшить число служебных бит в каждом байте. Например, первый байт в UTF-8 всегда начинается либо с 0, либо с 11 — а префикс 10 есть только у следующих байт. Заменим префикс 11 на 1, а у следующих байт уберём префиксы совсем. Что получится?

    0xxxxxxx — 1 байт
    10xxxxxx xxxxxxxx — 2 байта
    110xxxxx xxxxxxxx xxxxxxxx — 3 байта

    Стоп, а где же четырёхбайтовая запись? А она стала не нужна — при записи тремя байтами у нас теперь доступен 21 бит и этого с запасом хватает на все числа до 0x10FFFF.

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

    Ситуация с покрытием языков 2 байтами тоже стала лучше: теперь двухбайтовый формат даёт диапазон в 14 бит, а это коды до 0x3FFF. Китайцам не везёт (их иероглифы в основном лежат в диапазоне от 0x4E00 до 0x9FFF), но вот грузинам и многим другим народам стало повеселее — их языки тоже укладываются в 2 байта на символ.

    Вводим состояние энкодера


    Давайте теперь подумаем о свойствах самих строчек. В словаре чаще всего лежат слова, написанные символами одного алфавита, да и для многих других текстов это тоже верно. Было бы хорошо один раз указать этот алфавит, а дальше указывать только номер буквы внутри него. Посмотрим, поможет ли нам расположение символов в таблице Юникода.

    Как было сказано выше, Юникод поделён на плоскости по 65536 кодов каждая. Но это не очень полезное деление (как уже сказано, чаще всего мы находимся в нулевой плоскости). Более интересным является деление на блоки. Эти диапазоны уже не имеют фиксированной длины, и несут больше смысла — как правило, каждый объединяет символы одного алфавита.

    Блок, содержащий символы бенгальского алфавита. К сожалению, по историческим причинам, это пример не очень плотной упаковки — 96 символов хаотично раскиданы по 128 кодовым точкам блока.
    Блок, содержащий символы бенгальского алфавита. К сожалению, по историческим причинам, это пример не очень плотной упаковки — 96 символов хаотично раскиданы по 128 кодовым точкам блока.

    Начала блоков и их размеры всегда кратны 16 — сделано это просто для удобства. Кроме того, многие блоки начинаются и заканчиваются на значениях, кратных 128 или даже 256 — например, основная кириллица занимает 256 байт от 0x0400 до 0x04FF. Это довольно удобно: если мы один раз сохраним префикс 0x04, то дальше любой кириллический символ можно записывать одним байтом. Правда, так мы потеряем возможность вернуться к ASCII (и к любым другим символам вообще). Поэтому делаем так:

    1. Два байта 10yyyyyy yxxxxxxx не только обозначают символ с номером yyyyyy yxxxxxxx, но и меняют текущий алфавит на yyyyyy y0000000 (т.е. запоминаем все биты, кроме младших 7 бит);
    2. Один байт 0xxxxxxx это символ текущего алфавита. Его нужно просто сложить с тем смещением, которое мы запомнили на шаге 1. Пока алфавит мы не меняли, смещение равно нулю, так что совместимость с ASCII мы сохранили.

    Аналогично для кодов, требующих 3 байт:

    1. Три байта 110yyyyy yxxxxxxx xxxxxxxx обозначают символ с номером yyyyyy yxxxxxxx xxxxxxxx, меняют текущий алфавит на yyyyyy y0000000 00000000 (запомнили всё, кроме младших 15 бит), и ставят флажок, что мы теперь в длинном режиме (при смене алфавита обратно на двухбайтовый этот флажок мы сбросим);
    2. Два байта 0xxxxxxx xxxxxxxx в длинном режиме это символ текущего алфавита. Аналогично, мы складываем его со смещением из шага 1. Вся разница только в том, что теперь мы читаем по два байта (потому что мы переключились в такой режим).

    Звучит неплохо: теперь пока нам нужно кодировать символы из одного и того же 7-битного диапазона Юникода, мы тратим 1 лишний байт в начале и всего по байту на каждый символ.

    Работа одной из ранних версий. Уже нередко обходит UTF-8, но ещё есть что улучшать.
    Работа одной из ранних версий. Уже нередко обходит UTF-8, но ещё есть что улучшать.

    Что стало хуже? Во-первых, у нас появилось состояние, а именно смещение текущего алфавита и флажок длинного режима. Это нас дополнительно ограничивает: теперь одни и те же символы могут быть закодированы по-разному в разных контекстах. Поиск подстрок, например, придётся делать уже с учётом этого, а не просто сравнивая байты. Во-вторых, как только мы сменили алфавит, стало плохо с кодированием ASCII-символов (а это не только латиница, но и базовая пунктуация, включая пробелы) — они требуют повторной смены алфавита в 0, то есть снова лишнего байта (а потом ещё одного, чтобы вернуться к нашему основному).

    Один алфавит хорошо, два — лучше


    Попробуем чуть-чуть поменять наши битовые префиксы, втиснув к трём вышеописанным ещё один:

    0xxxxxxx — 1 байт в обычном режиме, 2 в длинном
    11xxxxxx — 1 байт
    100xxxxx xxxxxxxx — 2 байта
    101xxxxx xxxxxxxx xxxxxxxx — 3 байта



    Теперь в двухбайтовой записи на один доступный бит стало меньше — помещаются кодовые точки вплоть до 0x1FFF, а не 0x3FFF. Впрочем, всё ещё ощутимо больше, чем в двухбайтовых кодах UTF-8, большая часть распространённых языков всё ещё влезает, самая заметная потеря — выпала хирагана и катакана, японцы в печали.

    Что же за новый код 11xxxxxx? Это небольшой «загашник» размером в 64 символа, он дополняет наш основной алфавит, поэтому я назвал его вспомогательным (auxiliary) алфавитом. Когда мы переключаем текущий алфавит, то кусок старого алфавита становится вспомогательным. Например, переключились с ASCII на кириллицу — в «загашнике» теперь 64 символа, содержащих латиницу, цифры, пробел и запятую (самые частые вставки в не-ASCII текстах). Переключились обратно на ASCII — и вспомогательным алфавитом станет основная часть кириллицы.

    Благодаря доступу к двум алфавитам, мы можем справиться с большим количеством текстов, имея минимальные затраты на переключение алфавитов (пунктуация чаще всего будет приводить к возврату в ASCII, но после этого многие не-ASCII символы мы будем доставать уже из дополнительного алфавита, без повторного переключения).

    Бонус: обозначив допалфавит префиксом 11xxxxxx и выбрав его начальное смещение равным 0xC0, у нас получается частичная совместимость с CP1252. Иными словами, многие (но не все) западноевропейские тексты, закодированные в CP1252, будут выглядеть так же и в UTF-C.

    Тут, правда, возникает трудность: как из основного алфавита получить вспомогательный? Можно оставить то же самое смещение, но — увы — тут структура Юникода уже играет против нас. Очень часто основная часть алфавита находится не в начале блока (например, русская заглавная «А» имеет код 0x0410, хотя кириллический блок начинается с 0x0400). Таким образом, взяв в «загашник» первые 64 символа, мы, возможно, утратим доступ к хвостовой части алфавита.

    Для устранения этой проблемы я вручную прошёлся по некоторым блокам, соответствующим различным языкам, и указал для них смещение вспомогательного алфавита внутри основного. Латиницу, в порядке исключения, вообще переупорядочил наподобие base64.




    Финальные штрихи


    Давайте напоследок подумаем, где мы ещё можем что-то доработать.

    Заметим, что формат 101xxxxx xxxxxxxx xxxxxxxx позволяет закодировать числа вплоть до 0x1FFFFF, а Юникод заканчивается раньше, на 0x10FFFF. Иными словами, последняя кодовая точка будет представлена как 10110000 11111111 11111111. Стало быть, мы можем сказать, что если первый байт имеет вид 1011xxxx (где xxxx больше 0), то он обозначает что-то ещё. Например, можно добавить туда ещё 15 символов, постоянно доступные для кодирования одним байтом, но я решил поступить по-другому.

    Посмотрим на те блоки Юникода, которые требуют трёх байт сейчас. В основном, как уже было сказано, это китайские иероглифы — но с ними трудно что-то сделать, их 21 тысяча. Но ещё туда улетела хирагана с катаканой — а их уже не так много, меньше двухсот. И, раз уж мы вспомнили про японцев — там же лежат эмодзи (на самом деле они много где раскиданы в Юникоде, но основные блоки в диапазоне 0x1F3000x1FBFF). Если подумать о том, что сейчас существуют эмодзи, которые собираются из сразу нескольких кодовых точек (например, эмодзи ‍‍‍ состоит аж из 7 кодов!), то становится совсем жалко тратить на каждую по три байта (7×3 = 21 байт ради одного значка, кошмар же).

    Поэтому выбираем несколько избранных диапазонов, соответствующих эмодзи, хирагане и катакане, перенумеровываем их в один непрерывный список и кодируем в виде двух байт вместо трёх:

    1011xxxx xxxxxxxx

    Отлично: вышеупомянутый эмодзи ‍‍‍, состоящий из 7 кодовых точек, в UTF-8 занимает 25 байт, а мы уместили его в 14 (ровно по два байта на каждую кодовую точку). Кстати, Хабр отказался его переваривать (как в старом, так и в новом редакторе), так что пришлось вставить его картинкой.

    Попробуем исправить ещё одну проблему. Как мы помним, основной алфавит это по сути старшие 6 бит, которые мы держим в уме, и приклеиваем к коду каждого очередного декодируемого символа. В случае с китайскими иероглифами, которые находятся в блоке 0x4E000x9FFF, это либо бит 0, либо 1. Это не очень удобно: нам нужно будет постоянно переключать алфавит между этими двумя значениями (т.е. тратить по три байта). Но заметим, что в длинном режиме из самого кода мы можем вычесть число символов, которое мы кодируем с помощью короткого режима (после всех вышеописанных хитростей это 10240) — тогда диапазон иероглифов сместится к 0x26000x77FF, и в этом случае на всём этом диапазоне старшие 6 бит (из 21) будут равны 0. Таким образом, последовательности иероглифов будут использовать по два байта на иероглиф (что оптимально для такого большого диапазона), не вызывая переключений алфавита.

    Альтернативные решения: SCSU, BOCU-1


    Знатоки Unicode, ещё только прочитав название статьи, скорее всего, поспешат напомнить, что непосредственно среди стандартов Юникода есть Standard Compression Scheme for Unicode (SCSU), который описывает способ кодирования, весьма сходный с описанным в статье.

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

    Что занятно, SCSU использует идеи, очень похожие на те, к которым я пришёл самостоятельно (вместо понятия «алфавитов» там используются «окна», и их доступно больше, чем у меня). В то же время, у этого формата тоже есть минусы: он чуть ближе к алгоритмам сжатия, нежели кодирования. В частности, стандарт даёт множество способов представления, но не говорит, как выбрать из них оптимальный — для этого энкодер должен применять какие-то эвристики. Таким образом, SCSU-энкодер, дающий хорошую упаковку, будет сложнее и более громоздок, чем мой алгоритм.

    Для сравнения я перенёс относительно простую реализацию SCSU на JavaScript — по объему кода она оказалась сравнима с моим UTF-C, но в ряде случаев показала результат на десятки процентов хуже (иногда она может и превосходить его, но ненамного). Например, тексты на иврите и греческом UTF-C закодировал аж на 60% лучше, чем SCSU (вероятно, из-за их компактных алфавитов).

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

    Возможные доработки


    Приведённый мной алгоритм не универсален by design (в этом, наверное, мои цели сильнее всего расходятся с целями консорциума Unicode). Я уже упомянул, что он разрабатывался преимущественно под одну задачу (хранение мультиязычного словаря в префиксном дереве), и некоторые его особенности могут плохо подходить для других задач. Но тот факт, что он не является стандартом, может быть и плюсом — вы можете легко доработать его под свои нужды.

    Например, очевидным образом можно избавиться от наличия состояния, сделать кодирование stateless — просто не обновлять переменные offs, auxOffs и is21Bit в энкодере и декодере. В таком случае не получится эффективно упаковывать последовательности символов одного алфавита, зато будет гарантия, что один и тот же символ всегда кодируется одними и теми же байтами, независимо от контекста.

    Кроме того, можно заточить кодировщик под конкретный язык, поменяв состояние по умолчанию — например, ориентируясь на русские тексты, выставить в начале энкодера и декодера offs = 0x0400 и auxOffs = 0. В особенности это имеет смысл именно в случае stateless режима. В целом это будет похоже на использование старой восьмибитной кодировки, только не лишает возможности вставлять символы из всего Юникода по необходимости.

    Ещё один недостаток, упомянутый ранее — в объемном тексте, закодированном в UTF-C, нет быстрого способа найти границу символа, ближайшего к произвольному байту. Отрезав от закодированного буфера последние, скажем, 100 байт, вы рискуете получить мусор, с которым ничего не сделать. На хранение многогигабайтных логов кодировка и не рассчитана, но в целом это можно поправить. Байт 0xBF никогда не должен встречаться в качестве первого байта (но может быть вторым или третьим). Поэтому при кодировании можно вставлять последовательность 0xBF 0xBF 0xBF каждые, скажем, 10 Кб — тогда при необходимости найти границу будет достаточно просканировать выбранный кусок до тех пор, пока не найдётся подобный маркер. Вслед за последним 0xBF гарантированно будет начало символа. (При декодировании эту последовательность из трёх байт, конечно, нужно будет игнорировать.)

    Подводя итог


    Если вы дочитали досюда — поздравляю! Надеюсь, вы, как и я, узнали что-то новое (или освежили в памяти старое) об устройстве Юникода.

    Демонтрационная страница. На примере иврита видны преимущества как перед UTF-8, так и перед SCSU.
    Демонтрационная страница. На примере иврита видны преимущества как перед UTF-8, так и перед SCSU.

    Не стоит рассматривать вышеописанные изыскания как посягательство на стандарты. Однако я в целом доволен результатами своих наработок, поэтому рад ими поделиться: например, JS-библиотека в минифицированном виде весит всего 1710 байт (и не имеет зависимостей, конечно). Как я упоминал выше, с её работой можно ознакомиться на демо-страничке (там же есть набор текстов, на которых её можно посравнивать с UTF-8 и SCSU).

    Напоследок ещё раз обращу внимание на кейсы, в которых использовать UTF-C не стоит:

    • Если ваши строки достаточно длинные (от 100-200 символов). В таком случае стоит задуматься о применении алгоритмов сжатия вроде deflate.
    • Если вам необходима ASCII transparency, то есть вам важно, чтобы в закодированных последовательностях не возникали ASCII-коды, которых не было в исходной строке. Потребности в этом можно избежать, если при взаимодействии со сторонними API (например, работая с БД) вы будете передавать результат кодирования как абстрактный набор байт, а не как строки. В противном случае вы рискуете получить непредвиденные уязвимости.
    • Если вы хотите иметь возможность быстро находить границы символов по произвольному смещению (например, при повреждении части строки). Это можно делать, но только просканировав строку от начала (или применив доработку, описанную в предыдущем разделе).
    • Если вам нужно быстро делать операции над содержимым строк (сортировать их, искать в них подстроки, конкатенировать). Для этого строки требуется сначала декодировать, поэтому UTF-C будет медленнее UTF-8 в этих случаях (но быстрее алгоритмов сжатия). Поскольку одна и та же строка всегда кодируется одинаково, точное сравнение декодирования не требует, его можно производить побайтово.


    Update: пользователь tyomitch в комментариях ниже выложил график, подчёркивающий границу применимости UTF-C. На нём видно, что UTF-C эффективнее алгоритма сжатия общего назначения (вариации LZW) до тех пор, пока упаковываемая строка короче ~140 символов (правда, отмечу, что сравнение проводилось на одном тексте; для других языков результат может отличаться).
    Сравнение UTF-C и LZW

    Средняя зарплата в IT

    111 111 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 6 720 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

      +3
      Ну то есть самая очевидная проблема не решена: если строка к нам попала не сначала, то мы никак не сможем понять перед нами начало мультибайтовой последовательности или её середина.
      И подобрав особую последовательность, сможем убирая один байтик вначале вкорне изменить интерпретацию последующих символов. Не?
        +2

        Да, это верно как для SCSU, так и для моей UTF-C.


        Но в моей задаче (и кажется, во многих практических задачах тоже) такая проблема не может возникнуть, так что у меня не стояло цели её решать. Цель была только в компактности.

          –5

          Тогда кодируйте KOI8-R, CP-1251 и т.д.

            +6
            Основной вопрос в алфавите. В KOI8-R и аналоги весь юникод не засунешь.
          +1
          А не надо байтики откусывать :) надо символы откусывать. Плюс правда придётся тянуть state вместе с byte-offset, но это некритично. Основной минус — нельзя строку отгрызть с конца, а такой use case типа «оканчивается на xyz» попадается довольно часто.

          P.S: Автору UTF-C — мегареспект! :)
            0
            Не надо байтики откусывать…
            Вот только протоколы передачи данных откусить биты не могут, байты могут легко, а о ваших символах вообще представления не имеют.
              +3

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


              (Да и не для того это делалось же, чтобы эти строчки куда-то в сеть передавать)

                +1
                Речь о том, почему в utf-8 так сделано. Понятно что у вас совсем другая задача и универсальность utf-8 — избыточна.
                  0
                  (Да и не для того это делалось же, чтобы эти строчки куда-то в сеть передавать)

                  Просто буква T в названии UTF-C вводит в заблуждение.
                    0
                    Добавлю, что название UCF (Unicode Compression Format) куда вернее соответствовало бы сути формата, чем UTF-C.
                    0

                    Ну вот вам задача. Многогигабайтный текстовый документ. Пользователь тыкает в скроллбар.


                    Задача просмотрщика текста: Переместиться примерно в примерно нужное место файла, найти ближайший символ, попробовать найти после (или до) него ближайший перенос строки, начать рендеринг оттуда.

                      0
                      Ctrl-F «0xBF 0xBF 0xBF»
                +1

                Учитывая, что большинство строк имеет смысл хранить именно как строки (причём immutable), а не как буфер с байтами – не великая проблема.

                +1
                Если речь не идет о китайской раскладке и обычном тексте с редкими включениями утф-символов, вполне себе годны html entities и однобайтовая кодировка для хранения в БД.
                Из минусов — при хранении в БД приходится решать вопрос поиска по БД слов с этими entities.
                Из плюсов — ощутимое изменение размера БД и производительности.
                В свое время меряли объемы и скорость — habr.com/en/post/116822 — соотношения до сих пор актуальны, на sphinx и прочих БД так же сохраняются. Хотя казалось бы создатели БД могли бы уже озаботится вопросом более компактного внутреннего хранения utf-8 и работы с ним.
                  +3

                  Видимо, под «обычным текстом» подразумевается текст преимущественно на каком-то одном языке, чтобы под него можно было выбрать удобную однобайтовую кодировку?)


                  Мне вот хотелось уметь хорошо хранить строчки, язык которых заранее неизвестен.


                  Кстати, Википедия говорит, что вот SQL Server 2008 R2 как раз SCSU внутри себя использует, чтобы компактно строчки хранить.

                    0
                    Видимо, под «обычным текстом» подразумевается текст преимущественно на каком-то одном языке, чтобы под него можно было выбрать удобную однобайтовую кодировку?)
                    В целом да, но чуть шире.
                    windows-1252 позволяет охватить практически все европейские языки.
                    windows-1251 закрывает почти все кириллические языки.

                    Мне вот хотелось уметь хорошо хранить строчки, язык которых заранее неизвестен.
                    Если их немного, то как вариант можно хранить пометку «исключение» с хранением исходного текста в дополнительной таблице, при этом в основной хранить приведенный текст.
                    Тогда и поиск нормально получается и исходный текст присутствует. Такой подход может оправдывать себя если текстов в не основных кодировках не больше примерно 20%.

                    p.s.: Но вообще да, в современных реалиях нередко проще задавить этот вопрос сервером подороже:)
                      +2
                      Если их немного, то как вариант можно хранить пометку «исключение» с хранением исходного текста в дополнительной таблице, при этом в основной хранить приведенный текст.
                      Мне кажется, мы с вами всё-таки немного про разные категории задач говорим. Вы больше про конкретный продукт, который кладёт тексты в какую-то базу, а я писал движок, который сам по себе «база данных» в некотором смысле, и у него нет знаний об используемом языке. И когда нужно что-то искать в массиве пожатых строк, это достаточно недорого делается вызовом функции декодирования для каждой.
                        0
                        Если крайне упрощенно, то мы говорим о том, что вместо универсального ужатия (которое в случае отсутствия необходимости в поиске и т.д. неплохо делается тем же gzencode допустим)… есть смысл выбирать кодировку индивидуально для каждой единицы информации (где единица информации — статья, пост, коммент) и/или редкие исключения кодировать просто в html entities при этом используя опять же однобайтовую кодировку, т.к. с хорошим шансом она индивидуальная подобранная однобайтовая кодировка + исключения в види ентитес будут эффективнее.
                          +1
                          Но ведь по сути это и будет тем, что описано в статье. Грубо говоря, первый байт определяет кодировку и дальше тратится по одному байту на символ. Исключения, соответственно, кодируются 2-3 байтами (вместо 7 байт на html entities).
                            0
                            У Вас получается более гибкий подход — он лучше с точки зрения совмещения нескольких языков в одной единице информации, допустим немецкий, китайский, арабский, русский и иврит в одном комменте. Но обмен Вы отдали даже шанс на понимание Вашей кодировки чем-то, что с ней не знакомо и работает только с привычными стандартами.
                            И при этом нам не вполне понятно, чем Ваш подход лучше gzencode, т.к. Вам всё равно придется раскодировать строку перед работой с ней или перед выдачей ее юзеру, а gzencode на более или менее длинных текстах ужимает больше чем в 2 раза. При этом если Вам надо держать в памяти миллион коротких строк по 10 символов — почему бы не заменить это на 10 тысяч строк по 1000 символов, по принципу зип архива — если уж на то пошло?

                            Мы же исходим из того, что хотя в целом тексты могут быть на разных языках, но в одной единице информации как правило один язык, поэтому гибкостью можно пожертвовать и указывать кодировку для всей единицы информации, кодируя исключения в entities. В обмен получаем использование стандартной общепризнанной кодировки с которой умеет работать «код с улицы», облегчается поиск и вообще всё.
                              +1
                              Но обмен Вы отдали даже шанс на понимание Вашей кодировки чем-то, что с ней не знакомо и работает только с привычными стандартами.

                              Как я уже писал, речь про использование этой кодировки в своём коде. Всё взаимодействие с ней обёрнуто в функции Encode/Decode, которые на выходе/входе дают массив байт. Если нужно что-то с содержимым сделать — декодируем (обычно это нужно только в момент ввода или вывода), а если передать чему-то стороннему (или сбросить на диск, например) — передаём просто как байты.

                              При этом если Вам надо держать в памяти миллион коротких строк по 10 символов — почему бы не заменить это на 10 тысяч строк по 1000 символов, по принципу зип архива — если уж на то пошло?
                              Но «держать миллион строк по 10 символов» это же вводная, как её можно поменять на другую? :) Вот представьте, у нас смешанный словарь, содержащий слова разных языков мира. Или, например, список заголовков статей всех Википедий. Как вы их склеите так, чтобы иметь доступ за O(1) к каждому заголовку по его индексу?
                                0
                                Но «держать миллион строк по 10 символов» это же вводная, как её можно поменять на другую? :)
                                Это не вводная, это решение задачи хранения миллиона строк по 10 символов:)
                                Вот представьте, у нас смешанный словарь, содержащий слова разных языков мира. Или, например, список заголовков статей всех Википедий. Как вы их склеите так, чтобы иметь доступ за O(1) к каждому заголовку по его индексу?
                                Так мы же написали — «по принципу зип архива». Вам же не надо разахривировать весь архив, что бы вытащить один файл по его имени? А словарь общий, поэтому оверхеда на каждую конкретную строчку нет, только общий оверхед.
                                Если говорить применительно к БД (дада, мы помним что у Вас свой софт:)), то в innodb есть compressed формат — правда его техническую реализацию не помним, но если опять же это вариант с общим словарем — то даже придумывать ничего не надо.
                                В конце концов можно сделать виртуальный сжатый диск и кинуть базу (в любом виде) тупо на него.
                                  +1
                                  То есть вы предлагаете группировать слова из словаря по 100 штук в строки, далее эти строки сжимать и раскидывать по дереву поиска? Тогда для поиска нужного слова можно будет найти строку, его содержащую, за O(1), но затем нужно всю эту строку расшифровать, и далее внутри неё искать нужное слово уже последовательным поиском.

                                  Ну ладно, допустим, затраты на расшифровку строки из 100 слов вместо расшифровки одного слова, и затраты на последовательный поиск одного слова из ста не так уж велики по сравнению с поиском нужной строки в дереве, если словарь очень большой. Но возникает ещё другая проблема: если добавляются новые слова, то куда вставлять их в дерево? Отдельным узлом? Или всё таки внутрь строки к другим 100 словам? И то же самое при изменении слов, когда они должны перейти на новое место. В первом случае (если новые слова добавляются отдельными узлами) при частых изменениях скопится больше коротких строк, чем длинных, и эффективность алгоритма сжатия быстро упадёт. А во втором случае (при добавлении новых слов к существующим) при частых изменениях будут скапливаться очень длинные строки, что будет увеличивать время последовательного поиска в них (и время на вставку тоже возрастёт). Можно, конечно, при достижении определённого размера делить строку на две (например, при добавлении 150-го по счёту слова делить строку на две по 75 слов). Но в целом это всё выглядит как более сложное и нагромождённое решение, чем предлагаемое автором статьи, и в любом случае менее эффективное по времени работы. А преимуществ не даёт никаких, кроме «понимания кодировки чем-то, что с ней не знакомо», что в данной задаче про хранение словаря вообще не требуется.
                          0
                          И когда нужно что-то искать в массиве пожатых строк, это достаточно недорого делается вызовом функции декодирования для каждой.

                          И это третий существенный недостаток по сравнению с UTF-8, кроме уже упомянутых ASCII-непрозрачности и неопределимых границ символов.
                            0
                            Я не совсем понимаю, какой вывод из этого нужно сделать.

                            Обо всех этих недостатках я упомянул в теле статьи, о преимуществах тоже. Их существенность зависит от контекста: очевидно, что в одних классах задач встают одни требования, в других — другие. Поэтому в одном случае эффективнее одно решение, а в другом — другое.

                            Отдельно замечу, что во многих ситуациях UTF-8 точно так же требует кодирования/декодирования, как и мой подход. Но в отличие от, например, алгоритмов сжатия (у которых тоже своя область применимости) тут довольно простая логика, это не так затратно.
                              0
                              Обо всех этих недостатках я упомянул в теле статьи, о преимуществах тоже.

                              Если и так, то поиск был упомянут где-то в самом начале, и к концу статьи уже забылся :)
                              Не хватает именно что подведения итогов: «преимущества моей кодировки — а, б и в; недостатки — х, у и з

                              Отдельно замечу, что во многих ситуациях UTF-8 точно так же требует кодирования/декодирования, как и мой подход.

                              В каких именно? (Это тоже стоило упомянуть в статье.)
                                +1
                                Зато в самом начале есть дисклеймер, где выделена ключевая мысль :)

                                Дисклеймер. Сразу сделаю несколько важных оговорок: описанное решение не предлагается как универсальная замена UTF-8, оно подходит только в узком списке случаев (о них ниже)
                                  0
                                  Да, но как читатель статьи должен определить, подходит ему ваша кодировка или нет?
                                    +1
                                    Прочитать статью, обращая внимание на каждый упомянутый недостаток? По правде сказать, мне казалось, предостережений я в тексте оставил порядочно :)
                                      0
                                      Сортировка, проверка равенства, и конкатенация — точно не были упомянуты, я специально перепроверил.
                                        +1
                                        Дополнил финальный раздел. Надеюсь, теперь точно недопониманий не возникнет :)
                                          0
                                          Большое спасибо! (Правда, «возможность быстро находить границы символов» упомянута дважды.)
                                          А можете добавить ещё и вторую половину итога — «кейсы, в которых использовать UTF-C стоит»?
                                            +1
                                            Сортировка, «равенство» и т.п. часто бывают case-insensitive, т.е. даже в utf-8 со строкой как с массивом байт просто так не поработаешь.
                                              +1
                                              Как я объяснил в комментарии ниже, UTF-8 обеспечивает удобную работу со строкой как с массивом codepoints, потому что это единственная возможная интерпретация строки на неизвестном языке или на смеси разных языков.
                                              Если же нужны приведение регистров и «естественная сортировка», то неизбежно придётся привязываться к какому-то конкретному языку — и в этом случае 8-битная кодировка обеспечит ещё большее удобство.
                    –6
                    В чём смысл этой разработки? Если для экономии места при хранении текста, то с этим сейчас проблем нет вообще, терабайты почти в каждом компьютере. Если для уменьшения трафика — на нынешних скоростях и безлимитах даже на мобильный интернет ваш подвиг никто не заметит, тем более что сам html, скрипты, картинки и реклама (особенно анимированная или вообще видео) отъедают процентов 90...98 трафика по сравнению с полезным текстом. Если для ускорения работы программ с текстом за счёт мЕньшего объёма считываемых данных — то она, наоборот, замедлится, т.к. надо или в каждом проходе парсить текст с самого начала, потому что нет разделителей символов, или распаковывать его в тот же UTF-16. Передача служебной информации всякими датчиками — есть 7-битный GSM формат для латиницы и 8-битный для кириллицы, а эмодзи и заморские языки таким датчикам не нужны… Для чего тогда?
                      0
                      В этом случае однозначно UTF-32. deflate сделает всё остальное на трафике.
                        +12
                        В моей статье есть целый раздел, озаглавленный словами «Зачем же выдумывать что-то новое?». Мне несколько обидно, что вы не уделили ему внимания.

                        Смысл разработки в экономии места в случаях, когда алгоритмы сжатия общего назначения неэффективны. Например, если вам нужно держать миллион коротких (10-20 символов) строк в памяти. В таких случаях алгоритмы вроде deflate дадут больше оверхеда, чем пользы.
                        +2
                        что закодированная с помощью UTF-C строка не обеспечивает ASCII transparency
                        Ну тогда попробуйте провести сравнение ваших результатов с результатами полученными алгоритмами сжатия, для более-менее длинных текстов. Можно даже и для коротких, если мы предположим что у нас есть универсальные словари комперссии для специфичных языков.

                        Использование правильной кодировки упрощает некоторые алгоритмы, например сортировку. В вашем случае получается что надо перекодировать всё и потом сортировать, либо налету туда-сюда гонять.
                          0
                          Ну тогда попробуйте провести сравнение ваших результатов с результатами полученными алгоритмами сжатия, для более-менее длинных текстов. Можно даже и для коротких, если мы предположим что у нас есть универсальные словари комперссии для специфичных языков.

                          Но зачем? Основная область применения UTF-C — именно короткие тексты, когда алгоритмы сжатия не работают.
                            0
                            Но зачем? Основная область применения UTF-C — именно короткие тексты
                            Я с вашего демо взял пример, у вас там сравнение 674 байт против 379 байт в вашей кодировке. Я просто gzip попробовал, получилось 315 байт, т.е. выгоднее.

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

                            Если будут универсальные словари для языков, то по идее можно ими пользоваться, т.е. не тянуть с собой конкретный словарь, а просто давать ссылку на словарь в нашей библиотеке, типа первый байт это ссылка на словарь. Конечно потеряется эффективность, но для типичных случаев, не на сильно много.

                            Опять же, можно попробовать как данные в вашем формате жмутся, тоже интересно.
                              +1
                              Я с вашего демо взял пример, у вас там сравнение 674 байт против 379 байт в вашей кодировке
                              Там всё-таки достаточно длинные примеры, просто для наглядности. На строках длиной менее ~100 символов gzip начинает давать текст даже длиннее, чем UTF-8 (и не забываем ещё про тот факт, что процесс сжатия всё-таки более затратный, чем кодирование — которое делается в один проход, с небольшим числом операций на каждый символ).

                              Но вы правы, возможно будет ещё интересно для понимания сделать, например, графики, где будет видно, на каких объемах какой подход работает лучше.

                              ASCII transparency это основное преимущество, если его нету то пусть будет просто компрессия, она сможет на типичных данных в разы преимущество давать.
                              Да, в каких-то областях применений это разумеется так. Но, например, когда речь про то, чтобы держать массив строк в памяти своего приложения ASCII transparency не требуется (хорошая компрессия требуется, но, повторюсь, надо смотреть на типичную длину строк).
                                0
                                и не забываем ещё про тот факт, что процесс сжатия всё-таки более затратный, чем кодирование

                                Есть вещи типа github.com/google/snappy

                                Просто базируясь на вашем названнии (UTF-C), я преполагаю что вы хотели бы предложить это в качестве стандарта в каком-то виде. Для этого как раз неудобные вопросы очень помогают, может переосмыслив некоторые вводные, вам удасться сделать удачный формат который может не выжмет последний байт эффективности, но решит проблемы про которые вас спрашивают в комментариях.

                                  +2
                                  Есть вещи типа github.com/google/snappy
                                  For instance, compared to the fastest mode of zlib, Snappy is an order of magnitude faster for most inputs, but the resulting compressed files are anywhere from 20% to 100% bigger.
                                  Ну то есть тоже trade-off какой-то присутствует. Тоже было бы любопытно сравнить (я не утверждаю, что любое сжатие медленнее кодирования на нескольких ифах, но кажется, что второе заоптимизировать можно гораздо лучше, чем первое).

                                  Просто базируясь на вашем названнии (UTF-C), я преполагаю что вы хотели бы предложить это в качестве стандарта в каком-то виде.
                                  Ни в коем случае! Название это просто отсылка к UTF-8, на котором я построил свой подход (ну и мне показалась забавной созвучность USB-C, если честно :)

                                  Напротив: я написал код (и статью) так, чтобы его можно было не только импортировать в свой проект по надобности, а скопировать и поменять под свои нужды. Я об этом говорю в разделе «Возможные доработки»: я считаю, что когда речь идёт о внутренних частях своего проекта, то иногда полезно не только стремиться к стандартизации (помним картинку про competing standards от xkcd), но и к кастомизации под конкретную задачу.
                                    0
                                    Насколько я понимаю, Snappy работает так же, как Lz4 — заменяет повторяющиеся данные ссылками на предыдущие вхождения. В вашем случае очень сомневаюсь, что он даст хоть какое-то преимущество, так как от произвольного набора коротких слов вряд ли стоит ожидать большого количества повторений (кроме префиксов, но ваши строки и так в префиксном дереве)
                                  +2
                                  Но вы правы, возможно будет ещё интересно для понимания сделать, например, графики, где будет видно, на каких объемах какой подход работает лучше.

                                  Как-то так:



                                  Для сравнения использованы pieroxy.net/blog/pages/lz-string/index.html и
                                  абзац текста из википедии
                                  Early names of Tyre include Akkadian Ṣurru, Phoenician Ṣūr (вырезано движком хабра), and Hebrew Tzór (צוֹר‎). In Semitic languages, the name of the city means «rock» after the rocky formation on which the town was originally built. The official name in modern Arabic is Ṣūr (صور‎) meaning «wall» or «enclosure.»

                                  The predominant form in Classical Greek was Týros (Τύρος), which was first seen in the works of Herodotus but may have been adopted considerably earlier. It gave rise to Latin Tyrus, which entered English during the Middle English period as Tyre. The demonym for Tyre is Tyrian, and the inhabitants are Tyrians.
                                    +1
                                    О, спасибо. Если вы не против, я бы добавил этот график в статью, чтобы было наглядно видно, на каких длинах строк мой подход предпочтительнее.
                                      0
                                      На здоровье!
                                      Я бы и для демо-страницы прислал PR с поддержкой LZ, если бы репозиторий был публичным.
                                +2
                                Так работают же. Ваша ad-hoc схема с алфавитами — это почти то же самое, что делает алгоритм Хаффмана, только сжатие на основе алгоритма Хаффмана ещё и уложит это в биты, а не в байты.

                                У вас была неправильная предпосылка («короткие тексты не сжимаются») и на основании её вы сделали неправильный вывод.
                                  +1
                                  Да, уложит, но Хаффман не может «из воздуха» получить информацию о том, какой символ кодировать коротким кодом, а какой — подлиннее. Либо мы на каждую строчку дополнительно держим частоты символов (т.е. добавляем оверхед), либо строим какой-то отдельный глобальный словарь (но если мы хотим чтобы любая строка всегда кодировалась одним и тем же образом, он должен быть заранее зафиксирован). Такой «зашитый» в алгоритм частотный словарь — да, тоже приемлемая альтернатива, но мне показалась излишне сложной (и не факт, что стоящей того на практике).
                                    0
                                    Только вот кодировать с preset dictionary — стандартное АПИ для кучи либ архивации и гораздо проще, чем делать велосипед.

                                    deflateSetDictionary() / inflateSetDictionary() в zlib.

                                    или

                                    SDCH achieves its effectiveness by using pre-negotiated dictionaries to «warm up» its internal state prior to encoding or decoding. These may either be already stored locally, or uploaded from a source and then cached.
                                      +1
                                      Значит, понимание того, что «гораздо проще» у нас с вами несколько разное.

                                      Для меня, повторюсь, вариант тащить полноценную либу, осваивать её апи, готовить для неё какие-то данные (в надежде, что они будут репрезентативными для любого будущего датасета), и потом потенциально страдать от недостаточной производительности — не ощущался проще, чем написать две функции на 100 строчек кода. И что самое важное, это точно не ощущалось интереснее :)

                                      В то же время я совершенно не спорю, что кому-то другому может показаться иначе (и это нормально). Хорошо же, что у нас всех есть свобода выбирать, какими решениями пользоваться, и какие велосипеды писать :)
                                        +1
                                        Мне кажется, в этой задаче setDictionary не поможет: он устанавливает начальное значение для sliding window (в котором deflate ищет повторяющиеся последовательности байт); этот метод эффективен для сильно повторяющихся данных. В случае набора коротких слов на разных языках, как мне кажется, основное сжатие в deflate обеспечивается кодировкой Хаффмана, которая от setDictionary не зависит.
                                        В данной задаче могло бы помочь создание специализированных fixed huffman codes для каждого языка, и переключение между ними (стандартный блок deflate compression with fixed huffman codes, скорее всего, не будет самым эффективным), но это решение в любом случае будет сложнее, чем приведенное автором.
                                  0
                                  Использование правильной кодировки упрощает некоторые алгоритмы, например сортировку. В вашем случае получается что надо перекодировать всё и потом сортировать, либо налету туда-сюда гонять.

                                  И это четвёртый существенный недостаток UTF-C по сравнению с UTF-8.
                                  Не только сортировать, но и проверять равенство строк невозможно без перекодировки.
                                    0
                                    Извините, но кажется отмеченный вами четвёртый недостаток полностью совпадает с третьим :)

                                    Отмечу, что поскольку одна и та же строка кодируется одним и тем же способом, точное сравнение вполне допустимо делать побайтово, без декодирования. А для сравнения при сортировки сложность декодирования сравнима со сложностью декодирования UTF-8 (принципы у них одинаковые).

                                    Честно говоря, у меня складывается ощущение, что вы хотите просто сказать, что я сделал плохую и бесполезную (по вашему мнению) вещь. Для меня это несколько неприятно, но я готов принять и такое мнение.
                                      0
                                      Извините, но кажется отмеченный вами четвёртый недостаток полностью совпадает с третьим :)

                                      Не соглашусь: поиск затруднён тем, что вхождение подстроки байт не гарантирует вхождение подстроки символов. Со сравнением строк это не связано.

                                      Отмечу, что поскольку одна и та же строка кодируется одним и тем же способом, точное сравнение вполне допустимо делать побайтово, без декодирования.

                                      Если так, тогда конкатенация строк требует перекодировки.

                                      А для сравнения при сортировки сложность декодирования сравнима со сложностью декодирования UTF-8 (принципы у них одинаковые).

                                      Строки в UTF-8 можно сортировать без декодирования, в этом и фишка.
                                        +1
                                        Не соглашусь: поиск затруднён тем, что вхождение подстроки байт не гарантирует вхождение подстроки символов. Со сравнением строк это не связано.

                                        Когда вы отмечали третий недостаток, вы цитировали моё сообщение:
                                        И когда нужно что-то искать в массиве пожатых строк, это достаточно недорого делается вызовом функции декодирования для каждой.

                                        Наверное, я неточно сформулировал ту фразу, но речь там шла не про подстроки, а именно про бинпоиск нужной строки (что требует таких же сравнений, как при сортировке).

                                        Если так, тогда конкатенация строк требует перекодировки.
                                        Да, это так. Все мутирующие операции тут требуют декодирования.

                                        Строки в UTF-8 можно сортировать без декодирования, в этом и фишка.
                                        Скажем так, это спорный момент.

                                        Сортировать без декодирования так-то можно что угодно (и тем же бинпоиском искать потом). Сортировка прямо в UTF-8 гарантирует только то, что строки будут посортированы по порядковым кодам символов, а это неидеально: например, хорошо бы, чтобы сравнение шло без учёта регистра (чтобы буквы, отличающиеся только регистром, стояли рядом, а в Юникоде это почти никогда не так). Западноевропейские символы из Latin-1 Supplement и вовсе оторваны от родственных им аналогов без диакритики (как и русская «ё» от «е»). Так что если цель сортировать естественным образом, то декодировать нужно в любом случае, а потом применять Unicode collation algorithm.
                                          +1
                                          Наверное, я неточно сформулировал ту фразу, но речь там шла не про подстроки, а именно про бинпоиск нужной строки (что требует таких же сравнений, как при сортировке).

                                          Да, у выражения «поиск в строках» два разных значения, но оба они требуют перекодировки :-)

                                          чтобы буквы, отличающиеся только регистром, стояли рядом

                                          Канонический пример: i и I должны сортироваться как одна буква или как разные?
                                          У тюрков на этот счёт иное мнение, чем у других народов.

                                          Так что если цель сортировать естественным образом

                                          То нужно знать конкретный язык текста: например, в польском словаре chata идёт перед cukry, а в чешском — наоборот. В немецком словаре Öl идёт перед Sand, а в шведском — наоборот. Если же в массиве строк есть и чешские, и польские, и немецкие, и шведские, (а то ещё и турецкие,) то «естественный порядок» не определён, и единственный порядок, имеющий смысл при сортировке такого массива — это порядок по codepoints, что UTF-8 и обеспечивает.
                                            +1
                                            То нужно знать конкретный язык текста
                                            Да, неплохо бы это делать с учётом языка, не спорю (и никто не мешает дополнительно и эту информацию хранить и использовать при сортировке, как это делается в MySQL, к примеру).

                                            Но ещё я отмечу, что Юникод всё-таки определяет и некий базовый порядок сортировки символов (DUCET) и даже без уточнения под конкретный язык он даст более адекватную в большинстве случаев сортировку, нежели предлагаемую вами сортировку по кодовым точкам.

                                            Главный мой поинт остаётся в силе — если мы хотим естественный порядок, нам нужно декодировать строки (да, хорошо бы при этом знать язык).

                                            Если же в массиве строк есть и чешские, и польские, и немецкие, и шведские, (а то ещё и турецкие,) то «естественный порядок» не определён, и единственный порядок, имеющий смысл при сортировке такого массива — это порядок по codepoints, что UTF-8 и обеспечивает.
                                            Окей, я понял, что ваша цель не в естественном порядке. Но тогда я вообще не очень понимаю, что вы называете смыслом данного порядка, какая практическая задача этим решается?

                                            Вот цитата непосредственно из документа Unicode Collation Algorithm:
                                            The basic principle to remember is: The position of characters in the Unicode code charts does not specify their sort order.

                                            Так что мне кажется, сортировка по кодовым точкам не особо лучше любой другой детерменированной сортировки (как, например, по байтам в закодированном виде).
                                              +1
                                              Так что мне кажется, сортировка по кодовым точкам не особо лучше любой другой детерменированной сортировки (как, например, по байтам в закодированном виде).

                                              Для обработки внутри приложения — наверное да.
                                              При работе со внешними данными — удобно, когда я и вторая сторона используем один и тот же порядок сортировки, независимо от того, какой UTF с каждой стороны.
                                      0
                                      Только вот сортировать все равно придется каким-нибудь Unicode collation algorithm, а не просто сравнивать строки побайтно.
                                        0
                                        Побайтное сравнение в UTF-8 даёт корректный порядок по codepoints.
                                          0
                                          Окей, никто не спорит. Ну если только нормализированные формы не учитывать.

                                          Вот только во многих приложениях побайтного сравнения недостаточно и нужно сравнивать ключи сотрировки, которые можно сравнивать побайтно
                                            0
                                            dup
                                      –2
                                      Как только вы вводите состояние енкодера/декодера, то куда уж проще сделать специальную последовательность бит (например, 0xFF), за которой идет индекс 255-символьной страницы, а далее все символы адресуются байтами со смещением внутри этой страницы пока не встретится переключение на новую страницу. Если текст не состоит из чередующихся символов разных алфавитов, то выигрыш будет практически на уровне старых однобайтных кодировок.

                                      Так что поздравляю вас с изобретением велосипеда )
                                        +1
                                        Описанный вами подход выглядит очень похоже на описанный в статье, только вместо целого байта 0xFF в качестве маркера я трачу 1-3 бита. Да, чуть проще — чуть менее эффективно.

                                        Так что поздравляю вас с изобретением велосипеда )
                                        Спасибо, я старался!
                                          +1
                                          Если текст не состоит из чередующихся символов разных алфавитов, то выигрыш будет практически на уровне старых однобайтных кодировок.

                                          Почти в любом тексте очень часто встречаются пунктуация, пробелы и переводы строк из диапазона U+00xx.
                                          +1

                                          У вас терминал текст RTL-языках отображает слева направо — и с ивритом такое, и с арабским.
                                          Например, арабский текст должен отображаться как الأخبار — тут в отличие от терминала видно, что буквы имеют не только другое направление, но и другой вид (зависит от положения буквы в слове), и лигатуру лям-алиф (похожа на букву ꙋ)
                                          Арабский текст


                                          Впрочем, в моём GNOME Terminal — та же фигня.

                                            +1
                                            Это терминалы, они такие, да. Если программа будет по буковке выводить RTL-текст, как прикажете это рендерить? Визуально сдвигать уже выведенный текст? Люди такого от терминалов не ожидают.
                                              0
                                              Есть вообще хоть один терминал, поддерживающий арабицу?
                                              Стандартный в Windows — тоже нет.
                                              0
                                              Если строчка содержит текст на одном из современных языков (включая китайский), за пределы этой плоскости вы не выйдете.

                                              Выйду же: en.wikipedia.org/wiki/CJK_Unified_Ideographs
                                              20989 символов в BMP, и ещё 71867 вне неё.
                                                +1
                                                Вне BMP всё-таки только очень редко используемые иероглифы. Я, например, наугад открыл несколько статей в китайской Википедии, и не нашёл в них ни одного символа с кодом больше 0xFFFF.

                                                Так же как, например, у кириллицы есть несколько дополнительных блоков кроме 0x0400 —0x04FF, но на практике мы с ними практически не сталкиваемся.
                                                –6
                                                Зачем это всё? Имею ввиду юникод и авторские штуки.
                                                8бит всем хватает на кодировку и всегда хватало, там где это нужно — переключайте кодировки.
                                                Это самый эффективный способ сэкономить на байтах. Других нет.

                                                п.с.: Юникод нужен, но он нужен там, где он нужен. В 99% случаев он не нужен вообще. По сути, юникод — это избыточный крутой фреймворк, однако же подавляюще часто вы пользуетесь им на 1%, не более, а тогда зачем он вам?
                                                  +3

                                                  Как минимум, Юникод хорош тем, что это один общий стандарт, который сейчас уже более-менее всё поддерживает. Если вам нужно обозначить какой-то символ — в юникоде точно найдётся его код.


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


                                                  Ей-богу, риторика в духе «8 бит хватит всем» мне кажется очень странной.

                                                    +4
                                                    8бит всем хватает на кодировку и всегда хватало,

                                                    Восточноазиатам — не хватает и никогда не хватало. Сколько их, четверть населения планеты?

                                                    там где это нужно — переключайте кодировки.

                                                    Забыли те времена, когда емейл на русском ходил в четырёх разных кодировках, и для просмотра каждого письма приходилось её переключать?
                                                      0
                                                      Я даже перепроверил из какого года эта статья, уж больно странный коммент…
                                                      +1

                                                      Гуглеж "short string compression" выдает довольно много проектов, и даже научных статей. Сравнивали с чем-нибудь из этого?

                                                        0
                                                        Те варианты, что я видел, были заточены в первую очередь под английский язык (возможно, что-то упустил — смотрел довольно поверхностно). Впрочем, я даже о существовании SCSU не сразу узнал :)
                                                        +1
                                                        Кодировки текстов на естественных языках преследуют какую-то определённую цель. Обычно это либо хранение (и тут применяются алгоритмы сжатия), либо обработка. Для обработки (как в вашем случае) выбор зависит от алфавитов, с которыми нужно работать, от требуемых свойств (возможность поиска по подстроке, индексирование по символам и т.п.).

                                                        Ваша реализация находится где-то посередине между хранением и обработкой. Она будет не так компактна, как алгоритмы сжатия, и не так приспособлена к обработке текста, как UTF-8, UTF-16, либо национальные ANSI-кодировки (при работе с конкретным языком). Пожалуй, в той конкретной задаче, в которой вы её применяете, она даёт лучший результат.

                                                        Когда мне приходилось обрабатывать тексты на современных славянских языках, при этом требовался быстрый поиск по подстрокам, вырезания/слияния, индексный поиск по отдельным символам, разбиение на предложения и слова и т.п., я просто взял Windows 1251 и в символы ниже кода 32 внедрил недостающие буквы из польского и чешского алфавитов. Получилось очень компактное представление, удовлетворяющее всем вышеуказанным требованиям.
                                                          +1
                                                          Для обработки (как в вашем случае)
                                                          Не могу сказать, что в моём случае это так. Как раз-таки содержимое строк мне трогать не нужно (не требуются никакие изменения строк, поиск подстрок и тому подобное), они абсолютно статичны.

                                                          Кажется, это всё-таки чистая задача хранения строк, но при условии их малой длины (что мешает использовать алгоритмы сжатия).
                                                          0
                                                          Кириллице и ещё пяти алфавитам — ура — повезло, 2 байта на символ.

                                                          Какие еще 5 алфавитов составляют компанию Кириллице в числе везунчиков?
                                                            +1
                                                            Greek and Coptic (0370–03FF)
                                                            Cyrillic (0400–04FF)
                                                            Cyrillic Supplement (0500–052F)
                                                            Armenian (0530–058F)
                                                            Hebrew (0590–05FF)
                                                            Arabic (0600–06FF)
                                                            Syriac (0700–074F)
                                                            Arabic Supplement (0750–077F)
                                                            Thaana (0780–07BF)
                                                            N'Ko (07C0–07FF)
                                                              +1
                                                              Ошибся, семь: греческий (U+0370..U+03FF), армянский (коды U+0530..U+058F), иврит (U+0590..U+05FF), арабский (два блока, U+0600..U+06FF и U+0750..U+077F), сирийский (U+0700..U+074F), тана (мальдивский язык, U+0780..U+07BF) и н'ко, использующийся в языках манде в Западной Африке (U+07C0..U+07FF).
                                                              0
                                                              Например, первый байт в UTF-8 всегда начинается либо с 0, либо с 11 — а префикс 10 есть только у следующих байт. Заменим префикс 11 на 1, а у следующих байт уберём префиксы совсем. Что получится?

                                                              А получится снижение устойчивости кода к ошибкам. Применяемая в UTF-8 система префиксов при потере/искажении любого байта приводит к потере/искажению только одного символа. Кроме того, UTF-8 «заточен» на потоковую передачу текста. Прием можно начинать с любого байта — декодер сам определит начало следующего символа.

                                                              В предлагаемой же системе префиксов такой возможности нет. Искажение или потеря любого байта может привести к полной нечитаемости остальной части текста.
                                                                +1

                                                                Абсолютно верно, и об этом сказано в самой статье.


                                                                Если в вашей задаче важно, чтобы при повреждении строк сохранялась целостность последующего за ними текста — используйте UTF-8. Это ведь нормально — подбирать решение под задачу.


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

                                                                0
                                                                Я тоже как то задумывался над этой темой. Почему UTF-8 именно такой какой есть.

                                                                UTF-C:
                                                                0xxxxxxx — 1 байт (7 бит)
                                                                10xxxxxx xxxxxxxx — 2 байта (14 бит)
                                                                110xxxxx xxxxxxxx xxxxxxxx — 3 байта (21 бит)

                                                                Предложение:
                                                                Использование алгоритма компактного числа (не помню как называется):
                                                                0xxxxxxx — 1 байт (7 бит)
                                                                1xxxxxxx 0xxxxxxx — 2 байта (14 бит)
                                                                1xxxxxxx 1xxxxxxx 0xxxxxxx — 3 байта (21 бит)
                                                                1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx — 4 байта (28 бит)

                                                                Решена проблема нахождения символа по середине текста (Поиск бита 0х80).
                                                                Правда нет загашника.
                                                                Но можно загашник использовать из ASCII, 0xxxxxxx — 1 байт (7 бит), натягивая текущий алфавит от предыдущего символа.

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

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