Давайте посмотрим на тривиальный подход, который во многих случаях может быть оптимальным:
Он хранил бы:
- Количество элементов в диапазоне (с 31 битом, поскольку списки на Яве ограничены 2 31-1 элементами).
- За ним следует 1 бит для каждого индекса с указанием того, присутствует ли данный элемент в наборе или нет.
Это реализация первой версии фрактального компрессора для хранения данных из делений и слияний триангуляции.
Хотя это и не было оптимальным, так как по мере итерации делений количество элементов, которые должны храниться, сократилось, став очень небольшим процентом от общего числа, и в этом случае тривиальное кодирование может быть существенно улучшено.
Теперь цель состоит в том, чтобы усовершенствовать это тривиальное кодирование, посмотреть, можно ли получить более сжатое кодирование с точки зрения числа бит.
Первый подход : В тех случаях, когда количество элементов в наборе значительно меньше размера диапазона, мы можем рассмотреть возможность хранения имеющихся индексов.
В этом случае используется следующее:
- 31 бит для числа элементов в диапазоне.
- 31 бит для числа элементов, присутствующих в наборе.
- 31 бит * число элементов, присутствующих в наборе.
Второй подход :: Улучшается количество бит на один хранимый элемент:
- 31 бит для числа элементов в диапазоне. Количество битов самого крупного элемента в диапазоне ( numBitsElem ) будет рассчитываться.
- 5 битов на хранение numBitsElem ..................................................................Таким образом, если бы число элементов в диапазоне было 1023, то 10 было бы сохранено в этих 5 битах.
- numBitsElem биты, чтобы сохранить количество элементов в Комплексе.
- numBitsElem биты * число элементов, присутствующих в Комплексе.
Ну, понемногу мы приближаемся к лучшему кодированию...
Третье приближение Мы понимаем, что если мы сортируем набор в порядке восхождения, дельта (различия между последовательными элементами) могут быть закодированы меньшими битами, чем абсолютный элемент диапазона:
- 31 бит для числа элементов в диапазоне.
- Мы вычисляем маленький numBitsElem, чтобы кодировать элемент.Мы также вычисляем список дельт (список различий между последовательными элементами сортированного перечня элементов в наборе).И наконец, мы также вычисляем numBitsDelta
- 5 битов на хранение numBitsElem ..................................................................
- 5 битов на хранение numBitsDelta ..................................................................
- numBitsElem биты, чтобы сохранить количество элементов в Комплексе.
- numBitsDelta биты * число элементов в Комплексе.
Похоже, мы уже достигли оптимального кодирования, верно?
Давайте продолжим...
Четвертое приближение . Мы сосредоточимся на том факте, что может быть гораздо больше мелких дельт и, возможно, лишь несколько более крупных дельт, которые сломают ". numBitsDelta ".
В этих условиях мы могли бы найти " numOptimBitsDelta "меньший по сравнению с максимальным" num MaxBitsDelta ", которая, в свою очередь, меньше или равна..." numBitsElem ".
Но как мы кодируем дельта-элемент, который превышает... numOptimBitsDelta "?
Ну... так как дельта никогда не будет 0 (в наборе нет повторяющихся элементов), мы можем использовать значение 0, чтобы показать, что это особое значение.
И за этим 0 будет следовать значение дельты, но на этот раз закодировано " num MaxBitsDelta ".Общее число битов можно рассчитать следующим образом:
- 31 бит для числа элементов в диапазоне. Мы вычисляем наименьшее numBitsElem Мы также вычисляем список дельт (перечень различий между последовательными элементами заданного перечня элементов в Комплексе).
- 31 бит, чтобы сохранить количество элементов в Комплексе.
- 5 битов на хранение numOptimBitsDelta ..................................................................
- 5 битов на хранение num MaxBitsDelta ..................................................................
- numOptimBitsDelta биты * число элементов в Комплексе.
- num MaxBitsDelta биты * количество дельт, превышающих numOptimBitsDelta ..................................................................
Мы уже достигли оптимального кодирования?
Пятое приближение Ну... раз уж мы уже запрограммировали все это...Мы могли бы подумать о дополнительной ситуации...Возможно ли, что кодирование дополнения набора одним и тем же алгоритмом позволит получить более сжатые результаты?
Добавление набора понимается как другой набор, отделенный от оригинального, чей союз с оригинальным набором является всем диапазоном.
То есть, дополнительный набор будет содержать все элементы диапазона, отсутствующие в первоначальном наборе, и ни один из элементов в первоначальном наборе.
Красота в том, что из набора очень легко получить дополнительный набор, и поэтому мы могли бы получить оригинальный набор, закодировав дополнительный набор.
Очевидное приложение - набор, который содержит все элементы диапазона, кроме одного или нескольких...
Ну... если мы храним только отсутствующие (дополнительный набор), он может храниться в гораздо меньшем размере, так?
Кодирование в этом случае может быть вот так:
- 31 бит для числа элементов в диапазоне. Мы вычисляем наименьшее numBitsElem Мы также вычисляем список дельт (перечень различий между последовательными элементами заданного перечня элементов в Комплексе).
- 1 кусочек, чтобы сохранить, сохраняем ли мы оригинальный набор или дополнение.Это лишний кусочек.
- 31 бит, чтобы сохранить количество элементов в Комплексе.
- 5 битов на хранение numOptimBitsDelta ..................................................................
- 5 битов на хранение num MaxBitsDelta ..................................................................
- numOptimBitsDelta биты * число элементов в Комплексе.
- num MaxBitsDelta биты * количество дельт, превышающих numOptimBitsDelta , в местах, где они появляются.
Ну... теперь мы разговариваем.
Так вот где я застрял... но я знаю, что если все эти чудеса можно сделать, то что не может быть сделано путем поиска других моделей, или просто с помощью беспотерянного компрессора, как Zip или 7z...
Это подождет, на задней горелке в следующий раз...
