Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 14.01.2005, 12:41   #1
hex god
 
Griffon2-7's Avatar
 
Join Date: 03 2002
Location: Yerevan, AM
Age: 39
Posts: 3,172
Downloads: 1
Uploads: 0
Reputation: 9 | 0
Default Сработает ли такой архиватор?

Берем файл, читаем побайтно. В некий временный файл записываем в виде текста бинарные значения байтов исходного файла, то есть, например, байт со значением 201 записывается как 11001001. В итоге получаем текстовый файл, состоящий только из нулей и единиц (можно также предположить наличие некоторого header-а). Тепеть архивируем получившийся временный файл (размер которого в 8 раз больше исходного) любым архиватором, который как известно архивирует текст гораздо эффективнее, чем предположим mp3-файл.
Вопрос в следующем, сожмется ли больший файл сильнее, чем если бы сжимался исходный маленький?
Reply With Quote
Old 14.01.2005, 14:20   #2
Доктор
 
Tivin's Avatar
 
Join Date: 03 2002
Location: Yerevan
Age: 40
Posts: 1,734
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

А одно и тоже. Просто текстовые они по своей сути содержат больший потенциал для сжатия.
Reply With Quote
Old 14.01.2005, 14:40   #3
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Зависит от данных.
Reply With Quote
Old 14.01.2005, 14:44   #4
Guru Apprentice
 
Join Date: 02 2002
Location: /dev/null
Age: 41
Posts: 524
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Из man page gzip:
Gzip uses the Lempel-Ziv algorithm used in zip and PKZIP.
The amount of compression obtained depends on the size of
the input and the distribution of common substrings. Typ*
ically, text such as source code or English is reduced by
60-70%.

Ты увеличиваешь размер файла в 8 раз, а потом сжимаешь на чуть больше половины... по моему не получится...
Reply With Quote
Old 14.01.2005, 14:46   #5
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

если только не получится очень хороший набор данных... которые например одним RLE можно скатать практически в 0
Reply With Quote
Old 14.01.2005, 16:42   #6
hex god
 
Griffon2-7's Avatar
 
Join Date: 03 2002
Location: Yerevan, AM
Age: 39
Posts: 3,172
Downloads: 1
Uploads: 0
Reputation: 9 | 0
Default

Хрен поймет одним словом. Все руки не доходят сесть и попробовать...
Просто если такая возможность есть, получится, что можно еще раз сжать получившийся архив, потом еще, еще, еще... В конце концов все превратится черт его знает во что... Следовательно есть какой-то теоретический предел, максимальный КПД...
Reply With Quote
Old 14.01.2005, 16:48   #7
Доктор
 
Tivin's Avatar
 
Join Date: 03 2002
Location: Yerevan
Age: 40
Posts: 1,734
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally Posted by Griffon2-7
Просто если такая возможность есть, получится, что можно еще раз сжать получившийся архив, потом еще, еще, еще...
Чанцав, ведь при архивации добавляется соответствующая информация, так что предел довольно близок.

Так, например, очень маленькие файлы даже с первого архивирования получаются больше оригинала
Reply With Quote
Old 14.01.2005, 17:02   #8
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

предел Дав определяется избытком информации в данных
Reply With Quote
Old 14.01.2005, 18:58   #9
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Господин Гриффон-5

Есть понятие энтропии. которое очень четко позволяет сказать теоретический предел сжатия данных.

пусть у нас есть алфавит -- [ A, B, C ]

и текст состоящий из этого алфавита -- AABADCAAи тако далее.
пусть у нас есть функции - SIZEOF(Text), COUNT(Text, Symbol) - количество вхождений данного символа в текст.

вероятнсоть вхождения данного символа в текст -- P(Text, Symbol) = COUNT(Text, Symbol)/SIZEOF(Text).
Необходимое количество бит для кодирования всех вхождений данного символа --
Bits(Text, Symbol) = - COUNT(Text, Symbol) * LN(P(Text, Symbol))/LN(2)

минус, т.к. когарифм от вероятности всегда отрицательный

минимальная длина в который может быть закодирован текст (она-же энтропия) -- SUM(Bits(Text, Symbol) foreach Symbol in [A,B,C])

так что что хочешь делай, но меньше этого лимита не сожмешь

кстати .... я тут знаю один архиватор. для Doom2. сжимает его ровно в 1 байт. правда умеет сжимать и распаковывать только Doom ты понял к чему я клоню ?
Reply With Quote
Old 14.01.2005, 19:03   #10
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

пример: если есть текст состоящий из 10 букв A и 10 букв B(поправка -- об их последовательности я ваще ничего не говорю, это не важно), ты его сожмешь минимум в 20 бит. т.к. каждый из них для кодирования требует ровно 1 бит.
если же текст состоит из 2 букв А и 18 букв B, то ты его сожмешь в 9.38 бит -- причем для кодирования А тебе потребуется 3.32 бита на символ, а для кодирования B -- 0.15 бит на символ

так. и еще -- насчет _дробных_ бит не удивляться -- это нормальное понятие в теории всего этого дела и как ни странно и в практике тоже -- так арифмитечиское кодирование позволяет закодировать именно дробное количество бит на символ

Last edited by nm; 15.01.2005 at 17:01.
Reply With Quote
Old 14.01.2005, 20:26   #11
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 3
Default

Ne vdavayas` v podrobnosti - ninakoy raznici ne budet.
Reply With Quote
Old 14.01.2005, 20:32   #12
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally Posted by W_z_rd
Ne vdavayas` v podrobnosti - ninakoy raznici ne budet.
будет ;)
оно увеличится в объеме:)
т.к. ни один архиватор не кодирует идеально до теоритического размера :)))))
Reply With Quote
Old 15.01.2005, 12:08   #13
Профессор
 
Nikita's Avatar
 
Join Date: 01 2005
Location: Perm
Age: 38
Posts: 2,142
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

NM
No arxivator mojet prodelat` tvoyu operaciyu naoborot. I kstate on eto skoree vsego sdelayet, Zametiv chto kod sostoit iz 2 odinakovix posledovatel`nostey. a potom esli budet umnim yesh`o raz proidyotsya po tvoyemu file-u...
No ya dumayu vremennii file vsyoravno budet bol`she, t.k. yemu nujno budet derjat` informacuyu kodiruyush`uyu ASCII 0 i 1 ... chtobi potom mojno bilo vosstanovit`
Reply With Quote
Old 15.01.2005, 16:56   #14
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

accemic26 -- это теоритический минумум. доказательство и всяческие подробности всего этого дела есть в работах Шеннона.

если сумеешь предложить и доказать что-либо другое -- бросай все, чем ты занимался до сих пор, и доказывай -- докторскую точно сумеешь защитить
Reply With Quote
Old 15.01.2005, 16:59   #15
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

верьте Шеннону он не врет
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 20:44.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.