Есть идея алгоритма сжатия данных.

[Macros]

Если взять байт и разбить его на кластеры по два бита:
01.10.00.11
то каждый кластер можно закодировать одним битом плюс ключ к этому биту:
ключ_0 0=01,1=10
ключ_1 0=00,1=11
Чем дальше будет находиться один ключ от другого,тем больше степень сжатия.
Можно еще ввести корректор ключа.Например,ключ_0 не 0=01,1=10,а 0=10,1=11,какая комбинация чаще встречается.
Ключевой момент идеи:как программе декомпрессору указать где ключ,а где данные?
По моему мнению есть только один способ.Запаковывать в пакеты.Например:первый бит указывает ключ,
следующие несколько бит указывают размер пакета(например 4 бита=30 кластеров=3.75байт),остальные код.
Но при таком способе сжатый файл может получиться больше оригинала.
И не понятно может ли машина интерпретировать,что этот бит отвечает за это,а этот за то?

Кто что думает по этому поводу?

[veniside]

Хаффман уже давно всё это придумал и умер.

[JTG]

Автор http://programmersforum.ru/showthread.php?p=722544 вернулся?

[Macros]

Сообщение от JTG

Автор http://programmersforum.ru/showthread.php?p=722544 вернулся?

Тот фуфлагон принцип работы алгоритма не выкладывал(и не мог).И чего это у этих статей общего?

Это просто идея,с кодом Хаффмана она ничего общего не имеет.(((((((

[Tronix]

Я когда-то пытался так: http://programmersforum.ru/showthread.php?t=113859
В кратце - нихрена ессно не получилось ))

[Macros]

Сообщение от Tronix

Я когда-то пытался так: http://programmersforum.ru/showthread.php?t=113859
В кратце - нихрена ессно не получилось ))

Читали.Можно просто делить байт на два.Тогда с каждым делением старший бит в байте гарантированно всегда будет нулем.А если известно,что он всегда будет нулем,значит его можно сократить(например присоединить следующий байт).Правда все упирается в одно но:при умножении на два нужен бит четности.Если число было четным-просто *2,если не четным *2+1.Следовательно эффективность ноль.))

[ZonoID]

Я много писал по этому поводу на другом известном ресурсе gamedev.ru
Сразу скажу чем закончилось - осмеяли и отправили учить матан.

Сообщение от Macros

Если взять байт и разбить его на кластеры по два бита:
01.10.00.11
то каждый кластер можно закодировать одним битом плюс ключ к этому биту:
ключ_0 0=01,1=10
ключ_1 0=00,1=11
Чем дальше будет находиться один ключ от другого,тем больше степень сжатия.
Можно еще ввести корректор ключа.Например,ключ_0 не 0=01,1=10,а 0=10,1=11,какая комбинация чаще встречается.
.....
Кто что думает по этому поводу?

В чем смысл твоей идеи? Не сложно догадаться - прогнать через алгоритм один и тот же архивчик много раз. То есть многопроходный архиватор. (абсолютный архиватор, не зависимо от размеров входного массива должен выдать на выходе один едиственный байт)
Я разработал около тридцати подобных алгоритмов, некоторые "почти" работоспособны. Два из них - точно работоспособны...
Однако КПД подобных алгоритмов чрезвычайно низок, что-то около 1 - 1,5% сжатия за один проход. Причем не каждый массив подходит для сжатия. Конечно можно любой массив обрабатывать и если он не сжимается, то метить стоп-битом, то есть минимальное увеличение массива компенсируется сжатием других блоков массива.

Дам несколько советов.
1. Начни мыслить абстрактно. Отодвинь проблему дальше от себя, охвати взглядом и попытайся прочувствовать каждый бит.
2. Любое сжатие "без потерь" требует дополнительного массива "для восстановления". Чем меньше размер кванта (блока массива) тем больших размеров получится массив "для восстановления". В твоем случае - они равны. Чем больше размер кванта - тем меньше коэффициент сжатия. В идеале, алгоритм гарантированно работает тогда, когда сжатие минимально или отсутствует. Однако, ничто не мешает использовать "обработчики" исходного массива, которые изменяют энтропию, "подготавливают" массив к сжатию.
3. Разделять данные и массив "для восстановления" можно разными способами, главное не использовать "принцип хаффмана" )
Менять разрядность машинного слова, не используя стоп-байт для разделения одного слова от другого. Как? Долго писать...
4. Помни, что как только обнаружится работоспособный алгоритм (а таких много) думай о том, что будет с данными дальше? Пожал ты их один раз - получил 3% сжатие (смысла от него сам понимаешь немного), при втором проходе сжатия уже нет (энтропия) при третьем - увеличение. Почему так? Как изменить энтропию? Думай!
5. Условно можно разделить на три части. Немного высокопарно (и возможно бессмысленно прозвучит) но почитай и подумай, потом поймешь...
Отсутствие избыточности - тоже избыточность. Т.к. нарушена равновероятность выпадения определенных байт, а потому массив может быть (пункт 2) сжат, простым методом подмены (хаффман) часто встречающихся байт, редко встречающимися. Пересчет блока и вычленение отсутствующих байт с пересчетом оставшихся и выводом только номера варианта.
6. Самое страшное, это "статистическое равновесие"
7. Массив для восстановления должен обрабатываться и сжиматься тоже и одновременно с исходным массивом.

