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, но избежать вычислений в длинной арифметике будет крайне проблематично.
Дерево хаффмана, код хаффмана Но в твоем случае (5 различных весов) возможно можно придумать что-то быстрее, хотя не очень понятно зачем.
Код Хаффмана не поддерживает веса вывода, у него веса ввода.
Да, видимо не так понял задачу, как и велосипедист ниже.
Не удержался :D
Если решение знаешь, я вполне согласен на велосипед. Только расскажи ;)
Да нет, не знаю, только на правах шутки =)
Я стал искать картинку с велосипедом еще до того, как зашел сюда. Мне хватило автора и названия =)
Да, я что-то забыл, надо было самому себе запостить.
Или я сегодня совсем туплю, или не очень-то очевидно что такое w1 и w2.
В данном случае — количество
байтовсимволов, необходимых для представления символа Unicode в UTF-8 и UTF-16. Итоговую стоимость символа Unicode получаем взвешенным суммированием этих двух значений.И как мы в UTF16 кодируем 2^16 символов одним байтом?
Символов, прошу прощения. Для UTF-16 символ имеет размер два байта.
Есть идея использовать только символы размера 1 байт для UTF8 и 2 байта для UTF16, сложно придумать случай где выгодно использовать и другие символы, ибо они слишком большие по размеру, а различных вариантов имеют мало.
Это будет вариация на тему base64. Она жутко неудачная для UTF-16.
Или я снова не понимаю задачу, или ты не понимаешь очевидность решения. Давай рассмотрим задачу для UTF8. Символы первого типа имеют размер 8 бит, и количество вариантов 128-32=96, т.е. из 8 записанных битов полезной информации выходит 6.58 бита, итого имеем 0.82 по соотношению (информация/место место на диске) для второго типа у нас примерно 11 бит информации, а размер 16 бит получаем коэффициент 0.68, а дальше только хуже. Поэтому использование этих символов невыгодно никогда, для случая что символы алфавита A равновероятны, и нас интересует только матожидание длины кода для случайного текста.
UPD: Понял где не прав, иногда может быть выгодно часть символов алфавита A подвесить за ветку дерева с буквой более плохого типа.
Для UTF-16 в base64 получаем 6/16 = 0,375 эффективности записи, для UTF-8 получаем 6/8 = 0,75
Если мы будем использовать 2^15 символов, представимых в UTF-16 за один символ (два байта), будет не меньше 15/16 = 0,9375 эффективности UTF-16 и 15/24 = 0,625 эффективности UTF-8.
Ну так я тебе и предложил 0.82 для UTF8 и 2 байта для UTF16, т.е. 0,9375 эффективности как ты говоришь
Вся беда в том, что кодировать надо именно в Unicode (а не отдельно в UTF-8 и отдельно в UTF-16). Слишком длинная UTF-16 создает угрозу #MLE, от длины UTF-8 увеличивается время кодирования и занимаемое место на диске.
Похоже, что задача решается "инверсией" построения кода Хаффмана. Будем строить дерево префиксного перекодирования B -> A, начиная с одного корня и на каждой итерации "дробя" самый легкий узел. Эта жадность выглядит правильно.
И так делать до тех пор пока число листьев не превзойдет размер алфавита A, я правильно понял?
Да.
Это не выглядит верным решением, ибо символы 4-го типа чрезмерно тяжелые. 4 байта на 20 бит? ну его в топку, дешевле сделать 4 уровня однобайтовых значений. при |A| ~ 2^20 ты остановишься не первом шаге, а решение мягко говоря далеко от идеала.
Вроде бы, если мы "дробим" меньший узел, но не "дробим" больший, всегда можно поменять местами и будет лучше.
Да, действительно. Останавливаться на "больше размера алфавита" — неверно. Надо дольше дробить.