Как можно вычислить оптимальные параметры для схемы кодирования «старт-шаг-стоп»?

Question

Код «старт-шаг-стоп» — это метод сжатия данных, который используется для сжатия относительно небольших чисел.

Код работает следующим образом:Он имеет три параметра: старт, шаг и стоп.Start определяет количество битов, используемых для вычисления первых нескольких чисел.Шаг определяет, сколько бит добавить к кодировке, когда они закончатся, а остановка определяет максимальное количество бит, используемых для кодирования числа.

Таким образом, длина кодировки определяется как l = начало + шаг * i.

Значение «i» конкретного кода кодируется с использованием унарного кода.То есть ряд битов 1, за которыми следует завершающий бит 0.Если мы достигли остановки, мы можем отбросить завершающий 0 бит.Если я равен нулю, мы записываем только 0 бит.

Таким образом, код «старт-шаг-стоп» (1, 2, 5) будет работать следующим образом:

Значение 0, закодированное как:0 0
Значение 1, закодированное как:0 1
Значение 2, закодированное как:10 000
Значение 9, закодированное как:10 111
Значение 10, закодированное как:11 00000
Значение 41, закодированное как:11 11111

Итак, если файл содержит несколько чисел, как мы можем вычислить оптимальные коды начала, шага и остановки для этого файла?Оптимальные параметры определяются как те, которые приводят к наибольшей степени сжатия.

Answer 1

Эти коды «старт-шаг-стоп» выглядят как другой способ вызова. Коды Хаффмана.См. базовая техника для описания псевдокода их расчета.

По сути, это то, что делает алгоритм:

Прежде чем начать кодирование Хаффмана, вам необходимо собрать статистику каждого символа, который вы будете сжимать (их общую частоту в файле для сжатия).

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

В конце кодирования Хаффмана вашим начальным значением будет глубина самого мелкого листового узла, ваш шаг всегда будет 1 (логически это имеет смысл, зачем вам заставлять больше битов, чем вам нужно, просто добавляйте по одному за раз) и вашим стоп-значением будет глубина самого глубокого листового узла.

Если статистика частоты не отсортирована, для этого потребуется O(nlog n), если она отсортирована по частоте, это можно сделать за O(n).

Коды Хаффмана гарантированно имеют лучшее среднее сжатие для этого типа кодирования:

Хаффман смог разработать наиболее эффективный метод сжатия этого типа:Никакое другое отображение индивидуальных символов источника с уникальными строками битов не даст меньшего среднего размера выходного монтажа, когда фактические частоты символов согласуются с теми, которые используются для создания кода.

Это должно помочь вам реализовать идеальное решение вашей проблемы.

Редактировать: Хотя это похоже, это не то, что искал ОП.

Этот научная статья Автор этих кодов описывает обобщение кодов «старт-шаг-стоп», кодов «старт-стоп».Однако автор кратко описывает, как добиться оптимального старта-шага-остановки ближе к концу раздела 2.Он предполагает использование статистической случайной величины или подбор наилучшей комбинации методом грубой силы.Без какого-либо предварительного знания файла алгоритм равен O((log n)^3).

Надеюсь это поможет.

Answer 2

Подход, который я использовал, представлял собой простое решение методом грубой силы.Алгоритм следовал следующим основным шагам:

1. Подсчитайте частоту каждого числа в файле.В том же проходе вычислите общее количество чисел в файле и определите наибольшее число как maxNumber.

2. Вычислите вероятность каждого числа как его частоту, деленную на общее количество чисел в файле.

3. Определите «optimalStop» равным log2(maxNumber).Это идеальное количество битов, которое следует использовать для представления maxNumber, как в теории информации Шеннона, и, следовательно, разумная оценка оптимального максимального количества битов, используемых при кодировании определенного числа.

4. Для каждого значения «start» от 1 до «optimalStop» повторите шаги 5–7:

5. Для каждого значения «шага» от 1 до («optimalStop» — «start»)/2 повторите шаги 6 и 7:

6. Вычислите значение «stop», ближайшее к «optimalStop», которое удовлетворяет условию stop = start + шаг * i для некоторого целого числа i.

7. Вычислите среднее количество битов, которые будут использоваться при этом кодировании.Это можно рассчитать как вероятность каждого числа, умноженную на его битовую длину в данной кодировке.

8. Выберите кодировку с наименьшим средним количеством бит.