Алгоритмическое охлаждение: различия между версиями

Имея на входе битовую строку длины n, распределение вероятностей которой известно и достаточно далеко от равномерного, можно использовать сжатие данных для генерации более короткой строки, скажем, из m бит, в которой энтропия каждого бита будет гораздо ближе к единице. В качестве простого примера рассмотрим строку из четырех бит со следующим распределением: p0001 = p0010 = p0100 = p1000 = 1/4, где pi – вероятность строки i. Вероятность любого другого значения строки равна нулю, так что в сумме вероятности равны единице. Затем битовая строка может быть сжата с помощью алгоритма сжатия без потерь в 2-битовую строку, содержащую двоичное описание местоположения «1» в четырех вышеупомянутых строках. Поскольку вероятности всех этих строк равны нулю, можно также представить себе аналогичный процесс, который генерирует выходную строку той же длины n, что и входная, но при этом такую, что с помощью алгоритма сжатия на месте без потерь энтропия преобразуется в последние два бита. Например, логические вентили, оперирующие битами, могут выполнять перестановку 0001 ! 0000, 0010 ! 0001, 0100 ! 0010 и 1000 ! 0011, тогда как другие входные строки преобразуются в выходные строки, в которых два старших значащих бита не равны нулю; например, 1100 ! 1010. Легко заметить, что энтропия теперь полностью сосредоточена на двух наименьших значащих битах, что полезно при сжатии данных, в то время как два наибольших значащих бита имеют нулевую энтропию.