Каково самое длинное представление UTF8 строки в форме NFC заданной длины?

Контекст.

Я пишу C для спецификации iCal (RFC 5545). Он указывает, что максимальная длина строки с разделителями составляет 75 октетов, не считая разделителя. Как принцип надежности, так и символьная модель W3C склоняют меня к канонизации входных строк, закодированных в UTF8, в форму NFC (см. Формы).

При чтении входных строк я хотел бы читать в статически выделенный буфер. Но представление строки в UTF8 может иметь длину более 75 октетов, даже если ее форма NFC меньше 75. Таким образом, этот буфер должен быть больше 75 октетов. У меня вопрос сколько.

Вопрос.

Какова максимальная длина в октетах строки UTF8, форма NFC которой составляет не более 75 октетов? (Бонусные баллы: чья форма NFC состоит не более чем из N октетов.)

Кроме того, является ли это гарантированным и постоянным или является неуказанным следствием текущего Unicode и может быть изменено?


utf-8 canonicalization unicode-normalization canonical-form
person holomenicus    schedule 10.10.2018    source источник
comment
Почему бы вместо этого просто не использовать динамически выделяемый буфер? Выполните преобразование NFC, и если результат больше, чем ваш текущий размер буфера, перераспределите буфер на больший размер.   -  person Remy Lebeau    schedule 11.10.2018
comment
@RemyLebeau Да, я мог бы сделать это вместо этого. Вопрос по-прежнему актуален, потому что ответ будет информировать о предполагаемом размере начального буфера до перераспределения.   -  person holomenicus    schedule 12.10.2018
comment
Необходимый размер действительно зависит от конкретных кодовых точек, закодированных в строке. Одна кодовая точка кодируется между 1..4 байтами в UTF-8, поэтому строка из 75 октетов в UTF-8 может содержать максимум от 18 до 75 кодовых точек, в зависимости от конкретного содержимого. В лучшем случае, если строка состоит только из кодовых точек ASCII U+0000..U+007F, то 1 октет на кодовую точку (максимум 75 кодовых точек). В худшем случае, если строка состоит только из кодовых точек U+10000..U+10FFFF, то 4 октета на кодовую точку (максимум 18 кодовых точек).   -  person Remy Lebeau    schedule 12.10.2018

Ответы (1)


arrow_upward
1
arrow_downward

Вот некоторый код Javascript, который пытается найти кодовую точку Unicode, чье представление UTF-8 сокращается больше всего при преобразовании в NFD и обратно в NFC. Кажется, что ни одна кодовая точка не уменьшается более чем в три раза. Насколько я понимаю алгоритм нормализации Unicode, таким образом нужно проверять только одиночные кодовые точки.

Я думаю, что, по крайней мере теоретически, это может измениться в будущих версиях Unicode. Но существует политика стабильности в отношении расширения строк при нормализации в NFC (см. также Может ли нормализация Unicode NFC увеличить длину строки?), поэтому я думаю, что маловероятно, что это когда-либо изменится:

Канонические сопоставления (значения свойства Decomposition_Mapping) всегда ограничены, поэтому ни одна строка при нормализации к NFC не увеличивается более чем в 3 раза по длине (измеряется в кодовых единицах).

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

var maxRatio = 2;
var codePoints = [];

for (var i=0; i<0x110000; i++) {
  // Exclude surrogates
  if (i >= 0xD800 && i <= 0xDFFF) continue;
  var nfd = String.fromCodePoint(i).normalize('NFD');
  var nfc = nfd.normalize('NFC');
  var nfdu8 = unescape(encodeURIComponent(nfd));
  var nfcu8 = unescape(encodeURIComponent(nfc));
  var ratio = nfdu8.length / nfcu8.length;
  if (ratio > maxRatio) {
    maxRatio = ratio;
    codePoints = [ i ];
  }
  else if (ratio == maxRatio) {
    codePoints.push(i);
  }
}

console.log(`Max ratio: ${maxRatio}`);

for (codePoint of codePoints) {
  // Exclude Hangul syllables
  if (codePoint >= 0xAC00 && codePoint <= 0xD7AF) continue;
  var nfd = String.fromCodePoint(codePoint).normalize('NFD');
  var nfc = nfd.normalize('NFC');
  console.log(
    codePoint.toString(16).toUpperCase(),
    encodeURIComponent(nfd),
    encodeURIComponent(nfc)
  );
}

person nwellnhof    schedule 19.10.2018