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

[ZonoID]

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

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

Дык... тема то интересная, можно сказать любимая, если админы/модеры не против (контент то генерится уникальный, хоть и бредовый) можно и пообсуждать. Почему нет? Тем паче, что бурных дискуссий в топике я не наблюдаю. Похоже я вообще единственный, кто откликнулся на твой призыв. Однако что-то энтуазизма в твоем голосе я не слышу.
Что не так? Зачем тему создавал тогда?

Поэтому давай так, если есть желание тему развить, напиши. Я выложу еще пару-тройку своих идей. А ты своих. Я тебя покритикую, ты меня. А потом попробуем идеи объединить. Может чего и выйдет толкового?

А нет, так нет...

А что касается пиара сайта моего, если бы я хотел только ссыль оставить, я бы не стал столько текста писать, черкнул бы коротко "бред" и ссылку запостил (а здесь мол не бред написан, а умные вещи)

[ZonoID]

Вернемся к нашему примеру.

Обычное кодирование для четырех битового слова выглядит так:
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

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

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

Выпишем вообще все получившиеся комбинации:

0000 - 0
0001 - 1
0010 - 2
0011 - 3
0100 - 4
0101 - 5
0110 - 6
1000 - 7
1001 - 8
1010 - 9
1100 - 10

Вот теперь мы видим, что наша обработка сократила число вариантов с 16 до 11

Мыслим логически, на каждое обработанное 8-разрядное машинное слово, нам придется иметь 2 бита в массиве "для восстановления". Тогда как "экономический эффект" у нас равен 16 Х 16/11 Х 11 =
256/121=2.1 бита на байт - 2 (1 бит на каждое 4-х битовое слово на восстановление информации)
Итог: - 0.1

(0.1 бит экономии на каждый 8-ми разрядный байт, то есть на каждые 8 байт мы получаем 1 бит экономии или 16 байт экономии на каждый килобайт 1024 байта, для "сжатия без потерь", это очень приличные цифры и к тому же, нам ничто не мешает прогнать через наш алгоритм архив многократно, после каждого "прохода" энтропия будет менятся)

Почему же метод не сработал, если в теории все вроде правильно?

Причина в том, что "почти" не "равно".
У нас не изменилась разрядность, в ней просто появились "дырки" - пустые незаполненные варианты. (по поводу этого есть отдельная идея, если нужно напишу). Так как твоего положительного ответа я пока не услышал.

[NSvirus]

Где то в интернете читал веселую историю, "история одного байта"(или бита,точно не помню) называется. Советую

[ZonoID]

Жалко тема сдохла, а топикстартер потерялся...

Изучил тут соседнюю тему: http://programmersforum.ru/showthread.php?t=134734
почему-то закрытую, сразу скажу что "теорию" не читал, потому как все идеи высказанные в обсуждении мною просчитаны еще лет 10 назад.
Ничего не сработает. И дело не в том, что хэш прямо пропорционален размеру служебной информации и даже не в том, что хранить все возможные варианты хэшей на серваке бессмысленно. А в том, что сам подход - стандартен.
Прямолинейность мышления налицо. Раньше программисты мыслили более извращенно...

Прошу вас, если кому-то интересна эта тема, отпишитесь, потому что строчить вхолостую километры текста мне неохота. А если это кому нибудь интересно - то запросто.

И так моя идея, основанная на вышеописанном способе:

Если взять любой произвольный кусок массива из 128 байт длинной, то сколько не считайте вероятности, в нем не будет более 128 не повторяющихся байт.
А поскольку 128 ровно в 2 раза меньше 256, то мы имеем экономию 1 бит на байт.
или 1/8 массива.

+ для восстановления нам придется иметь "служебную информацию" которая состоит из номера варианта всех возможных комбинаций. После довольно несложных подсчетов, я выяснил что число вариантов как раз равно... экономии.

Биты из "сжимаемой информации" плавно перетекают в массив для восстановления.

Я поигрался с размерами "куска массива". Цифры всегда прямо пропорциональны.

Вот тут я и придумал "вилки". А что если удалить часть информации из массива?
Повторяющиеся байты (а таковые будут всегда, в противном случае а такой будет всего один единственный, это когда все 128 байт разные, а значит сжатие будет еще больше) можно удалить оставив всего лишь указатели и значение. Приведу пример:

011
123
222
123
014
147
000
111

Самый простейший случай у нас имеется массив из 8 байт и 2 из них повторяются.

1. Нам не надо хранить целиком все байты. Достаточно рассортировать все возможные варианты по 8 байт. и хранить только указатель нужного варианта.
2. внутри варианта придется хранить все возможные варианты перестановок местами данных байт (12345678, 13245678, 14235678 и т.п.)
3. за счет вилки можно удалить один из повторяющихся байт оставив (см п1) номер варианта "вилки" и значение самого байта


