Алгоритм сжатия информации 2:1 (2 стр)

Не по теме, но вспомнился just cause 2.
1gb установка = 8gb распаковка...

Mikle
> Сожми файл, заполненный случайными числами, хотя бы на 1%.
Абсолютно без разницы, какие данные находятся в файле. Алгоритм работает с битами, а не с байтами или более объёмными единицами информации.

Pilix
Ну так покажи пример)

Ты попал на gamedev форум, парень, здесь принято предоставлять доказательства.

Monstradamus
> Ну так покажи пример)
Разумеется, но всему своё время. Текущая версия алгоритма несьедобна для всех кроме меня. Впереди ещё исследования частных случаев (чтобы выбросить 4 огромные таблицы), улучшение алгоритма определения предела, муторная оптимизация всего кода и ещё то, о чём я, вероятно, не догадываюсь.

Pilix
> Вывод: 7 троллей.

Так сожми их до 3.5 троллей =) Затем до 1.75 =) Хотя это степень сжатия троллей надо смотреть :) Вдруг попытка сжатия тролля ведет к увеличению его толстоты :D

Ну тк а как тут не троллить? Написано "алгоритм", а об алгоритме ни слова и какие-то магические характеристики типа универсального сжатия чего угодно в 2 раза. Как я уже говорил, подобные идеи тут были, только толку от них ..

Pilix
> чтобы выбросить 4 огромные таблицы

Насколько они огромны по отношению к размеру исходных данных ?

Показываю наглядный пример:

32-х битное число 0 (напоминаю, работаем с битами):
00000000 00000000 00000000 0000000

После первой итерации мы получаем сжатие 2:1
00000000 00000000

После второй итерации мы опять получаем сжатие 2:1
00000000

После третьей итерации мы опять получаем сжатие 2:1
0000

После четвертой итерации мы опять получаем сжатие 2:1
00

После пятой итерации мы опять получаем сжатие 2:1
0

oh wait.....

Я кстати знаю как сделать архиватор, который закодирует войну и мир в один бит. Если бит 1, то это война и мир. Если бит 0, то это не война и мир. Ни один архиватор так сильно сжимать информацию не умеет.

Sergio
> Показываю наглядный пример:
> 32-х битное число 0 (напоминаю, работаем с битами):
> 00000000 00000000 00000000 0000000
Насколько я понял, у автора такой случай самый затратный

Pilix
> Это очень сильно тормозит процесс распаковки (к сжатию это не относится),
> особенно в случае длинных участков единиц или нулей в исходной информации.

Pilix
> Это очень сильно тормозит процесс распаковки (к сжатию это не относится),
> особенно в случае длинных участков единиц или нулей в исходной информации
Сожми сначала RLE

dev
> Ты попал на gamedev форум, парень, здесь принято предоставлять доказательства.
Бросьте, здесь неглупые люди вокруг. Не уж то вы думаете, что выложу код, который появился спустя 2 года исследований, чтобы его пустили в интернеты, а там и доработали?

Sergio
> oh wait.....

32:1 !!!

Возможна оптимизация для 64-битных процессоров!! Тут ещё как бонус - блочная обработка !

64-х битное число 0
00000000 00000000 00000000 0000000 00000000 00000000 00000000 0000000

После первой итерации мы получаем сжатие 64:1
0

;)

Pilix
> Не уж то вы думаете, что выложу код, который появился спустя 2 года
> исследований, чтобы его пустили в интернеты, а там и доработали?

Так зачем было создавать тему ? Раз ни сказать, ни показать нечего. NumTrolls++

Нетрудно провести тот же эксперимент с числом (unsigned int)(-1) и экстраполировать результаты на любое число. Или я что-то делаю не так?

Sergio
> Или я что-то делаю не так?

Понадобятся огромные таблицы для частных случаев :D
Причем тут уже привели пример:

> Если бит 1, то это война и мир. Если бит 0, то это не война и мир.