Теория: Алгоритм сжатия, который делает некоторые файлы меньшими, но ни одно большее?
В теории (теорией, которую я имею в виду Стандарт SQL ) говорится, что то, ГДЕ ограничивает набор результатов перед возвращением строк и НАЛИЧИЕМ, ограничивает набор результатов после обеспечения всех строк. Таким образом, ГДЕ быстрее. По Стандарту SQL совместимый DBMSs в этом отношении, только используйте НАЛИЧИЕ, где Вы не можете поставить условие ГДЕ (как вычисляемые столбцы в некотором RDBMSs.)
можно просто видеть план выполнения относительно обоих и проверить на себя, ничто не разобьет это (измерение для Вашего определенного запроса в Вашей определенной среде с Вашими данными.)
3 ответа
По принципу «дырки», для строки из 10 бит у вас есть 1024 возможных входа, и вам нужно отобразить 9 бит или меньше, поэтому имеется <1024 выходов.
Это гарантирует, что либо алгоритм имеет коллизии (сжатие с потерями), либо в какой-то момент выбирает возврат неизмененного ввода в качестве вывода.
В последнем случае вы не можете определить, как распаковать произвольную строку битов. (Это может быть неизмененный ввод или сжатый вывод из более крупной битовой строки).
-> Невозможно.
Just a slight clarification of RJFalconer's post...
You only have to have some files becoming smaller, so the claim that a string of 10 bits has to map to 9 bits or fewer isn't quite right. In particular, if someone proposed such a compression mechanism it could map all strings of 10 bits or fewer to exactly the same output (i.e. an identity transformation).
However, we are told that there is at least one file which does become smaller. Without loss of generality, consider that to start with x bits and end up as y bits, where y is strictly less than x.
Now consider the domain of "files with y bits or fewer", which has 2y+1-1 bit strings (including the empty one). In order for none of those to result in a bigger file, each has to map to a bit string in the same domain, i.e. 2y+1-1 compressed files. However, we already know that the initial string of length x bits compresses to one of those values - leaving only 2y+1-2 possible values.
At this point the pigeon hole principle comes in - you clearly can't map 2y+1-1 inputs to 2y+1-2 outputs without repeating an output, which violates the reversibility of compression.
a) impossible
If you have a file that can not be compressed further, you still have to add the information whether it has been compressed or not, so in that case the file would have to grow.