Сработает ли такой архиватор?

Griffon2-7 · Jan 14, 2005, 12:41

Берем файл, читаем побайтно. В некий временный файл записываем в виде текста бинарные значения байтов исходного файла, то есть, например, байт со значением 201 записывается как 11001001. В итоге получаем текстовый файл, состоящий только из нулей и единиц (можно также предположить наличие некоторого header-а). Тепеть архивируем получившийся временный файл (размер которого в 8 раз больше исходного) любым архиватором, который как известно архивирует текст гораздо эффективнее, чем предположим mp3-файл.
Вопрос в следующем, сожмется ли больший файл сильнее, чем если бы сжимался исходный маленький?

Tivin · Jan 14, 2005, 14:20

А одно и тоже. Просто текстовые они по своей сути содержат больший потенциал для сжатия.

Agregat · Jan 14, 2005, 14:40

Зависит от данных.

Ektich · Jan 14, 2005, 14:44

Из 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 раз, а потом сжимаешь на чуть больше половины... по моему не получится...

Agregat · Jan 14, 2005, 14:46

если только не получится очень хороший набор данных... которые например одним RLE можно скатать практически в 0

Griffon2-7 · Jan 14, 2005, 16:42

Хрен поймет одним словом. Все руки не доходят сесть и попробовать...
Просто если такая возможность есть, получится, что можно еще раз сжать получившийся архив, потом еще, еще, еще... В конце концов все превратится черт его знает во что... Следовательно есть какой-то теоретический предел, максимальный КПД...

Tivin · Jan 14, 2005, 16:48

Quote:

Originally Posted by Griffon2-7

Просто если такая возможность есть, получится, что можно еще раз сжать получившийся архив, потом еще, еще, еще...

Чанцав, ведь при архивации добавляется соответствующая информация, так что предел довольно близок.

Так, например, очень маленькие файлы даже с первого архивирования получаются больше оригинала

Agregat · Jan 14, 2005, 17:02

предел Дав определяется избытком информации в данных

nm · Jan 14, 2005, 18:58

Господин Гриффон-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

ты понял к чему я клоню ?

nm · Jan 14, 2005, 19:03

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

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

и как ни странно и в практике тоже -- так арифмитечиское кодирование позволяет закодировать именно дробное количество бит на символ

W_z_rd · Jan 14, 2005, 20:26

Ne vdavayas` v podrobnosti - ninakoy raznici ne budet.

nm · Jan 14, 2005, 20:32

Quote:

Originally Posted by W_z_rd

Ne vdavayas` v podrobnosti - ninakoy raznici ne budet.

будет ;)
оно увеличится в объеме:)
т.к. ни один архиватор не кодирует идеально до теоритического размера :)))))

