UTF-16 и произвольный доступ
(их вообще кто-нибудь в природе встречал?).я так понимаю, что вы не работаете активно с мрачными юникодными строками
поэтому предлагаю такой подход:
- если строчка простая, то храните UCS-2 (массив 16-битных символов)
- если строчка содержит суррогатные пары, то храните массив 32-битных символов
если строчка содержит суррогатные пары, то храните массив 32-битных символовЭто неплохой вариант. Но всё равно обидно, если в тексте из полмиллиарда символов встретилась одна суррогатная пара, тратить на неё лишний гигабайт...
понял, вы работаете с большими текстами, тогда такой подход не годится 
могу посоветовать монстра по имени icu
http://icu-project.org/repos/icu/icuhtml/trunk/design/string...
могу посоветовать монстра по имени icu
http://icu-project.org/repos/icu/icuhtml/trunk/design/string...
Вообще, похоже, третий вариант круче всего. Если в тексте N символов, из которых M имеют код больше 0xFFFF, то расход памяти: 2N + 6M байт (при условии, что позиция укладывается в 32 бита а время доступа: O (1 + ln (M...
не забудьте учесть случай, когда кругом суррогатные пары 
не забудьте учесть случай, когда кругом суррогатные парыНу в этом случае расход памяти всего в два раза больше, чем при честном хранении 32-битных символов... И производительность весьма умеренно деградирует, благодаря логарифмической сложности... И спасибо за ссылку.
UTF-16
как вариант 24-битныхЩито?
Насколько произвольный доступ? Запись или чтение?
Щито?Ну современный Unicode, он примерно в 21 бит влезает... Так что можно символы в виде 24-битных целых хранить, хотя, конечно, в виде 32-битных удобнее.
Насколько произвольный доступ?Ну типа по заданной позиции (позиция --- это порядковый номер символа считая от начала текста).
Запись или чтение?Эффективным должно быть чтение. Замена символа и даже вставка/удаление тоже могут понадобиться, но для них эффективность O(n) в принципе подходит.
Эффективным должно быть чтение. Замена символа и даже вставка/удаление тоже могут понадобиться, но для них эффективность O(n) в принципе подходит.тогда есть модификация третьего метода: в дополнительном массиве хранить не только положения суррогатных пар, но еще и количество их до j-го символа. Тогда доступ будет за O(1). Пересчитывается за линейное время. Возможно, есть полезные структуры данных для этого.
но еще и количество их до j-го символаЯ правильно понимаю, что хранить надо для каждого j? Если так, то это нивелирует весь выигрыш по памяти.
а, точняк, давно первый пост читал
Ну храни тогда последовательности 16 -> 32 -> 16 -> 32 -> 16 -> 32, в отдельном массиве их длины. 16-битные последовательности еще дополнять до кратного 32 битам для удобства адресации. Время доступа O(числа переключений в худшем случае - O(кол-ва 32-битных пар ня?
а откуда известно, что очень нужны эти UCS-4 символы? У нас вот на них кладется, даже в gcc (где wchar_t 32битный) используется short. В винде вот используется UCS-2 без суррогатов. А вам сильно надо?
У нас вот на них кладется, даже в gcc (где wchar_t 32битный) используется short. В винде вот используется UCS-2 без суррогатов.у нас тоже используется basic_string<short> в юниксах, но подразумевается UTF-16 при этом
в виндовых апи тоже ожидается UTF-16, не смотря на то, что в старых виндах UCS-2 был
вики
UTF-16 is the native internal representation of text in the Microsoft Windows 2000/XP/2003/Vista/CE;
а откуда известно, что очень нужны эти UCS-4 символы?Это нужно, чтобы иметь моральное право сказать, что программа поддерживает Unicode. А в Win32 там UTF-16, а не UCS-2...
То, что у вас "на них кладётся", это ценная информация, но нам не поможет.
Задача: хранить в памяти текст Unicode с возможностью эффективного произвольного доступа.Я бы хранил просто UTF-8, и отдельно держал бы таблицу смещений по какому-то модулю, например. А конкретный символ уже выискивать от смещения.
Вообще, всё от языка зависит. Надо понять каких символов там больше всего. Универсальное тут что-то посоветовать нельзя.
Да и что такое "эффективный произвольный доступ"? Что это? Изменять придется? Или только читать? И насколько произвольно? Задачу бы рассказал.
там откуда возникает произвольный доступ обязательно использовать смещение в символах?
согласен с пианистом по поводу утф-8 и индекса. для текста например индекс строк выглядит логично.
согласен с пианистом по поводу утф-8 и индекса. для текста например индекс строк выглядит логично.
Чуваки, вы про нормализацию и акценты забываете.
Типа, там есть несколько десятков особых символов — всякие умляуты, аксантэгё, ударения етс. Есть даже по-моему ещё более долбанутые для изготовления индексов, например, но это память меня может подводить уже. Так вот, эти особые символы можно комбинировать по нескольку штук сразу. Для часто используемых есть нормализованные версии — ну, собственно, буковки с умляутами. Разумеется, не для всех буковок встречаются варианты с умляутами, а особенно с умляутами и ударениями вместе.
Соответственно во-первых существует как минимум две нормальные формы (для любой из разновидностей уникода) — максимально сжатая и максимально денормализованная, и надобно выбрать одну из них и приводить всё к ней. Иначе у вас сравнение строк тупо не будет работать. Ну и кстати разумеется никакого признака способа нормализации в кодировке не предусмотрено, и зачем в самом деле, лол. Да, не ислючено, что кодеки в избранном языке уже автоматически нормализуют всё так или иначе, но это надобно проверить.
Но это я в порядке лирического отступления, суть же моего спича в том, что никакого UTF-32 не хватает чтобы хранить текст с ударениями (например) так, чтобы при выкусывании оттуда куска не появлялось висячих и ударений и не исчезали нужные. Так что мысли в этом направлении можно оставить сразу же.
По поводу остального: во-первых, а нафига собственно доступ по индексу нужен-то? Это же наверняка часть какой-то бОльшей задачи, типа "возможность перехода на энтую строку плюс возможность перевода курсора на следующий или предыдущий символ", которую и надо решать — заводя массив индексов адресов строк (а то и вовсе работая с массивом строк атакже понапиздив где-нибудь корректно работающие функции перехода по символам взад-вперёд (оно как бы однозначное даже в обратную сторону, хоть про это специально подумали).
Во-вторых, все известные мне современные языки хранят текст в UCS-2, позволяя программисту самому заморачиваться неразбиением суррогатных пар если ему это нужно. Полагаю, что это наилучший вариант в силу разнообразных причин!
Типа, там есть несколько десятков особых символов — всякие умляуты, аксантэгё, ударения етс. Есть даже по-моему ещё более долбанутые для изготовления индексов, например, но это память меня может подводить уже. Так вот, эти особые символы можно комбинировать по нескольку штук сразу. Для часто используемых есть нормализованные версии — ну, собственно, буковки с умляутами. Разумеется, не для всех буковок встречаются варианты с умляутами, а особенно с умляутами и ударениями вместе.
Соответственно во-первых существует как минимум две нормальные формы (для любой из разновидностей уникода) — максимально сжатая и максимально денормализованная, и надобно выбрать одну из них и приводить всё к ней. Иначе у вас сравнение строк тупо не будет работать. Ну и кстати разумеется никакого признака способа нормализации в кодировке не предусмотрено, и зачем в самом деле, лол. Да, не ислючено, что кодеки в избранном языке уже автоматически нормализуют всё так или иначе, но это надобно проверить.
Но это я в порядке лирического отступления, суть же моего спича в том, что никакого UTF-32 не хватает чтобы хранить текст с ударениями (например) так, чтобы при выкусывании оттуда куска не появлялось висячих и ударений и не исчезали нужные. Так что мысли в этом направлении можно оставить сразу же.
По поводу остального: во-первых, а нафига собственно доступ по индексу нужен-то? Это же наверняка часть какой-то бОльшей задачи, типа "возможность перехода на энтую строку плюс возможность перевода курсора на следующий или предыдущий символ", которую и надо решать — заводя массив индексов адресов строк (а то и вовсе работая с массивом строк атакже понапиздив где-нибудь корректно работающие функции перехода по символам взад-вперёд (оно как бы однозначное даже в обратную сторону, хоть про это специально подумали).
Во-вторых, все известные мне современные языки хранят текст в UCS-2, позволяя программисту самому заморачиваться неразбиением суррогатных пар если ему это нужно. Полагаю, что это наилучший вариант в силу разнообразных причин!
эгё"эгю", сын мой.
Оставить комментарий
VitMix
Задача: хранить в памяти текст Unicode с возможностью эффективного произвольного доступа.Мне в голову пришли следующие три варинта:
Первый вариант: хранить текст как массив 32-битных (как вариант 24-битных) символов. Всё хорошо с точки зрения эффективности доступа, но жалко тратить 3 или даже 4 байта памяти на символ, при том, что практически наверняка символы с кодами больше 0xFFFF в тексте не встретятся (их вообще кто-нибудь в природе встречал?).
Достоинства: простота реализации, скорость
Недостатки: перерасход памяти
Второй вариант: хранить текст в виде массива 16-битных слов. Для символов с кодами меньше 0x10000 там будет сам символ, а для прочих символов там будет первая часть UTF-16 суррогатной пары. Вторые части пар при этом можно хранить в хэш-таблице типа позиция=>значение.
Достоинства: экономия памяти, скорость
Недостатки: сложность реализации
Третий вариант: хранить текст в виде массива 16-битных слов в кодировке UTF-16. Отдельно иметь массив целых чисел, содержащий позиции всех суррогатных пар. Этот второй массив использовать для коррекции индекса при произвольном доступе. В этом случае время произвольного доступа будет пропорционально количеству в тексте суррогатных пар (то есть количеству в тексте символов с кодами больше 0xFFFF).
Достоинства: эффективность по памяти, лёгкость конвертации в/из UTF-16 (это может понадобиться)
Недостатки: сложность реализации
Кто-нибудь что-то подобное использовал? Или может быть какие-то другие варианты.