| | | | | | | | | | | | | | | | | | | | | Ч | т | о | | е | с | т | ь | | т | е | о | р | е | т | и | ч | е | с | к | и | й | | п | р | е | д | е | л | | с | ж | а | т | и | я | | ? | | | | | | | | | | | | | | | | | | | | |
| |
| Этот вопрос может быть понят в двух различных смыслах: |
| (a) Для данного копрессора/декомпрессора, какова лучшая возможная степень |
| сжатия без потерь для произвольной строки (последовательности байт), поданной |
| на вход ? |
| (b) Для данной строки, каков лучший копрессор/декомпрессор, сжимающий без |
| потерь ? |
| Для случая (a), вопрос в основном бессмысленен, т.к. специфичный компрессор |
| может сжимать один большой файл в один бит и увеличивать все другие файлы |
| всего на один бит. Не существует компрессора без потерь, гарантированно |
| сжимающего все возможные подаваемы на вход файлы. Если он сжимает некоторые |
| файлы, то он должен увелиичать другие. Это может быть доказано простым |
| подсчетом (см. | [9] | ). В случае (a) размер декомпрессора не учитывается в |
| определении коэффициента сжатия, т.к. декомпрессор фиксирован и может |
| разжимать произвольное число файлов произвольного размера. |
| Для случая (b), конечно необходимо учитывать размер декомпрессора. Задача |
| может быть перефразирована как "Какова наименьшая программа P, воспроизводящая |
| строку S?". Размер такой программы называется Колмогоровой сложностью строки |
| S. Некоторые (в действительности большинство) строки совсем не сжимаемы, любой |
| программой: наименьшее представление строки есть сама строка. Другими словами, |
| выход впсевдо-случайного генератора чисел может быть сильно сжимаем, т.к. |
| достаточно знать параметры и инициализатор генератора для воспроизведения |
| произвольно длинной последовательности. |
| Ссылка: "An Introduction to Kolmogorov Complexity and its Applications", |
| Ming Li and Paul Vitanyi, 2nd edition, Springer-Verlag, ISBN 0-387-94868-6 |
| www.cwi.nl | |
| Если вы не хотите читать целую книгу, рекомендуется прекрасная лекция |
| Чэйтина (G. J. Chaitin) "Randomness & Complexity in Pure Mathematics": |
| www.cs.auckland.ac.nz | Десятичное и двоичное представление Чэйтиновского числа |
| Omega являются примерами несжимаемых строк. Больше статей находится на |
| www.cs.auckland.ac.nz | |
| |