Каково понятие позади сжатия zip?
Язык Common LISP Ansi Paul Graham является хорошей книгой.
я думаю, что это могло бы быть распродано, таким образом, Ваш лучший выбор получить его через Amazon. Я получил книгу для класса "Обработки естественного языка", я занял свой второй курс в колледже. Мы должны были записать проекты программирования в LISP, и таким образом, я должен был изучить Lisp быстро.
книга помогла мне вполне немного.
3 ответа
Хорошим местом для начала было бы поискать Хаффмана схема сжатия. Основная идея huffman заключается в том, что в данном файле одни байты появляются чаще, чем другие (в текстовом файле многие байты вообще не появляются). Вместо этого потратите 8 бит на кодирование каждого байта, почему бы не использовать более короткую последовательность битов для кодирования наиболее распространенных символов и более длинные последовательности для кодирования менее распространенных символов (эти последовательности определяются путем создания дерева Хаффмана).
Один раз вы научитесь использовать эти деревья для кодирования / декодирования файлов на основе частоты символов, представьте, что затем вы начинаете работать с частотой слов - вместо того, чтобы кодировать «они» как последовательность из 4 символов, почему бы не считать это одним символом из-за его частоты, что позволяет назначить ему собственный лист в дереве Хаффмана. Это более или менее основа для ZIP и других типов сжатия без потерь - они ищут общие «слова» (последовательности байтов) в файле (включая последовательности всего 1 байта, если они достаточно распространены) и используют дерево для их кодирования. Затем в zip-файл необходимо включить только информацию о дереве (копию каждой последовательности и количество раз, которое она появляется), чтобы дерево можно было восстановить, а остальную часть файла - декодировать.
Последующие действия:
Чтобы лучше ответить на исходный вопрос, идея сжатия без потерь заключается не столько в удалении пустого пространства, сколько в удалении избыточной информации.
Если вы создали базу данных для хранения музыкальных текстов, вы бы обнаружили, что много места используется для хранения припева, который повторяется несколько раз. Вместо того, чтобы использовать все это пространство, вы можете просто поместить слово CHORUS перед первым экземпляром строк припева, а затем каждый раз, когда припев будет повторяться,
Понятие между сжатием в основном статистическое. Если у вас есть серия байтов, вероятность того, что байт N будет X на практике, зависит от распределения значений предыдущих байтов 0..N-1. Без сжатия вы выделяете 8 бит для каждого возможного значения X. При сжатии количество байтов, выделяемых для каждого значения X, зависит от предполагаемого шанса p (N, X).
Например, для данной последовательности «аааа» алгоритм сжатия может присвоить высокое значение p (5, а) и меньшие значения до p (5, б). Когда p (X) высокий, цепочка битов, назначенная X, будет короткой, когда p (X) низкий, используется длинная цепочка битов. Таким образом, если p (N, X) является хорошей оценкой, то средняя строка битов будет короче 8 бит.
Основная концепция заключается в том, что вместо использования восьми битов для представления каждого байта вы используете более короткие представления для более часто встречающихся байтов или последовательностей байтов.
Например, если ваш файл состоит исключительно из байта 0x41 ( A ) повторяется шестнадцать раз, затем вместо представления его в виде 8-битной последовательности 01000001 сократите его до 1-битной последовательности 0 . Тогда файл может быть представлен как 0000000000000000 (шестнадцать 0 сек). Таким образом, файл с байтом 0x41 , повторяющимся шестнадцать раз, может быть представлен файлом, состоящим из байта 0x00 , повторяемого дважды.
Итак, у нас есть то, что для этого файла ( 0x41 повторяется шестнадцать раз) биты 01000001 не t передают любую дополнительную информацию через бит 0 . Итак, в этом случае мы отбрасываем посторонние биты, чтобы получить более короткое представление.
Это основная идея сжатия.
В качестве другого примера рассмотрим восьмибайтовый шаблон
0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
и теперь повторяем его 2048 раз. . Один из способов следовать описанному выше подходу - представить байты с помощью трех битов.
000 0x41
001 0x42
010 0x43
011 0x44
100 0x45
101 0x46
110 0x47
111 0x48
Теперь мы можем представить вышеуказанный байтовый шаблон как 00000101 00111001 01110111 (это трехбайтовый шаблон 0x05 0x39 0x77 ) повторяется 2048 раз.
Но даже лучший подход состоит в том, чтобы представить байтовый шаблон
0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
одним битом 0 . Затем мы можем представить вышеупомянутый байтовый шаблон как 0 , повторенный 2048 раз, который становится байтом 0x00 , повторенным 256 раз. Теперь нам нужно сохранить только словарь
0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
и байтовый шаблон 0x00 , повторенный 256 раз, и мы сжали файл с 16 384 байтов до (по модулю словаря) 256 байтов.
Это в двух словах. как работает сжатие. Весь бизнес сводится к поиску коротких и эффективных представлений байтов и байтовых последовательностей в заданном файле. Это простая идея, но детали (поиск изображения) могут быть довольно сложными.
См., Например: