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

Question

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

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

Таким образом, длина кодировки определяется как l = start + step * 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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

6. Рассчитать значение "stop", ближайшее к "optimStop", которое удовлетворяет условию stop = start + step * i для некоторого целого числа i.

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

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