Для нашего варианта "вилки":

011 123 222 123 014 147 000 111

повторяется число 123 пометим повторяющиеся единицами, не повторяющиеся 0,

01010000

выкинем второй повторяющийся байт и набьем массив "для восстановления"

Нетрудно посчитать количество вариантов всех возможных перестановок 2 единиц на 8 "знакоместах". и выбрать нужный вариант.

Далее, первое число оставляем, второе удаляем. (Записи не поднимал пишу по памяти), расчеты показали, что выигрыш есть и он хотя и невелик, но вполне присутствует. А вот дальше.. пошел сбой. Небольшой пример, единицами показаны повторяющиеся байты, а 0 неповторяющиеся:

00000000 - нет вилок
00000011 - вилка 1
00000101 - вилка 2
.........
11000000 - вилка 30

далее тройная вилка:

00000111 - тройная вилка номер 1
00001101 - тройная вилка номер 2
............ - и так далее

до 7-мерной вилки

и наконец - все 8 чисел одинаковые

Количество вилок начинает расти в обратной пропорциональности получающейся экономии от их использования.

В восьми байтах подряд может быть НЕСКОЛЬКО "вилок" сразу, (чего я не учел) и чем этих "вилок" больше, тем сложнее их обработать. Получается каждый блок массива нужно прогонять многократно, и массив "служебной информации" начинает "распухать" от пустых проходов, а если отсортировать "вилки" по количеству повторений и хранить только номер варианта, таких вариантов настолько много....

пример две вилки в одном блоке:

00002211 - единицы повторяющиеся байты, двойки другие повторяющиеся... и так далее.

И так, впав в окончательный маразм и убив почти 2 дня на подсчеты я вывел формулу (не помню уже, записи искать лень) и после всех расчетов и извращений пришел к исходному числу - размеру обрабатываемого массива.

И начали меня мучать смутные сомнения... уж не "закон сохранения размера информации" я открыл?

[Serge_Bliznykov]

Где то в интернете читал веселую историю, "история одного байта"(или бита,точно не помню) называется. Советую

История одного байта

[veniside]

> "закон сохранения размера информации" я открыл?

не, скорее это "самый извращённый способ показать, что для хранения 256 уникальных комбинаций в общем случае потребуется минимум 8 двоичных бит".

[Smitt&Wesson]

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

История одного байта

Почитал. Бред Сивой кобылы. Ха-ха, насмешил!

[techmanforever]

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

1. Начни мыслить абстрактно. Отодвинь проблему дальше от себя, охвати взглядом и попытайся прочувствовать каждый бит.
2. Любое сжатие "без потерь" требует дополнительного массива "для восстановления".
7. Массив для восстановления должен обрабатываться и сжиматься тоже и одновременно с исходным массивом.

1 - Это прям в точку
2 - А вот это не обязательно
7 - А эттого может и не быть вовсе согласно 2)

Да и сжать можно и легко любые рандомные данные. Вот тока коэффициент сжатия не очень на каждый проход.
Что то около ~ 1.05

Что же касается http://programmersforum.ru/showthread.php?t=134734, то этот метод и прочие похожие не помогут.
Так как в принципе надо понимать что для случайных данных стандартные методы не подходят, какими бы они хитрыми небыли. Что касается конкретно метода по ссылке то он будет работать только на футуристическом компьютере у которого размек кластера данных меняется в зависимости от хранимых данных. Понятно дело попытка сымитировать это на реальном железе привет к тому что вся выгода сжатия покроется хранением служебной информации на винте.

Да и то доказательство что приводят обычно люди что сжать любую последовательность нельзя до одного бита не действительно. Оно абстракно. А реальна совсем другая ситуация. Сжать до 1 бита нельзя по другим причинам. Во первых в компьютере минимальная информация занимает байт, а во вторых постоянно поджимая файл надо понимать что количество этих самых попыток надо где то хранить. Т.е. по любому до 1 байта сжать нельзя, но вовсе не из за различия комбинаций N количества байт перед N-1 количества. Не говоря уж что до бита :-)

[JTG]

Да и сжать можно и легко любые рандомные данные. Вот тока коэффициент сжатия не очень на каждый проход.
Что то около ~ 1.05

Ещё один теоретик. Ну да, 1.05, сжатые данные будут занимать на 5% больше, согласен

[techmanforever]

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

Ещё один теоретик. Ну да, 1.05, сжатые данные будут занимать на 5% больше, согласен

Эх ... если бы тока теоретик

А так достал с запыленой полочки Open Watcom Fortran и програмлю в свободное от работы время ...