@we1

Какие есть алгоритмы сжатия числа?

Есть массив из чисел в 10 бит (то есть максимум 1024 значения). Для его хранения нужно 2 байта * количество чисел. Можно поделить эти числа на 4 и получить возможность хранить числа в однобайтовом массиве. Но тогда потеряются нижние значения - младшие биты. Есть ли алгоритм, который позволяет сохранять "верхние" и "нижние" биты и сжимать "середину" ? Например, числа 1000 и 2 превращаются в 232 и 2 или что-то подобное. Я понимаю, что если есть сразу весь массив, то можно проанализировать "середину" и выкинуть ее, отняв от чисел больше какого-то значения незначимую часть. Но что если массив еще не получен и есть только отдельные числа и для них для всех придется использовать алгоритм без знаний о том, что за результаты будут в конце?
  • Вопрос задан
  • 224 просмотра
Пригласить эксперта
Ответы на вопрос 5
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Можно хранить в битовом массиве, тогда потребуется ровно 10 бит для каждого числа. Каждые 4 числа занимают 5 байт.

Будет небольшое замедление при записи и считывании чисел из такого массива (Надо найти смещение, прочитать 2 каких-то байта, отбросить лишние биты)

Возможно последний байт в массиве не до конца использован (+6 лишних бит), когда как в текущем решении у вас лишние 6 бит на каждое число.
Ответ написан
hint000
@hint000
у админа три руки
Есть ли алгоритм, который позволяет сохранять "верхние" и "нижние" биты и сжимать "середину" ?
Довольно сумбурно выражена мысль, но дайте я догадаюсь:
Чтобы у маленьких чисел не терялись младшие биты, а у больших не терялись старшие?
Если я вас правильно понял, то поздравляю, вы изобрели числа с плавающей точкой.
Ответ написан
solotony
@solotony
покоряю пик Балмера
- если числа между собой не сильно различаются - храните их разницу
- если числа повторяются много раз - положите их в словарь и храните индекс
Ответ написан
gbg
@gbg
Любые ответы на любые вопросы
Обычные алгоритмы сжатия чем не годны? Сжатие Хаффмана хотите переизобрести?
Ответ написан
Adamos
@Adamos
Ваша проблема сформулирована как задача о семиугольном треугольнике.
Лучше сформулировать более общую проблему - что за числа, как их нужно обрабатывать - и, возможно, вам подскажут более адекватное решение.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы