 |
Сработает ли такой архиватор? |
 |
14.01.2005, 12:41
|
#1
|
|
hex god
Join Date: 03 2002
Location: Yerevan, AM
Age: 48
Posts: 3,172
Rep Power: 0
|
Сработает ли такой архиватор?
Берем файл, читаем побайтно. В некий временный файл записываем в виде текста бинарные значения байтов исходного файла, то есть, например, байт со значением 201 записывается как 11001001. В итоге получаем текстовый файл, состоящий только из нулей и единиц (можно также предположить наличие некоторого header-а). Тепеть архивируем получившийся временный файл (размер которого в 8 раз больше исходного) любым архиватором, который как известно архивирует текст гораздо эффективнее, чем предположим mp3-файл.
Вопрос в следующем, сожмется ли больший файл сильнее, чем если бы сжимался исходный маленький?
|
|
|
|
|
14.01.2005, 14:20
|
#2
|
|
Доктор
Join Date: 03 2002
Location: Yerevan
Age: 49
Posts: 1,734
Rep Power: 0
|
А одно и тоже. Просто текстовые они по своей сути содержат больший потенциал для сжатия.
|
|
|
|
|
14.01.2005, 14:40
|
#3
|
|
Грустно...
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 44
Posts: 21,717
Rep Power: 9
|
Зависит от данных.
|
|
|
|
|
14.01.2005, 14:44
|
#4
|
|
Guru Apprentice
Join Date: 02 2002
Location: /dev/null
Age: 50
Posts: 524
Rep Power: 0
|
Из 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 раз, а потом сжимаешь на чуть больше половины... по моему не получится...
|
|
|
|
|
14.01.2005, 14:46
|
#5
|
|
Грустно...
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 44
Posts: 21,717
Rep Power: 9
|
если только не получится очень хороший набор данных... которые например одним RLE можно скатать практически в 0 
|
|
|
|
|
14.01.2005, 16:42
|
#6
|
|
hex god
Join Date: 03 2002
Location: Yerevan, AM
Age: 48
Posts: 3,172
Rep Power: 0
|
Хрен поймет одним словом. Все руки не доходят сесть и попробовать...
Просто если такая возможность есть, получится, что можно еще раз сжать получившийся архив, потом еще, еще, еще... В конце концов все превратится черт его знает во что... Следовательно есть какой-то теоретический предел, максимальный КПД...
|
|
|
|
|
14.01.2005, 16:48
|
#7
|
|
Доктор
Join Date: 03 2002
Location: Yerevan
Age: 49
Posts: 1,734
Rep Power: 0
|
Quote:
|
Originally Posted by Griffon2-7
Просто если такая возможность есть, получится, что можно еще раз сжать получившийся архив, потом еще, еще, еще...
|
Чанцав, ведь при архивации добавляется соответствующая информация, так что предел довольно близок.
Так, например, очень маленькие файлы даже с первого архивирования получаются больше оригинала
|
|
|
|
|
14.01.2005, 17:02
|
#8
|
|
Грустно...
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 44
Posts: 21,717
Rep Power: 9
|
предел Дав определяется избытком информации в данных 
|
|
|
|
|
|
|
|
14.01.2005, 18:58
|
#9
|
|
ЙЦУКЕН
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 56
Posts: 3,118
Rep Power: 0
|
Господин Гриффон-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 ты понял к чему я клоню ?
|
|
|
|
 |
|
14.01.2005, 19:03
|
#10
|
|
ЙЦУКЕН
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 56
Posts: 3,118
Rep Power: 0
|
пример: если есть текст состоящий из 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.
|
|
|
|
|
14.01.2005, 20:26
|
#11
|
|
Академик
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 54
Posts: 4,854
Rep Power: 5
|
Ne vdavayas` v podrobnosti - ninakoy raznici ne budet.
|
|
|
|
|
14.01.2005, 20:32
|
#12
|
|
ЙЦУКЕН
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 56
Posts: 3,118
Rep Power: 0
|
Quote:
|
Originally Posted by W_z_rd
Ne vdavayas` v podrobnosti - ninakoy raznici ne budet.
|
будет ;)
оно увеличится в объеме:)
т.к. ни один архиватор не кодирует идеально до теоритического размера :)))))
|
|
|
|
|
15.01.2005, 12:08
|
#13
|
|
Профессор
Join Date: 01 2005
Location: Perm
Age: 47
Posts: 2,142
Rep Power: 0
|
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`
|
|
|
|
|
15.01.2005, 16:56
|
#14
|
|
ЙЦУКЕН
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 56
Posts: 3,118
Rep Power: 0
|
accemic26 -- это теоритический минумум. доказательство и всяческие подробности всего этого дела есть в работах Шеннона.
если сумеешь предложить и доказать что-либо другое -- бросай все, чем ты занимался до сих пор, и доказывай -- докторскую точно сумеешь защитить
|
|
|
|
|
15.01.2005, 16:59
|
#15
|
|
Грустно...
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 44
Posts: 21,717
Rep Power: 9
|
верьте Шеннону он не врет
|
|
|
|
|
All times are GMT. The time now is 20:55. |
|
|
