Яр - как правильно спроектировать структуру данных строковых типов

Ну я так понял, что ё нормализуется, даже если оно введено в виде е и двух точек

ЕМНИП в юникоде для буквы ё не определена декомпозиция, поэтому поиск с эквивалентными е/ё приходится велосипедить вместо использования NFD

Но тогда по сути (для частного случая русского языка) нормализация - это и есть превращение в графемный кластер

Для частного случая русского языка любой юникодный code point - графемный кластер, нормализация ничего не изменит

Использовать code point'ы с NFC нормализацией - это вполне разумное приближение для графемных кластеров, огромное количество кода в мире его использует (твиттер, например, именно так считает количество символов в сообщении), но в общем случае это не одно и то же

Да вот тут выше писали, что е и две палки - это «то же самое» , что ё. У меня так получается:

> (format t "~A~A" (code-char #x438) (code-char #x306))
й ; в GUI

> (format *trace-output* "~A~A" (code-char #x438) (code-char #x306)) 
(finish-output *trace-output*)
; печатается в консоли офтопика как отдельное "и" и отдельная 
волна за ним, но при копировании из консоли в окно ответа этого
 форума опять получается "й".

Операции поиска и замены работают на уровне code point'ов, а не графемных кластеров.

То есть, если мне надо найти слов «ёкарный», то мне надо искать все 4 возможные комбинации? А для поиска какого-нибудь вьетнамского выражения 2 в степени «количество слогов»? Издеваешься?

Для типа графемных кластеров придумали нормализацию (NFKC). Но они калечат отображение X² == X2.

К тому же, в огромном количестве кода даже этого не требуется, строки хранятся, передаются и сравниваются как единое целое, т.е. как байты

Ну если их не надо выводить, не надо сравнивать (например при копировании файла с текстом целиком), то конечно.

Пожалуй единственные случаи, когда нужны графменые кластеры - это шейпинг текста и редактирование на экране с помощью курсора

Даже для любого регекспа нужны. Например «инициал» = «заглавная буква» + «точка». Если заглавная буква с ударением или это Ё, то можно получить неверный результат.

Для типа графемных кластеров придумали нормализацию (NFKC). Но они калечат отображение X² == X2

А X² - это же два глифа, а не один? Почему тогда они его калечат?

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

Существуют буквы, для которых нет нормализации. Например «Он описа́л этот памятник». Здесь после нормализации ударение занимает отдельную букву.

То есть, если мне надо найти слов «ёкарный», то мне надо искать все 4 возможные комбинации? А для поиска какого-нибудь вьетнамского выражения 2 в степени «количество слогов»? Издеваешься?

Откуда такие выводы? Конечно, искать надо в нормализованном варианте

Только какое отношение имеет нормализация к графемным кластерам? Насколько я понимаю, юникод не дает гарантию, что для любого графемного кластера есть композиция из одного code point'а, и границы кластеров определяются по отдельным правилам.

А X² - это же два глифа, а не один? Почему тогда они его калечат?

Normalization Form KC (NFKC) и Normalization Form KD (NFKD) помимо (де)композиции, нормализуют следующие символы:

Изощрённые шрифты (ℍ и ℌ)
Кружки (①)
Изменённый размер и угол поворота (ｶ и カ, ︷ и {)
Степени (⁹ и ₉)
Дроби (¼)
Другие (™)

Можно использовать NFC, но там другая проблема: affine и affine --- абсолютно разные слова. И гарантии на то, что одна графема будет одни кодпоинтом всё равно нет

Откуда такие выводы? Конечно, искать надо в нормализованном варианте

Однажды я прогуливался по мосту и увидел человека, стоящего на краю, который собирался прыгнуть. 
Я быстро подбежал к нему и сказал «Стой! Не делай этого!»
«Я ничего не могу поделать» — плакал он, «я потерял интерес к жизни».
«Чем ты зарабатываешь на жизнь?» — спросил я.
Он сказал: «Я разрабатываю технические требования для веб-сервисов»
«Я тоже!» — сказал я. «Ты используешь REST-сервисы или SOAP-сервисы?»
Он сказал: «REST-сервисы»
«Я тоже!» — сказал я. «Ты используешь текстовой формат XML или бинарный формат XML?»
Он сказал: «текстовой формат XML»
«Я тоже!» — сказал я. «Ты используешь XML 1.0 или XML 1.1?»
Он сказал: «XML 1.0»
«Я тоже!» — сказал я. «Ты используешь UTF-8 или UTF-16?»
Он сказал: «UTF-8»
«Я тоже!» — сказал я. «Ты используешь нормализацию юникода формы C или нормализацию юникода формы KC?»
Он сказал: «нормализацию юникода формы KC»
«Умри, иноверная мразь!» — прокричал я, и столкнул его с моста.

© http://tty01.blogspot.ru/2004/07/unicode-normalization-form-c.html

Я имел в виду только то, что для поиска и замены границы графемных кластеров определять не нужно.

Какую форму нормализации использовать - это уже по ситуации, API или структура данных строки от этого не изменится.

Я имел в виду только то, что для поиска и замены границы графемных кластеров определять не нужно.

Если я укажу заменить в тексте q на s, то q̣̇ внезапно заменится на ṩ и текст перестанет быть нормализованным, так как для ṩ существует представление в виде одного кодпоинта.

Операции поиска и замены работают на уровне code point'ов, а не графемных кластеров.

Это смотря что и как искать. Если искать тупо последовательность code points, то логично, что операция не знает о графемных кластерах. Но может быть нужно искать именно конкретную последовательность как кластер. Например, чтобы в строке ç̈a (U+0063 U+0327 U+0308 U+0061) поиск подстрок c̈ (U+0063 U+0308) или ç (U+0063 U+0327) давал или не давал вхождений. Но вообще это ближе к нормализации, потому что в таком случае часто ещё и без учёта регистра надо искать, а также учитывать всякие композиции-декомпозиции

В то же время в начале этой темы высказывалось мнение о том, что тип строки должен быть единственным. Но мне кажется, что возникает более чем один тип:

• строка в лучшем виде (массив кластеров)
• то, что отправляется по сети (набор байт в той или иной кодировке)

И вот в этом втором пункте и начинают появляться всякие «строка в кодировке utf-8», «строка в кодировке utf-16», строка нормализованная так и сяк - просто потому, что если мы внутри своей среды выполнения устроим рай, то нужно будет в этом раю манипулировать и с сущностями среднего мира, а они разношёрстные.

Кажется самым простым запретить для них все операции, кроме преобразования из/в правильную строку и разбития на подстроки (для буферизации), но я боюсь, как бы тут реальность не внесла свои коррективы.

И мне кажется, что из чтения этого https://gist.github.com/julik/1852214

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

Я бы не сказал, что это строковые типы.

Модель текстовых данных — это набор чиселок в какой-нибудь кодировке, которые каким-нибудь образом представляются байтами, чтобы их хранить и передавать. Тут я навскидку вижу три варианта:

• поднять лапки вверх: строка = байты, кодировку и всё прочее выдумывайте сами;
• исповедовать единственно верный способ представления текста: строка = ASCIIZ, или UTF-16/UTF-8, или что-нибудь однобайтовое в соответствии с текущей локалью, и т. д.;
• сесть на все стулья сразу: строка = байты + кодировка, можно делать прозрачные преобразования и иногда даже не терять информацию.

А вот к этой модели можно уже наворотить сколько хочется представлений: графемные кластеры, code points, байтики. Но только для всего, кроме байтиков, нужно уже знать кодировку строки и использовать алгоритмы, специфичные для кодировки.

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

Культурное влияние скорее просматривается в языках программирования, где хочется и добавить поддержку Юникода, и каким-то образом сохранить вековую традицию «строки — это ж просто массивы символов», и сделать так, чтобы любые привычные операции с массивами работали не только для английского языка. Тем временем, тот же Юникод не такой простой. Это не просто массивы символов.

Лично я думаю, что нельзя сделать сразу те три вещи выше. Поэтому есть смысл поступать прагматично: сделать родные строки максимально похожими на культурный идеал «тупо массива» и предоставить возможность опускаться до уровня Юникода тем, кому надо.

То есть так, чтобы для родных строк индексация, конкатенация, поиск и замена а) никогда не приводили к некорректным результатам, б) выдавали простой предсказуемый результат, в) результат был близок к тому, что выдают алгоритмы Юникода.

Представление строки как массива графемных кластеров подходит под этот идеал. Здесь нельзя неправильно склеить байтики UTF-8 или суррогаты UTF-16 и сломать строку. Если строку разбить на символы по индексам, а потом склеить — то получится исходная строка (или как минимум что-то очень похожее на неё). Длина строки выдаёт максимальный доступный индекс. Поиск и замена не приводят к весёлым ложным срабатываниям.

Тем же, кому нужно Юникод-корректное поведение, можно выдать реализации низкоуровневых алгоритмов. Пусть там уже помнят, как нормализуется конкретная строка, и все прочие особенности. Эти люди знают, что делают.

Поэтому есть смысл поступать прагматично: сделать родные строки максимально похожими на культурный идеал «тупо массива» и предоставить возможность опускаться до уровня Юникода тем, кому надо.

Похоже, что так, ура! (правда, сейчас наверняка придёт Монк и подкинет ещё какой-нибудь контпримрер).

правда, сейчас наверняка придёт Монк и подкинет ещё какой-нибудь контпримрер

Если реализовывать как

Представление строки как массива графемных кластеров подходит под этот идеал. Здесь нельзя неправильно склеить байтики UTF-8 или суррогаты UTF-16 и сломать строку. Если строку разбить на символы по индексам, а потом склеить — то получится исходная строка (или как минимум что-то очень похожее на неё). Длина строки выдаёт максимальный доступный индекс. Поиск и замена не приводят к весёлым ложным срабатываниям.

то контрпримера не будет. Единственный язык с юникодом, который пошёл по другому пути — это Rust. Хотя у них есть итератор по графемам.

Потенциальный подводный камень --- лигатуры. С одной стороны лигатура является одной графемой, с другой стороны, почти всегда работать с ней надо (при поиске и замене) как с отдельными символами.

Кстати, посмотрел на нормализацию по-умолчанию в DrRacket

(define/public (string-normalize s) 
      (regexp-replace* 
       #rx"\u200b" 
       (regexp-replace*
        #rx"\u2212" 
        (string-normalize-nfkc s)
        "-")
       ""))

Теперь озадачен.

Существенный недостаток вижу только один. Исчезает числовое представление буквы. То есть буква может соответствовать списку чисел, а не одному числу.

Это корректно, но отличается от всех остальных языков программирования.

исчезает числовое представление буквы

Для русского языка ведь наверняка такой проблемы не существует? А китайцы, мне кажется, к такому привыкли, потому что в винде (не знаю, как в современной) utf-16, в котором как раз приходится иероглифы кодировать несколькими буквами, если я ничего не путаю.

Исчезает числовое представление буквы

Можно расширить мой предыдущий вариант структуры дополнительным полем-массивом длин графем или же просто номером-позицией графем .
«abcç̈a»
[1,1,1,2,2] - длинна символа
[1,2,3,4,6] - позиция символа

Можно расширить мой предыдущий вариант структуры

Угу. Это уже вопрос как представить, он вторичен. Я пока на концептуальном уровне не всё понимаю (про виды нормализации ещё надо почитать).

Это корректно, но отличается от всех остальных языков программирования.

список чисел из наперёд диапазона можно представить бигнумом.

Для русского языка ведь наверняка такой проблемы не существует?

Строка «ПОГО́ДА» написана по-русски? В ней у четвёртой буквы нет кода. Есть список кодов (1054,769).

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

Вопрос не в том, как кодировать, а в том, как работать. В Java, например, элементом строки является int. В CL есть char-code. А если за основу взять графемы, то char-code должен возвращать список.

дополнительным полем-массивом

Тогда уж сразу по пути Rust'а. Строка = массив байт и итераторы по графемам и кодпоинтам. Для языка высокого уровня жутко неудобно.

список чисел из наперёд диапазона можно представить бигнумом.

Код буквы в виде бигнума. Прикольная идея. С учётом того, что бигнум в CL базовый тип, мне нравится.

Для языка высокого уровня жутко неудобно.

Из-за того, что нельзя получить/заменить, например, пятую «букву»? Как по мне, тут не столько в (высоко)уровневости дело. Хотя мне «работать с текстом» приходилось довольно редко.

Из-за того, что нельзя получить/заменить, например, пятую «букву»?

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

Примерная аналогия — арифметика. В CL и других нормальных языках есть бесконечные целые, автоматически использующиеся по необходимости, есть рациональные числа. То есть, например, бухучёт можно строить как есть без округления. Требовать в языке высокого уровня явно отслеживать переполнения как в Си было бы также жутко неудобно.

Требовать в языке высокого уровня явно отслеживать переполнения как в Си было бы также жутко неудобно.

C#, например, достаточно высокого уровня? Там, конечно, «слегка» удобнее, чем в С, но checked необходимо в нужных местах руками расставлять.

В CL и других нормальных языках есть бесконечные целые, автоматически использующиеся по необходимости

С этим, насколько я знаю, тоже не всё так просто. Ну или список «нормальных языков» не такой и большой.

А ведь без этого знания я правильный поиск в Rust не напишу.

Дык, эта тема показывает, что и в «нормальных языках» нюансы имеются.

C#, например, достаточно высокого уровня?

Нет. Он промежуточного. Как Java и C++.

Ну или список «нормальных языков» не такой и большой.

CL, Scheme, Haskell, всё семейство ML, Python, 1C... Практически все, где при реализации алгоритма не приходится бороться с самим языком.

Дык, эта тема показывает, что и в «нормальных языках» нюансы имеются.

Тут проблема устаревания стандарта. Когда принимали ANSI CL всего этого кошмара (композитных символов) не было. А значит графема и кодпоинт являлись одним и тем же. Сейчас на юникод навешали вагон костылей (одни варианты и полтора десятка пробелов чего стоят).

Надо соблюдать спокойствие. Письменность - это сложно, как и другие гуманитарные явления (например, календарь).

Нет. Он промежуточного. Как Java и C++.

Понятно.

Кстати, про «бесконечные целые автоматически используемые при необходимости»: насколько я понимаю, в том же Haskell если тип задан явно, то при переполнении автоматически расширяться он не будет.

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

В CL тоже можно declare fixnum написать.

А если явно написать Integer, то будет.

понимаете, какое дело, текст может быть только в 1-й кодировке: unicode, хоть и в различных вариациях

ascii, к слову, тоже подмножество юникода

всё остальное не текст, а бинарные данные

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

нельзя, т.к. бухучёт использует только целые числа, без округления ошибка будет

понимаете, какое дело, текст может быть только в 1-й кодировке: unicode, хоть и в различных вариациях, ascii, к слову, тоже подмножество юникода

А Shift-JIS и Big5 не являются подмножеством юникода. Так что увы.

бухучёт использует только целые числа, без округления ошибка будет

Так в ответе будут целые, а в расчёте рациональные и ответ будет верный. Float использовать нельзя, так как последовательность операций влияет на результат.

это их проблемы

это их проблемы

С таким подходом можно КОИ-8 использовать. Для русского хватит, а у остальных «их проблемы».

остальным - юникод, все нужные символы там есть/будут

В Java, например, элементом строки является char (== short == int16)

FIXED. И то есть планы по компактификации ASCII-only стрингов в byte[], возможно, будет уже в девяточке.