Оптимальное целочисленное кодирование, которое все еще сортируется

Одна из опрятных характеристик UTF-8 состоит в том, что если вы сравниваете две строки (с <) побайтно, вы получаете тот же ответ, как если бы вы сравнивали их по кодовым точкам. Мне было интересно, была ли подобная кодировка оптимальной по размеру (например, UTF-8 "отнимает" пространство, помещая байты в 10xxxxxx, если они не являются первым байтом, представляющим кодовую точку).

Предположение об оптимальности здесь состоит в том, что неотрицательное число n является более частым, чем число m, если n < м.

Мне больше всего интересно узнать, существует ли (байтовая сопоставимая) кодировка, которая работает для целых чисел, причем n чаще, чем m, если | n | < | М |.

Ответ 1

Вы рассматривали вариант кодирования Хаффмана? Традиционно один рекурсивно объединяет два наименее частых символа, но чтобы сохранить порядок, можно объединить два смежных символа с наименьшей суммой.

Похоже, эта проблема была хорошо изучена (а жадный алгоритм не является оптимальным). Оптимальный алгоритм дал Ху и Такер, который описан здесь и более подробно в этом thesis.

Эта статья обсуждает сжатие на основе словаря, сохраняющее порядок, также выглядит интересным.

Ответ 2

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

Для кодирования целых чисел, использующих UTF-8 в качестве базового алгоритма, влечет за собой отображение первых n целых чисел в 1-байтовое кодирование, следующее m для 2-байтового кодирования и т.д. Независимо от того, является ли это оптимальное кодирование, зависит от распределения. Если первые n чисел очень часты по сравнению с более высокими номерами, то UTF-8 будет (близким) оптимальным.

Ответ 3

Существует очень мало стандартных кодировок, и ответа нет. Любая дальнейшая оптимизация за пределами UTF-8 не должна упоминаться как "кодирование", но "сжатие" - и лексикографически сопоставимое сжатие - это другой отдел.

Если вы решаете реальную (не чисто академическую) проблему, я просто придерживаюсь самого стандартного UTF8. Вы можете узнать о его эффективности по сравнению с другими стандартными кодировками на utf8everywhere.org.