Увеличение степени сжатия и скорости чтения
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.216.88] |
|
|
правила раздела Алгоритмы

| Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Увеличение степени сжатия и скорости чтения
|
Сообщ.
#16
,
|
|
|
|
А вот начальное состояние автомата (для алгоритма Лемпела-Зива -- начальное заполнение окна, для динамического Хаффмана -- начальное древо...) можно подобрать оптимальным для всего набора файлов, которые будут сжиматься. Или пару-тройку таких начальных состояний
|
|
Сообщ.
#17
,
|
|||
|
|
В этом то и суть блочного архивирования. Каждый блок архивируется своим отпимальным для него методом. В начале архива имеем структуру блоков где указанано: номер блока и текущее смещение-указатель на этот блок в архиве так же имеем "таблицу" файлов находящихся в архиве, где указывается: имя файла, смещение на блоки файла в архиве, и соответсвенно размер.. |
|
Сообщ.
#18
,
|
|
|
|
Так уже ж есть блоки -- сами файлы. Зачем еще усложнять?
Ето таки может сработать, в самом деле... Но что-то мне подсказывает, что ето будет (как минимум) полиномиально высокой степени сложно сделать. А то и НП-полно вообще |
|
Сообщ.
#19
,
|
|
|
|
Щас как раз и занялся этим..
завтра выложу результаты |
|
Сообщ.
#20
,
|
|||
|
|
Именно.. получается, что один файл разбит на блоки, каждый из которых имеет отпимальный метод сжатия.. Конечно при архивации придется перебирать мнрожество методов для каждого блока и это займет много времени. Но зато в итоге получим "идеальный" архив |
|
|
|
|
|
Распаковку быстрее, чем LZSS (вообще методов семейства LZ77) ты сделаешь вряд ли. LZB чуть получше, поэтому советую именно его.
Интервальное кодирование (более скоростная модификация арифметического), как и Хаффман, как и контекстное моделирование, для разнородных данных, ИМХО, не лучший метод, да и по скорости явно медленнее. LZW (в общем, любые LZ78) - метод тормозной. А по поводу блочного кодирования... ты знаешь, не думаю, что у тебя будет большой выигрыш, т.к. при чередовании методов будет теряться информация о предыдущих байтах (или её нужно собирать заново - опять же время), соответственно и сжатие хуже. Подумай: создал ты адаптивную PPM-модель, закодировал 16kb, а потом переходишь к LZB... здесь, в общем-то можно использовать предыдущие байты как окно, но когда ты перейдёшь обратно в PPM, придётся строить модель заново (хотя, можно и использовать старую, но ещё не факт, что так лучше). Не буду тебя отговаривать, но ИМХО, это только лишний гемор. Я б использовал LZB или ZIP вообще (чтоб не мучаться) RAR, кстати, тоже LZSS использует, только там куча фильтров, поэтому и тормозит. |
|
Сообщ.
#22
,
|
|
|
|
Не, тут постановка такая: создать архиватор, причем не контекстно-адаптивный, как LZSS, или статистический, как LZW или хаффмана, а идеальный, использующий как знание о структуре всего кодируемого потока, так и каждой отдельно взятой его части
И потом посмотреть, что из етого получится. (И заодно разрешить некоторые теологические споры, касающиеся того, сколько "посторонней" информации вносят существующие архиваторы в сжатый поток |
|
Сообщ.
#23
,
|
|
|
|
Итак..
Получился почти "идеальный" архиватор с элементами собственно распаковки данных.. Упаковка идет раз 10 медленней чем всякие RARы и ZIPы, но зато распаковка куда быстрее, правда пока не намоного примерно на 5-10%, но над этим работы продолжаются.. |
|
Сообщ.
#24
,
|
|
|
|
А как на счёт степени сжатия?
И какой метод использован? p.s. Ты это всё вручную пишешь? |
|
Сообщ.
#25
,
|
|
|
|
Объясняю технологию...
Имеем кучу файлов, которые необходимо заархивировать. В процессе архивации читаем файл по блокам (например по 16 кБ, можно выбрать любой). Архивируем его (блок)по-очереди несколькими способами (LZb(W), RLEB(W), Huffman или вообще не архирируем). Сравниваем какой метод для этого блока наиболее эффективен и пишем его в архив. Правда на это уходит до фига времени При разархивации знаем каким методом блок заархивирован и распаковываем его.. Про процентное содержание я уже писал Коэфф. сжатия лучше даже чем у RARа |