Upd. похоже, что придумалось решение.
====== Задача такая:
Пусть задан некоторый алфавит A и алфавит B. Будем считать, что все символы алфавита A появляются равновероятно. Каждый символ алфавита B имеет некоторый вес — вещественное число, характеризующее сложность его передачи. Необходимо построить префиксный код, кодирующий символ алфавита A словом над алфавитом B, минимизирующий средний вес получающегося слова над алфавитом B.
Техническое замечание: алфавит A как можно больше (меньше 224 — странно), алфавит B порядка 220, причем в нем примерно 5 различных весов 4 различных веса передачи. Радовать будет просто хорошее решение.
Источник: жизнь (необходимо записать бинарные данные в Unicode так, чтобы UTF-16 и UTF-8 представления были не очень длинными).
Примерные данные алфавита B:
| Количество символов | w1 | w2 | Описание, кому интересно |
| 27 - 25 | 1 | 1 | Однобайтовые UTF-8 символы, кроме "плохих" первых 32 |
| 211 - 27 | 2 | 1 | Двухбайтовые UTF-8 символы |
| 216 - 211 - 211 - 2 | 3 | 1 | Трехбайтовые UTF-8 символы, кроме "плохих" последних двух и суррогатов: Неверный BOM U+FFFE и символ U+FFFF запрещены в Unicode. U+D800..U+DFFF — диапазон суррогатных пар для UTF-16, запрещен в Unicode. |
| 220 | 4 | 2 | Старшая часть Unicode, которая кодируется суррогатной парой в UTF-16 |
Итоговый вес — это, например, 0.45w1 + 0.55w2
Upd. в итоге получилось построить перекодировку бинарных данных в Unicode со средней избыточностью ~30% для UTF-8 и ~20% для UTF-16 представлений (~40% и ~35% худшие случай, соответственно) кодированием 12-байтовых последовательностей. Для UTF-8 это практически неулучшаемо из-за собственной избыточности UTF-8, для UTF-16 низкая избыточность ведет к высокой избыточности представления в UTF-8. Вероятно, что для более длинных последовательностей можно улучшить результат UTF-16 при том же значении UTF-8, но избежать вычислений в длинной арифметике будет крайне проблематично.
Comments (0)
