guest Весьма благодарен за столь подробное заявление.
Опровергаю Вашу критику моего алгоритма.
1. Сей алгоритм "сжимает" не строки длины N, а строки длины N*2^N;Верно. Как я неоднократно уже заявлял, мой алгоритм сжимает ВСЕ строки длиной N – набор данных из ВСЕХ строк длиной N общей длины N*2^N. Этим алгоритмом я пытаюсь опровергнуть заявление Евгения о невозможности сжатия ВСЕХ строк длиной N. Я ни разу не заявлял, что имею алгоритм, который сжимает КАЖДУЮ отдельную строку длиной N. В тексте от 18.01 08.17 я сделал предположение о возможности сжатия КАЖДОЙ строки длиной N, если они сжимаются не по отдельности, а в наборе данных. Могу подтвердить это алгоритмом, с той разницей, что этот алгоритм не сожмет произвольный набор данных, а лишь некоторые из них. То есть он не универсальный (иначе я бы сжал им что угодно), а применим для отдельных случаев.
2. Алгоритм "сжимает" не все 2^(N*2^N) строки длины N*2^N, а только (2^N)! из них;Верно. Наборов данных, содержащих ВСЕ строки длиной N, как раз (2^N)!
4. Алгоритм сжимает не любые (2^N)! строк длины N*2^N, а только те, что являются перестановками всех 2^N строк длины NВерно. По тем же причинам.
3. "Сжатием" считается случай, когда длина выходной последовательности алгоритма меньше log2((2^N)!), Неверно. Давайте не будем усложнять. Сжатием строки, состоящей из ВСЕХ строк длиной N бит и общей длиной N*2^N бит, считается случай, когда длина выходной последовательности меньше N*2^N бит. Не нужен здесь логарифм.
что не выполняется никогда а уже начиная с N=3 ("сжатая" по этому алгоритму последовательнось в этом случае будет длиной 17 бит, в то время как число перестановок 8-ми элеменов равно 40320 и меньше, чем 2^16) не достигается и равенства. Пусть за нас факты говорят.
N=3 бита
Первая итерация
011 101 110 000 010 100 001 111 - Набор данных
000 001 010 011 100 101 110 111 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных первая строка - 000
это 4 вхождение в из 8 возможных - 011
исключаем его из набора данных
2 итерация
011 101 110 010 100 001 111 - Набор данных
00 010 011 100 101 110 111 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных 2 строка - 001
это 7 вхождение в из 7 возможных -110
исключаем его из набора данных
3 итерация
011 101 110 010 100 111 - Набор данных
00 01 100 101 110 111 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных 3 строка - 010
это 4 вхождение в из 6 возможных -110
исключаем его из набора данных
4 итерация
011 101 110 100 111 - Набор данных
00 01 10 110 111 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных 4 строка - 011
это 1 вхождение в из 5 возможных -00
исключаем его из набора данных
5 итерация
101 110 100 111 - Набор данных
00 01 10 11 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных 5 строка - 100
это 3 вхождение в из 4 возможных -10
исключаем его из набора данных
6 итерация
101 110 111 - Набор данных
0 10 11 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных 6 строка - 101
это 1 вхождение в из 3 возможных - 0
исключаем его из набора данных
6 итерация
101 110 111 - Набор данных
0 10 11 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных 6 строка - 101
это 1 вхождение в из 3 возможных - 0
исключаем его из набора данных
7 итерация
110 111 - Набор данных
0 1 - Вхождения каждой строки длиной 3 бита в набор данных
записываем, где находится в наборе данных 7 строка - 110
это 1 вхождение в из 2 возможных - 0
исключаем его из набора данных
Итого: выходная строка 011 110 110 00 10 0 0 - 15 бит< N*2^N=3*2^3=24 бита
Прошу модератора с пониманием отнестись, если мне придется привести то же самое для N=4.
Откуда Вы, guest , взяли число 40320, я не знаю. При N=8 бит, N*2^N=2048 бит. Этот набор данных жмется примерно до 1600 бит
4. Таким образом, простая нумерация перестановок уже начиная с N=3 будет более эффективна. Причем, даже в этом случае ни о каком "сжатии" нет и речи.
Что ж, мой алгоритм – один из способов нумерации (2^N)! строк. Однако, он эффективен, не требует предварительной фиксации отношений "строка-ее номер" и проверки их при исполнении алгоритма, поэтому он оптимален в общем случае. А сжатие я показал.
Теперь о сжатии вообще и фактах из теории представления двоичных функций.
Все это очень интересно.
Но. Боюсь, что Ваши аргументы действительны в тех же координатах, что и у других уважаемых участников дискуссии. В Абстрактных данных. Вы ввели еще один показатель невозможности сжатия – шенноновскую сложность. Я уже заявлял о неприменимости разных показателей к возможности сжатия реальных данных. Пока меня никто не опроверг (по крайней мере, последнее слово сказано мной). Любой набор данных (строка) с max шенноновской сложностью может входить в другой набор данных или разбит на части, где эта сложность будет меньшей, и набор данных может быть сжат. Не согласны? Ответьте на вопрос: как осуществлять арифметические операции с шенноновской сложностью?
Реальные архиваторы работают с достаточно узкими классами последовательностей, причем такими, которые имеют заведомо малую сложность. В основном, - используются статистические закономерности в этих последовательностях
Верно. А для новых архиваторов нужно найти новые закономерности.
Вы способны подсчитать шенноновскую сложность функции, порождающей двоичное число, представляющее собой Ваш диск С? Предполагаю, она достаточна велика. Почему же реальный архиватор способен сжать диск?
доселе не известно общее описание (для произвольного n) ни одной такой функции
Я считаю, все, что не запрещено, - разрешено. Раз я не вижу доказательств невозможности сжатия – сжатие возможно.
)
Разве программа, печатающая 1024 буквы 'X' будет длинней этой строки? Ты ж сказал, что это длина минимальной строки.
Против Колмогорова не попрешь.
Не хочу сказать, что сгенерить предельно сложную последовательность не сложно - это весьма непросто (хотя, думаю quest это удастся), но вот сжать ее хотя бы на сколько-либо (даже если она будет не идеальной) будет ничуть не проще. Попробуйте, для тривиального опыта, зажать какой-либо файл хотя бы каким-либо архиватором при максимальном сжатии (я попробовал RARом) - и проанализируйте ее характеристики - и вы поймете что получившаяся последовательность УЖЕ приближается к шуму и чтобы что-либо оттуда выкинуть - надо ОЧЕНЬ постараться. 
ОК. Запускаем его - на месте наш исходник один в один! Невозможно? Легко!
Не со зла