Nikita · Jan 15, 2005, 12:08

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`

nm · Jan 15, 2005, 16:56

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

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

Agregat · Jan 15, 2005, 16:59

верьте Шеннону он не врет

Jan 14, 2005, 12:41	#1
Griffon2-7 hex god Join Date: Mar 2002 Location: Yerevan, AM Posts: 3,173 Rep Power: 7 Reputation: 19	Сработает ли такой архиватор? Берем файл, читаем побайтно. В некий временный файл записываем в виде текста бинарные значения байтов исходного файла, то есть, например, байт со значением 201 записывается как 11001001. В итоге получаем текстовый файл, состоящий только из нулей и единиц (можно также предположить наличие некоторого header-а). Тепеть архивируем получившийся временный файл (размер которого в 8 раз больше исходного) любым архиватором, который как известно архивирует текст гораздо эффективнее, чем предположим mp3-файл. Вопрос в следующем, сожмется ли больший файл сильнее, чем если бы сжимался исходный маленький? __________________ Ленинградское время 0 часов 0 минут

Jan 14, 2005, 14:40	#3
Agregat Грустно... Join Date: Aug 2002 Location: Там, где всегда идут дожди Posts: 21,637 Rep Power: 11 Reputation: 211	Зависит от данных. __________________ http://аvitya.livejournal.com Хотели, как лучше, а получилось даже хуже... Лозунг шахматиста: На каждый шах - ответим матом!

Jan 14, 2005, 14:44	#4
Ektich Guru Apprentice Join Date: Feb 2002 Location: /dev/null Posts: 524 Rep Power: 7 Reputation: 10	Из 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 раз, а потом сжимаешь на чуть больше половины... по моему не получится... __________________ \/\/h47'5 1n 4 n4m3? 7h47 wh1(h w3 (4\|\| 4 r053, 8y 4ny 07h3r n4m3 w0u\|d 5m3\|\| 45 5w337...

Jan 14, 2005, 14:46	#5
Agregat Грустно... Join Date: Aug 2002 Location: Там, где всегда идут дожди Posts: 21,637 Rep Power: 11 Reputation: 211	если только не получится очень хороший набор данных... которые например одним RLE можно скатать практически в 0 __________________ http://аvitya.livejournal.com Хотели, как лучше, а получилось даже хуже... Лозунг шахматиста: На каждый шах - ответим матом!

Jan 14, 2005, 16:42	#6
Griffon2-7 hex god Join Date: Mar 2002 Location: Yerevan, AM Posts: 3,173 Rep Power: 7 Reputation: 19	Хрен поймет одним словом. Все руки не доходят сесть и попробовать... Просто если такая возможность есть, получится, что можно еще раз сжать получившийся архив, потом еще, еще, еще... В конце концов все превратится черт его знает во что... Следовательно есть какой-то теоретический предел, максимальный КПД... __________________ Ленинградское время 0 часов 0 минут

Jan 14, 2005, 14:20	#2
Tivin Антиянкист и антисемит Join Date: Mar 2002 Location: Yerevan Posts: 1,734 Rep Power: 7 Reputation: 10	А одно и тоже. Просто текстовые они по своей сути содержат больший потенциал для сжатия.

Jan 14, 2005, 17:02	#8
Agregat Грустно... Join Date: Aug 2002 Location: Там, где всегда идут дожди Posts: 21,637 Rep Power: 11 Reputation: 211	предел Дав определяется избытком информации в данных __________________ http://аvitya.livejournal.com Хотели, как лучше, а получилось даже хуже... Лозунг шахматиста: На каждый шах - ответим матом!

Jan 14, 2005, 18:58	#9
nm ЙЦУКЕН Join Date: Jul 2002 Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77 Posts: 3,114 Rep Power: 7 Reputation: 10	Господин Гриффон-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 ты понял к чему я клоню ? __________________ -- Опоздавшему поросёнку сиська возле жопы.

Jan 14, 2005, 19:03	#10
nm ЙЦУКЕН Join Date: Jul 2002 Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77 Posts: 3,114 Rep Power: 7 Reputation: 10	пример: если есть текст состоящий из 10 букв A и 10 букв B(поправка -- об их последовательности я ваще ничего не говорю, это не важно), ты его сожмешь минимум в 20 бит. т.к. каждый из них для кодирования требует ровно 1 бит. если же текст состоит из 2 букв А и 18 букв B, то ты его сожмешь в 9.38 бит -- причем для кодирования А тебе потребуется 3.32 бита на символ, а для кодирования B -- 0.15 бит на символ так. и еще -- насчет _дробных_ бит не удивляться -- это нормальное понятие в теории всего этого дела и как ни странно и в практике тоже -- так арифмитечиское кодирование позволяет закодировать именно дробное количество бит на символ __________________ -- Опоздавшему поросёнку сиська возле жопы. Last edited by nm : Jan 15, 2005 at 17:01.

Jan 14, 2005, 20:26	#11
W_z_rd Академик Join Date: Aug 2002 Location: Yerevan, Armenia Posts: 4,781 Rep Power: 7 Reputation: 191	Ne vdavayas` v podrobnosti - ninakoy raznici ne budet. __________________ Женщин не надо понимать, их надо любить!

Jan 15, 2005, 12:08	#13
Nikita Профессор Join Date: Jan 2005 Location: Perm Posts: 2,142 Rep Power: 4 Reputation: 10	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`

Jan 15, 2005, 16:56	#14
nm ЙЦУКЕН Join Date: Jul 2002 Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77 Posts: 3,114 Rep Power: 7 Reputation: 10	accemic26 -- это теоритический минумум. доказательство и всяческие подробности всего этого дела есть в работах Шеннона. если сумеешь предложить и доказать что-либо другое -- бросай все, чем ты занимался до сих пор, и доказывай -- докторскую точно сумеешь защитить __________________ -- Опоздавшему поросёнку сиська возле жопы.

Jan 15, 2005, 16:59	#15
Agregat Грустно... Join Date: Aug 2002 Location: Там, где всегда идут дожди Posts: 21,637 Rep Power: 11 Reputation: 211	верьте Шеннону он не врет __________________ http://аvitya.livejournal.com Хотели, как лучше, а получилось даже хуже... Лозунг шахматиста: На каждый шах - ответим матом!

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Luna v znakakh Zodiaka	Helen	Psychology and Philosophy	33	Apr 18, 2007 11:21
Вот такой реальный американский учебник русского языка...	acid	Uncensored	17	May 23, 2006 04:27
А есть такой закон?	AshA	Law	6	Jul 12, 2004 14:47
неплохой такой футбол - Киликия:Мика	tig	Sport	0	Jun 7, 2004 21:38
dlinniy flame ;)	m4ng0	Test	0	Jun 5, 2002 11:16