Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Category:

Порядок

Сперва о порядке байтов в представлении слов.

У нас есть два порядка байтов в слове: LSB, младший (наименее значимый) байт вперёд и MSB, старший (наиболее значимый) байт вперёд. В первой случае проще преобразовывать между значениями разных размеров, второй случай проще сравнивать побайтово (memcmp).

Можно считать, что для MSB порядка байтов "вес" i-го (от адреса значения, i=1..size, 1 это байт по адресу значения) байта равен 256(size-i).

Теперь о порядке строк.

Строки мы сравниваем побайтово, как "целые в кодировке старший байт вперёд". Однако от целых строки отличны наличием длины, строка может содержать и ноль байтов и теребайт. В библиотеке crit bit trees предлагают считать все строки представленными бесконечной последовательностью байтов с дополнением нулями справа.

Размер у нас бесконечный, поэтому вес i-го байта строки мы определим, как 256-i. То есть, строки можно представлять в виде бесконечных дробей.

Арифметическое кодирование так же представляет последовательности символов в виде бесконечных дробей.

Про порядок арифметически закодированных строк.

Сперва предложу рассмотреть кодирование битов. Если мы используем одну и ту же, сколь угодно динамическую модель, то конкретный i-й бит 0 всегда будут закодирован в диапазоне [0..pi), а 1 всегда будет закодирован в диапазоне [pi..1). То есть, последовательность битов, начинающаяся с 0, будет иметь закодированное представление меньшее (в смысле сравнения получившихся строк - получившаяся дробь будет меньше), чем последовательность битов, начинающихся с 1.

В случае кодирования битов мы кодируем полный алфавит.

И если мы кодируем полный алфавит, как это принято в побуквенных языковых моделях (charRNN, TDCN, побуквенная SNMLM и тп), мы сохраняем свойство выше.

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

Итак, основной вывод: при арифметическом кодировании с использованием полного алфавита мы получаем сохранение порядка несжатых строк при сравнении сжатых представлений.
Tags: базы данных
Subscribe

  • Думал, будет 6. А получилось 7

    Жим лежа гантелей 50 кг - 7 раз. На один раз больше давнишнего. Вешу я сейчас на 6 или 8 кило меньше. Со следующей недели попробую потренировать…

  • Ура!

    Я победил в этой маленькой битве. Описание команд MIPS (не полиморфное) успешно грузится. Я поменял направление хранения цифр с "старшие знаки…

  • Ура!

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments