Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
В топике О невозможности универсального архиватора
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит?
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
Замечательно! Если у нас есть последовательность бит длины n, мы просто n раз применим этот супер-архиватор , и получим последовательность из 0 бит! Всё, получено противоречие с существованием такого архиватора.
Более сложный вопрос: существуют ли несжимаемые слова длины n? То есть существует ли такое слово, что для любой машины Тьюринга, генерирующей это слово кодировка машины будет длиннее. Этот вопрос рассматривался Колмогоровым, и он очень нетривиален.
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
Более короткая цепочка бит обладает меньшим числом комбинаций, чем более длинная. Таким образом какие-то различные входные цепочки бит (исходный файл) должны быть преобразованы в одинаковые выходные цепочки бит (сжатый файл). Очевидно, что корретная распаковка (восстановление исходной цепочки) при этом невозможна.
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
Наверное повторюсь...
Для того, чтобы доказать невозможность такого архиватора (кстати, почему архиватора? -- архивация и сжатие информации разные понятия), достаточно доказать, что мощность множества строк длины L строго больше мощности множества всех строк длины не превыщающей L. Если это так, то получится, что нельзя построить взаимнооднозначное отображение множества строк длины L на множество строк длины не превыщающей L.
Для определенности предположим, что строки кодируются в алфавите с количеством символов равным k (k>1). Тогда мощность множества строк длины L равна k^L, а мощность множества строк длины меньшей L равна k^0+k^1+...+k^(L-1) = (k^L-1)/(k-1).
k^L-1 >= (k^L-1)/(k-1) при k>1
k^L > k^L-1
следовательно k^L > (k^L-1)/(k-1)
В случае с k=2 (т.е. двоичное представление) 2^L > 2^L-1. Это означает, что как ни крути, а одну строку длины L из всех возможных никак не сделать короче.
Впрочем, если отказаться от условия, что по сжатой строке можно было бы однозначно восстановить оригинальную, то можно сжимать как угодно сильно. Хоть до 0.
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Более короткая цепочка бит обладает меньшим числом комбинаций, чем более длинная. Таким образом какие-то различные входные цепочки бит (исходный файл) должны быть преобразованы в одинаковые выходные цепочки бит (сжатый файл). Очевидно, что корретная распаковка (восстановление исходной цепочки) при этом невозможна.
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
АТ>Более короткая цепочка бит обладает меньшим числом комбинаций, чем более длинная. Таким образом какие-то различные входные цепочки бит (исходный файл) должны быть преобразованы в одинаковые выходные цепочки бит (сжатый файл). Очевидно, что корретная распаковка (восстановление исходной цепочки) при этом невозможна.
Позволю себе внести маленькое уточнение (не сочтите за буквоеда). Важно то, что более длинная цепочка бит обладает существенно большим числом комбинаций, а именно
Если предположить, что количество комбинаций combinations(n) не такая быстро растущая функция, то мы уже не придём к противоречию, поскольку цепочка длины n может быть отображена в цепочку произвольной длины i \in {1..n-1}. Если положить L равному минимальной длине цепочки, при которой
то мы вполне можем получить отображение для всех цепочек длины >= L. Правда не для всех цепочек длины меньшей L такой архиватор будет получать сжатую цепочку.
Привет, Real 3L0!
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
Любой архиватор — это инъективная функция, отображающая множество A последовательностей символов в некоторое множество B последовательностей. Поэтому |A| <= |B|.
Отсюда следует, что лучший архиватор на все случаи — это тождественное преобразование.
Стандартные архиваторы основаны обычно на том, что из множества A выделяются наиболее часто встречаемые символы и последовательности символов, которым присваиваются наиболее короткие последовательности множества B. Но всегда остаются последовательности, которые становятся более длинными! Так, для текстовых файлов, для графических или каких-либо других могут наиболее эффективно использоваться различные архиваторы.
Простейший архиватор — это архиватор, построенный на анализе вероятностей появления символов в последовательностях и построении кодировки с помощью алгоритма Шеннона, например.
Допустим, что у нас есть 3 "текстовых" символа 000, 001 и 010, которые встречаются с вероятностью 0.25, и 5 символов, которые встречаются с вероятностью 0.05.
Построим кодировку по алгоритму Шеннона:
000 — 00
001 — 01
010 — 10
011 — 1100
100 — 1101
101 — 1110
110 — 11110
111 — 11111
Средняя длина символа в кодировке будет 0.75 * 2 + 0.15 * 4 + 0.1 * 5 = 2.6 против 3 ранее!
Однако, например, последовательность 110110111 (вероятность ее очень мала и равна 0.000125) перейдет в последовательность из 15 цифр! Но в среднем мы будем иметь 86,7% начальной длины последовательности!
Уменьшение длины последовательностей возможно, но только в вероятностном смысле!
Так, можно самому проанализировать частоту встречаемости символов в некоторой совокупности файлов на компьютере и написать простейший архиватор собственных, например, текстовых файлов. Можно даже написать драйвер: как открывают файл *.txt, он его раскрывает, как сохраняют — архивирует.
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
Здраствуйте!
Вопрос, о котором вы говорити рассматривался еще Клодом Шенноном (наверное, знаете его — основоположник теории информации). Он (или какой то другой ученый, работавший в етой области) ввел понятие информативности сообщения, которая лежыт в пределах от 0 до 1. И теоретический размер заархивированного идеальным архиватором сообщения равен его начальному размеру*коеффициент информативности.
Так что ваше L — переменная, зависящая от сообщения.
Здравствуйте, Кодт, Вы писали:
АТ>Более короткая цепочка бит обладает меньшим числом комбинаций, чем более длинная. Таким образом какие-то различные входные цепочки бит (исходный файл) должны быть преобразованы в одинаковые выходные цепочки бит (сжатый файл). Очевидно, что корретная распаковка (восстановление исходной цепочки) при этом невозможна.
К>Впервые встречаю такое простое изложение. К>
Простое, но не совсем полное ("хоть и ответ правильный"), как заметил LCR. Рассматривать, разумеется, надо суммарное количество разнообразных комбинаций в более коротких битовых цепочках всевозможной длины, а не какой-то конкретной длины, как сделал я изначально.
Если у нас есть битовая цепочка длины L (2^L комбинаций), то суммарное количество комбинаций во всевозможных более коротких цепочках будет равно 2^L — 1, т.е. всего лишь на 1 меньше. Таким образом, если хотя бы одну входную цепочку по условиям задачи разрешается исключить из рассмотрения (типа "не будет такого файла"), то вышеприведенное доказательство невозможности архивации будет уже не применимо.
Здравствуйте, LCR!
L> R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. L> Докажите мне, что нельзя(можно) придумать архиватор, который бы мог L> сжимать файл с любым содержимым, длины меньше(больше) L, как минимум L> на 1 бит? И чему равно L?
L> Замечательно! Если у нас есть последовательность бит длины n, мы L> просто n раз применим этот супер-архиватор , и получим L> последовательность из 0 бит! Всё, получено противоречие с L> существованием такого архиватора.
Так ведь еще есть условие насчет L. Конечно правильнее "длины больше L".
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Уже, наверно, года 4 на досуге решаю одну проблемку. Докажите мне, что нельзя(можно) придумать архиватор, который бы мог сжимать файл с любым содержимым, длины меньше(больше) L, как минимум на 1 бит? И чему равно L?
Я не во все врубился, но вспомнил одну из своих мыслей, которую хотел сделать, но как говориться "языков не знаю", в данном случае математических.
А что если архиватор будет накладывать (например инвертируя биты) какие-нибудь функции, а после этого поле битов станет более однообразным, в файл пишем номер функции, ее параметры, потом жмем стандартным способом и опять накладываем функцию.
Функций может быть несколько, их можно сформулировать для разного типа информации, а еще и подбирать в процессе архивации наиболее эффективные (Долго будет только сжимать, но иногда это не проблема, например зажать файлик видео, а потом распостранять на дискетках).
PLU>Я не во все врубился, но вспомнил одну из своих мыслей, которую хотел сделать, но как говориться "языков не знаю", в данном случае математических.
PLU>А что если архиватор будет накладывать (например инвертируя биты) какие-нибудь функции, а после этого поле битов станет более однообразным, в файл пишем номер функции, ее параметры, потом жмем стандартным способом и опять накладываем функцию.
PLU>Функций может быть несколько, их можно сформулировать для разного типа информации, а еще и подбирать в процессе архивации наиболее эффективные (Долго будет только сжимать, но иногда это не проблема, например зажать файлик видео, а потом распостранять на дискетках).
Есть простое нестрогое опровержение универсального архиватора:
"Файл размером 1Мбит после многократных сжатий упаковали до размера 1 бит.
Вот сам архив:
Привет, mrhru!
M>Есть простое нестрогое опровержение универсального архиватора: M>"Файл размером 1Мбит после многократных сжатий упаковали до размера 1 бит. M>Вот сам архив: M>
M> 1
M>
M>Теперь его надо распаковать."
Идем бьем в морду тому, кто это упаковывал, а затем идем к тому, у кого остался оригинал и слезно умоляем вернуть все как было: "Я принес тебе зубы это подонка!".
I> Здраствуйте! I>Вопрос, о котором вы говорити рассматривался еще Клодом Шенноном (наверное, знаете его — основоположник теории информации). Он (или какой то другой ученый, работавший в етой области) ввел понятие информативности сообщения, которая лежыт в пределах от 0 до 1. И теоретический размер заархивированного идеальным архиватором сообщения равен его начальному размеру*коеффициент информативности. I>Так что ваше L — переменная, зависящая от сообщения.
Здравствуйте, mrhru, Вы писали:
PLU>А что если архиватор будет накладывать (например инвертируя биты) какие-нибудь функции, а после этого поле битов станет более однообразным, в файл пишем номер функции, ее параметры, потом жмем стандартным способом и опять накладываем функцию.
PLU>Функций может быть несколько, их можно сформулировать для разного типа информации, а еще и подбирать в процессе архивации наиболее эффективные (Долго будет только сжимать, но иногда это не проблема, например зажать файлик видео, а потом распостранять на дискетках).
M>Есть простое нестрогое опровержение универсального архиватора: M>"Файл размером 1Мбит после многократных сжатий упаковали до размера 1 бит. M>Вот сам архив: M>
M> 1
M>
M>Теперь его надо распаковать."
Ну ладно, универсального может и не надо пока. Вот если описанный мной способ позволит зжать МП4 еще раз в десять, мне этого до конца жизни хватит. А то вон писали где-то американские математики создали метод упаковки, который в 10 раз сильнее имеющихся. Вот и спи после этого спокойно
, и получим последовательность из 0 бит! Всё, получено противоречие с существованием такого архиватора.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Перекуём баги на фичи!
Apapa.gif)
Хоть один человек вспомнил старика Шеннона.
