Ответ 1

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

Возьмем строку длиной в 25 байт Blah blah blah blah blah! (200 бит) из Пример объяснения алгоритма дефляции.

Наивный подход

Наивный подход заключался бы в кодировании каждого символа с кодовым словом той же длины. У нас есть 7 разных символов и, следовательно, нужны коды с длиной ceil(ld(7)) = 3. Наши кодовые слова могут выглядеть так:

000 → "B"
001 → "l"
010 → "a"
011 → "h"
100 → " "
101 → "b"
110 → "!"
111 → not used

Теперь мы можем кодировать нашу строку следующим образом:

000 001 010 011 100 101 001 010 011 100 101 001 010 011 100 101 001 010 110
B   l   a   h   _   b   l   a   h   _   b   l   a   h   _   b   l   a   !

Для этого потребуется только 25 · 3 бит = 75 бит для кодированного слова плюс 7 · 8 бит = 56 бит для словаря, таким образом 131 бит (65,5%)

Или для последовательностей:

00 → "lah b"
01 → "B"
10 → "lah!"
11 → not used

Закодированное слово:

01 00    00    00    00    10
B  lah b lah b lah b lah b lah!

Теперь нам просто нужно 6 · 2 бит = 12 бит для кодированного слова и 10 · 8 бит = 80 бит плюс 3 · 8 бит = 24 бит для длины каждого слова, таким образом 116 бит (58,0%).

Подход кода Хаффмана

код Хаффмана используется для кодирования более частых символов/подстрок с более коротким кодом, чем менее частые:

5 × "l", "a", "h"
4 × " ", "b"
1 × "B", "!"

// or for sequences

4 × "lah b"
1 × "B", "lah!"

Возможный код Хаффмана для этого:

0      → "l"
10     → "a"
110    → "h"
1110   → " "
11110  → "b"
111110 → "B"
111111 → "!"

Или для последовательностей:

0  → "lah b"
10 → "B"
11 → "lah!"

Теперь наш Blah blah blah blah blah! может быть закодирован:

111110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 111111
B      l a  h   _    b     l a  h   _    b     l a  h   _    b     l a  h   _    b     l a  h   !

Или для последовательностей:

10 0     0     0     0     11
B  lah b lah b lah b lah b lah!

Теперь для первого кода требуется только 78 бит или 8 бит вместо 25 · 8 = 200 бит, как и наша начальная строка. Но нам еще нужно добавить словарь, где хранятся наши символы/последовательности. Для нашего примера для каждого символа нам понадобится 7 дополнительных байтов (7 · 8 бит = 56 бит), и нашему примеру для каждой последовательности потребуется снова 7 байтов плюс 3 байта для длины каждой последовательности (таким образом, 59 бит). Это приведет к:

56 + 78 = 134 bit (67.0%)
59 +  8 =  67 bit (33.5%)

Действительные цифры могут быть неверными. Не стесняйтесь редактировать/исправлять его.

Ответ 2

Отметьте эту страницу вики...

Алгоритмы сжатия без потерь обычно используют статистическую избыточность таким образом, чтобы представлять данные отправителя более сжато без ошибок. Сжатие без потерь возможно, поскольку большинство данных реального мира имеют статистическую избыточность. Например, в тексте на английском языке буква "e" встречается гораздо чаще, чем буква "z", а вероятность того, что буква "q" будет сопровождаться буквой "z", очень мала.

Другой тип сжатия, называемый сжатием данных с потерями или перцепционным кодированием, возможен, если допустима некоторая потеря верности. Как правило, сжатие данных с потерями будет определяться исследованиями о том, как люди воспринимают данные, о которых идет речь. Например, человеческий глаз более чувствителен к тонким изменениям яркости, чем к изменениям цвета. Сжатие изображений JPEG частично работает, "округляя" часть этой менее важной информации. Сжатие данных Lossy обеспечивает способ получения наилучшей точности для заданного количества сжатия. В некоторых случаях желательно прозрачное (незаметное) сжатие; в других случаях верность приносится в жертву, чтобы как можно больше уменьшить количество данных.

Схемы сжатия без потерь обратимы, поэтому исходные данные могут быть восстановлены, а схемы с потерями принимают некоторую потерю данных для достижения более высокого сжатия.

Однако алгоритмы сжатия без потерь не будут сжимать некоторые файлы; действительно, любой алгоритм сжатия обязательно не сжимает любые данные, не содержащие различимых паттернов. Поэтому попытки сжатия сжатых данных, как правило, обычно (текстовые файлы, как правило, могут быть сжаты больше после сжатия из-за меньшего количества символов), приводят к расширению, а также будут пытаться сжать все, кроме самых зашифрованных данных.

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

Примером сжатия без потерь и потери является следующая строка:

25.888888888

Эта строка может быть сжата как:

25.[9]8

Интерпретируется как "двадцать пять очков 9 восьмерок", оригинальная строка прекрасно воссоздана, просто написана в меньшей форме. В системе с потерями, используя

26

вместо этого исходные данные теряются, при меньшем размере файла.

Ответ 3

Алгоритмы сжатия без потерь преобразуют каждый возможный вход в отдельные выходы таким образом, что более общие входы преобразуются в более короткие выходы. Математически невозможно, чтобы все возможные входные данные были сжаты - в противном случае у вас будет несколько вводов A и B, сжимающих одну и ту же форму, поэтому, когда вы распаковываете их, вернитесь к A или обратно в B? На практике наиболее полезная информация имеет некоторую избыточность, и эта избыточность соответствует определенным шаблонам; поэтому данные могут с пользой быть сжаты, потому что случаи, которые расширяются, когда вы сжимаете их, естественно не возникают.

Утраченное сжатие, например, используемое в сжатии JPEG или MP3, работает путем аппроксимации входных данных некоторым сигналом, который может быть выражен в меньшем количестве бит, чем оригинал. Когда вы распаковываете его, вы не получаете оригинал, но обычно получаете что-то достаточно близко.

Ответ 4

В ОЧЕНЬ простых терминах общая форма сжатия - http://en.wikipedia.org/wiki/Dictionary_coder. Это предполагает замену более длинных повторяющихся строк короткими.

Например, если у вас есть файл, который выглядит так:

"Monday Night","Baseball","7:00pm"
"Tuesday Night","Baseball","7:00pm"
"Monday Night","Softball","8:00pm"
"Monday Night","Softball","8:00pm"
"Monday Night","Baseball","5:00pm"

Это будет примерно 150 символов, но если вы сделаете простую замену следующим образом: A = "В ночь на понедельник", B = "Вторник", C = "Бейсбол", D = "Софтбол", E = "7:00 pm", F = "8:00 pm", G = 5: 00pm "

Затем одно и то же содержимое может быть закодировано как:

A,C,E
B,C,E
A,D,F
A,D,F
A,C,G

Использование на 25 символов! Умный наблюдатель мог также увидеть, как легко уменьшить это до 15 символов, если мы предположили еще кое-что о формате файла. Очевидно, что есть накладные расходы на ключ замены, но часто очень большие файлы имеют много этих подстановок. Это может быть очень эффективным способом сжимать большие файлы или структуры данных и допустить, чтобы они были "несколько" читаемыми человеком.

Ответ 5

Rosetta Code имеет запись в кодировке Хаффмана, как и предыдущий в блоге.