[ZonoID]

Вот тебе одна "гениальная" идея для осмысления:
Сравни два числа: 10000010 и 11101101
Вроде числа как числа... Однако "на глазок" видно, что первое "легче" второго. У второго больше единиц.
А что если инвертировать второе число не трогая первое (массив "для восстановления" из двух бит 01, 0 - не трогаем, 1- инвертируем)
10000010 и 00010010 + 01
Смотри внимательно на получившиеся числа, не слишком ли много нулей?
Простой метод не работает, однако объясню как делается:
Обработав массив мы нарушили энтропию. А значит наш массив можно сжать. Квантуем оба числа по 2 бита.
10 00 00 10 и 00 01 00 10 +01
Выбросим лишние 00 (массив для восстановления 0 - нет, 1 - есть 00)
10 (0) (1) (1) 10 (0) и (1) 01 (0) (1) 10 (0) +01
1010 +0110 и 0110 + 1010 + 01
Итог: +2 бита. Алгоритм не работает!
Причина в статистическом равновесии... )
----------------
Более сложный метод.
Обычное кодирование для четырех битового слова выглядит так:
0000 - 0
0001 - 1
0010 - 2
0011 - 3
0100 - 4
0101 - 5
0110 - 6
0111 - 7
1000 - 8
1001 - 9
1010 - 10
1011 - 11
1100 - 12
1101 - 13
1110 - 14
1111 - 15

Выпишем все двухбитовые комбинации, что бы понимать как выглядит энтропия.

00 - 8
01 - 8
10 - 8
11 - 8

После нашей обработки, массив будет выглядеть так:

0000 - 0
0001 - 1
0010 - 2
0011 - 3
0100 - 4
0101 - 5
0110 - 6
1000 - 7
1000 - 8
1001 - 9
1010 - 10
1011 - 11
1100 - 12
0010 - 13
0001 - 14
0000 - 15

Выпишем все двухбитовые комбинации, что бы понимать как изменилась энтропия.

00 - 13
01 - 7
10 - 9
11 - 3

Нетрудно понять, что всю "картинку" портят именно 11. Вероятность нарушена, но недостаточно.
Необходима еще одна обработка массива, что бы отделить "котлеты от мух".
Нам нужно понимать, что просходит.

Вот как это выглядит:

0000 - легкий байт (число нулей больше чем единиц)
0001 - легкий байт
0010 - легкий байт
0100 - легкий байт
1000 - легкий байт

0011 - равновесный байт (число нулей равно числу единиц, что обрабатывай, что нет "вес" не изменится)
0101 - равновесный байт
0110 - равновесный байт
1001 - равновесный байт
1010 - равновесный байт
1100 - равновесный байт

1110 - тяжелый байт, инвертируем и получаем - 0001
1101 - тяжелый байт, инвертируем и получаем - 0010
1011 - тяжелый байт, инвертируем и получаем - 0100
0111 - тяжелый байт, инвертируем и получаем - 1000
1111 - тяжелый байт, инвертируем и получаем - 0000

Итак. Статистически:
"легких" - 5
"тяжелых" - 5
"равновесных" - 6

Вот теперь понятно, что бы наш алгоритм сработал, недостаточно разделить массив на две части легкие/тяжелые.
Необходимо исключить рановесные.

Сможешь придумать КАК это сделать? Нобелевка твоя будет...

----------------------------------------

// реклама запрещена

[Macros]

Как тебе не лень было столько текста набирать???




Молодец и сайт свой пропиарил.Для этого и регистрировался?

[mutabor]

Да давно уже придумали алгоритм с отрицательной степенью сжатия, сжимает до минус бесконечности