Комментарии 7
Для тех, кто первый раз читает про этот алгоритм:
Он был изобретён 70 лет назад и сильно устарел. Например, уже давно существует zstandard.
Например, уже давно существует zstandard.
Открываем википедию, читаем:
Zstandard combines a dictionary-matching stage (LZ77) [...], and Huffman coding (used for entries in the Literals section).
Я к тому, что кодирование Хаффмана никуда не делось — оно используется во многих алгоритмах сжатия данных в качестве одной из стадий.
Я не говорю, что не нужно знать базу, но писать про прошлое тысячелетие без какой либо новизны в 2020… Особенно, когда уже на хабре множество раз появлялись подобные статьи.
p.s.
Biga, спасибо за поддержку))
p.s.
Biga, спасибо за поддержку))
В целом вы правы, и минусуют вас зря. Но! Всё-таки zstandard — это название архиватора. zstandard внутри себя использует алгоритм FSE (Finite State Entropy), который в свою очередь является вариантом реализации метода энтропийного кодирования ANS (Asymmetric Numeral Systems). Другой вариант реализации ANS — алгоритм rANS. Эти два алгоритма с полным основанием можно назвать более современными, чем Хаффман, хотя во всех трёх при желании можно найти некоторое сходство с ним.
Прежде, чем Вы вдохновитесь методом сжатия Хаффмана (что неплохо),
и решите использовать его в своих проектах (что похвально),
либо вообще – вздумаете создавать свой алгоритм сжатия (что вообще круто),
стОит встать на табуретку
и окинуть все это взглядом сверху,
чтобы за формулами и крутыми решениями этого алгоритма
(да и вообще – всех остальных алгоритмов сжатия)
(если автор поста не бросит благое дело и продолжит писать следующие серии )
… ритма увидеть общую идею, общий подход.
А заключается он в том, что это все эти алгоритмы основаны на энтропии.
Или, говоря по-русски, на том, что некоторые символы в сообщении (файле) встречаются «часто», а другие символы – «редко».
В противном случае все эти алгоритмы сжатия ничего сжимать не будут.
(домашнее задание: попробуйте заархивировать (сжать) любой файл JPG — любым архиватором, и сравните размер сжатого файла – и оригинального JPG )
(Прим.: не проводите экспреимент дома, и желательно, чтобы рядом был кто-то из взрослых)
А теперь чуть подробнее по Хаффману.
Допустим, на представление каждого символа мы тратим 8 бит.
1) Красота идеи в том, чтобы те символы, которые в нашем условном файле встречаются часто – кодировать не 8 битами – а более коротко — 2..7 битами, зато те символы, которые встречаются редко – 9 битами и более.
( И да, для этого, прежде всего, Вам придется прочесть весь исходный файл,
и составить таблицу частоты появления всех символов).
2) Эти наши короткие цепочки битов должны быть не-префиксными, тоесть однозначно указывать единственный вариант прочтения, иначе потом, при чтении (декодировании) нам никак не узнать, где заканчивается «короткий» символ.
Например, «короткий» символ всегда начинается и оканчивается на ноль:
010 0110 01110 0111110 итд
Тогда мы точно знаем, что 0101 – это не «короткий» символ, потому что он содржит 010, а у нас это запрещено – наши «короткие» символы «не-префиксные» — т е никак не могут быть началом другого символа.
2.1) В реальности, таких «коротких» символов получится немного, всего штук 10-15, дальше они начнут удлиняться и теряется весь смысл в «укорачивании».
2.2) Как сказал бы Задорнов: «подождите смеяться! (с)».
В смысле радоваться.
Если у нас, например, имеется 8 коротких символов, то другие 8 «оригинальных» символов из нашего файла, придется обозначать уже не 8 битами, а, по кр мере, 9 битами.
Если у нас в файле каких то символов много больше чем других, а каких то – много меньше, то «сжатие» произойедет.
Если же частота повторения символов одинакова, или даже различная, но отличается не намного – «сжатый» файл получится длиннее, чем оригинальный.
В описаниях алгоритмов сжатия, для примеров, как правило, используют буквенные «сообщения».
В натуральных языках частота повторения разных букв неодинакова (и заранее известна).
В случае, если вы намерены сжимать не текст, а просто набор данных, то часто количество разных байт в этом файле — примерно одинаково, и тогда сжать ничего не получится и никаким алгоритмом.
На сладкое: поищите в сети про «ZIP-бомбу».
Это когда, например, Вы создаете файл из 100500 мильонов «единиц» и одного «нуля» (можно наоборот), затем сжимаете архиватором, и посылает кому то этот файлик в 1 килобайт.
… дец Сюрприз наступит при попытке его раскрыть.
и решите использовать его в своих проектах (что похвально),
либо вообще – вздумаете создавать свой алгоритм сжатия (что вообще круто),
стОит встать на табуретку
и окинуть все это взглядом сверху,
чтобы за формулами и крутыми решениями этого алгоритма
(да и вообще – всех остальных алгоритмов сжатия)
(если автор поста не бросит благое дело и продолжит писать следующие серии )
… ритма увидеть общую идею, общий подход.
А заключается он в том, что это все эти алгоритмы основаны на энтропии.
Или, говоря по-русски, на том, что некоторые символы в сообщении (файле) встречаются «часто», а другие символы – «редко».
В противном случае все эти алгоритмы сжатия ничего сжимать не будут.
(домашнее задание: попробуйте заархивировать (сжать) любой файл JPG — любым архиватором, и сравните размер сжатого файла – и оригинального JPG )
(Прим.: не проводите экспреимент дома, и желательно, чтобы рядом был кто-то из взрослых)
А теперь чуть подробнее по Хаффману.
Допустим, на представление каждого символа мы тратим 8 бит.
1) Красота идеи в том, чтобы те символы, которые в нашем условном файле встречаются часто – кодировать не 8 битами – а более коротко — 2..7 битами, зато те символы, которые встречаются редко – 9 битами и более.
( И да, для этого, прежде всего, Вам придется прочесть весь исходный файл,
и составить таблицу частоты появления всех символов).
2) Эти наши короткие цепочки битов должны быть не-префиксными, тоесть однозначно указывать единственный вариант прочтения, иначе потом, при чтении (декодировании) нам никак не узнать, где заканчивается «короткий» символ.
Например, «короткий» символ всегда начинается и оканчивается на ноль:
010 0110 01110 0111110 итд
Тогда мы точно знаем, что 0101 – это не «короткий» символ, потому что он содржит 010, а у нас это запрещено – наши «короткие» символы «не-префиксные» — т е никак не могут быть началом другого символа.
2.1) В реальности, таких «коротких» символов получится немного, всего штук 10-15, дальше они начнут удлиняться и теряется весь смысл в «укорачивании».
2.2) Как сказал бы Задорнов: «подождите смеяться! (с)».
В смысле радоваться.
Если у нас, например, имеется 8 коротких символов, то другие 8 «оригинальных» символов из нашего файла, придется обозначать уже не 8 битами, а, по кр мере, 9 битами.
Если у нас в файле каких то символов много больше чем других, а каких то – много меньше, то «сжатие» произойедет.
Если же частота повторения символов одинакова, или даже различная, но отличается не намного – «сжатый» файл получится длиннее, чем оригинальный.
В описаниях алгоритмов сжатия, для примеров, как правило, используют буквенные «сообщения».
В натуральных языках частота повторения разных букв неодинакова (и заранее известна).
В случае, если вы намерены сжимать не текст, а просто набор данных, то часто количество разных байт в этом файле — примерно одинаково, и тогда сжать ничего не получится и никаким алгоритмом.
На сладкое: поищите в сети про «ZIP-бомбу».
Это когда, например, Вы создаете файл из 100500 мильонов «единиц» и одного «нуля» (можно наоборот), затем сжимаете архиватором, и посылает кому то этот файлик в 1 килобайт.
А как вы отличите кодирование символа 'a' от кодирования символа 'd' в вашем примере? Может быть это комбинация символов 'ab'!?
Кстати, где источник? Похоже оригинальная статья уже не существует.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм сжатия Хаффмана