Что-то вроде перевернутого генератора случайных чисел

Question

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

Предположим, у меня есть список несортированных уникальных номеров из неизвестного источника, длина обычно составляет от 255 до 512 с диапазоном от 0 до 512.
Интересно, существует ли какой-нибудь алгоритм, который считывает данные и возвращает что-то вроде начального числа, который я могу использовать для создания списка, который будет как-то близок к оригиналу, но с некоторой степенью ошибки.

Например

• оригинальный список

  {5, 13, 25, 33, 3, 10}
  

• обновленный список

  {4, 10, 30, 30, 5, 5} or {8, 20, 20, 35, 5, 9} //and so on
  

У этой проблемы есть имя, и есть ли алгоритм, который может делать то, что я только что описал?
Это так же, как метод Монте-Карло, потому что, насколько я понимаю, это не так.

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

Я попытался решить эту проблему, используя простой 16-битный ГСЧ и перебор всех возможных значений, сравнивая их с исходным списком, и выбрал значение с минимальной разницей, но я думаю, что этот способ довольно тупой и неэффективный.,

Answer 1

Это действительно сжатие с потерями.

Вы не говорите нам диапазон значений в списке. Из предоставленных вами образцов мы можем экстраполировать, чтобы они насчитывали не менее 6 битов (от 0 до 63). В общей сложности вам нужно сжать от 0 до 3072 бит.

Если эти последовательности не имеют специального свойства и кажутся случайными, я сомневаюсь, что есть какой-либо способ добиться значительного сжатия. Подумайте, что вероятность того, что произвольная последовательность будет сопоставлена ​​из 32-разрядного начального числа, равна 2^32,2^(-3072)=7,10^(-916), т. Е. Меньше, чем бесконечно малая. Если вы допускаете ошибку 10% для каждого значения, вероятность совпадения составляет 2^32.0.1^512=4.10^(-503).

Тривиальный способ сжатия с точностью 12,5% состоит в том, чтобы избавиться от трех младших битов каждого значения, что приводит к 50% экономии (1536 бит), но я сомневаюсь, что это то, что вы ищете.

Было бы полезно измерить энтропию последовательностей http://en.wikipedia.org/wiki/Entropy_%28information_theory%29 и / или возможные корреляции между значениями. Это может быть сделано путем построения всех (V, Vi+1) пар или тройок (Vi, Vi+1, Vi+2) и поиска шаблонов.