Как сжать массив случайных натуральных чисел в определенном диапазоне? - PullRequest
0 голосов
/ 01 апреля 2019

Я хочу сжать массив, состоящий из примерно 10 ^ 5 случайных чисел в диапазоне от 0 до 2 ^ 15. Целые числа не отсортированы, и мне нужно сжать их без потерь.

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

Есть ли предложенные алгоритмы для этого?

1 Ответ

1 голос
/ 01 апреля 2019

При условии, что вам не нужно сохранять исходный порядок, вместо того, чтобы передавать сами цифры, пропустите счет. Если они имеют нормальное распределение, можно ожидать, что каждое число будет повторяться 3 или 4 раза. С 3 битами на число мы можем сосчитать до 7. Вы можете сделать массив из 2 ^ 15 * 3 бит, и каждые 3 бита установить счетчик этого числа. Для обработки экстремальных случаев, которые имеют более 7, мы также можем отправить список номеров и их количество для этих случаев. Затем вы можете прочитать массив из 3 битов и перезаписать его дополнительной информацией для числа больше 7.

...