мне относительно недавно сын, заканчивающий MIT на пальцах объяснил как работает RAID-5 и как он ухитряется восстанавливать информацию в конфигурации например 7 дисков +1, когда казалось бы куда там и как оно возможно. Оказалось, что идея настолько проста, что просто офигеть.
Хаффман использовался в архиваторе HA, еще активно используется в линиях передачи. Морзе, кстати, на той же идее базируется - чем чаще используется символ - тем короче цепочка.
В ZIP же основа архивации - сворачивание цепочек алгоритмом на основе Lempel-Zive.
На самом деле Хаффман не очень для файловой архивации - цепочка нулей, скажем, длинной в 1 мегабайт всё равно будет 1/8 мегабайта, не меньше. В том время как LZ превратит это в 5 байт грубо говоря - (dword: 1024*1024) byte: 0
Сразу вспомнился алгоритм архивации "sort-drop-RLE". Сортируем биты в файле по возрастанию: нули вперёд, единицы назад. Лидирующие нули ничего не значат, поэтому их отбрасываем. А единицы архивируем, просто пересчитав их, и записав в архив общее количество. Разархивация - в обратном порядке.
Это я к тому, что дидактичнее было бы пробелы тоже включить в дерево. Ну, и упомянуть про LZ, а то может создаться впечатление, что zip - это только Хаффман.
Чего-то я не вкурил, а откуда возьмётся информация о том, где стояла какая-то единица?
Или это шутка такая?
> Это я к тому, что дидактичнее было бы пробелы тоже включить в дерево.
Думаешь? Ну, дерево было бы немного посложнее, после добавления м к дереву со стоимостью 4 оказалось бы дешевле создать отдельное поддерево с листьями а и пробелом, а потом уже слить их. Не знаю, насколько это прибавляет наглядности.
> откуда возьмётся информация о том, где стояла какая-то единица?
Оттуда же, откуда возьмётся информация о расположении пробелов в фразе про маму и Раму, то есть - ниоткуда. То есть, это шутка конечно, но строго в тему.
> Не знаю, насколько это прибавляет наглядности.
Ну, как бы, выкидывание пробелов наглядность несколько убавляет, потому что либо создаёт обманчивое впечатление, что пробелы (или нули, как у меня) можно просто выкинуть, "они же ничего не значат", либо вызывает законные вопросы "а как их потом восстановить-то, в примере об этом ничего не сказано". И вообще, в качестве учебных примеров как-то обычно используют примеры удобные и при этом корректные, а не просто удобные :-)
Comments 9
Reply
Reply
В ZIP же основа архивации - сворачивание цепочек алгоритмом на основе Lempel-Zive.
На самом деле Хаффман не очень для файловой архивации - цепочка нулей, скажем, длинной в 1 мегабайт всё равно будет 1/8 мегабайта, не меньше. В том время как LZ превратит это в 5 байт грубо говоря - (dword: 1024*1024) byte: 0
Reply
Емнип, там Deflate -- сочетание LZ и Huffman.
> На самом деле Хаффман не очень для файловой архивации - цепочка нулей, скажем, длинной в 1 мегабайт всё равно будет 1/8 мегабайта, не меньше.
Да, бывает намного лучше, безусловно. Но -- очень простой алгоритм зато, учебный.
Reply
Это не LZ, это RLE. LZ вроде ж по словарю работает и в такие фокусы просто не умеет.
Reply
Сразу вспомнился алгоритм архивации "sort-drop-RLE".
Сортируем биты в файле по возрастанию: нули вперёд, единицы назад.
Лидирующие нули ничего не значат, поэтому их отбрасываем.
А единицы архивируем, просто пересчитав их, и записав в архив общее количество.
Разархивация - в обратном порядке.
Это я к тому, что дидактичнее было бы пробелы тоже включить в дерево. Ну, и упомянуть про LZ, а то может создаться впечатление, что zip - это только Хаффман.
Reply
Чего-то я не вкурил, а откуда возьмётся информация о том, где стояла какая-то единица?
Или это шутка такая?
> Это я к тому, что дидактичнее было бы пробелы тоже включить в дерево.
Думаешь? Ну, дерево было бы немного посложнее, после добавления м к дереву со стоимостью 4 оказалось бы дешевле создать отдельное поддерево с листьями а и пробелом, а потом уже слить их. Не знаю, насколько это прибавляет наглядности.
Reply
Оттуда же, откуда возьмётся информация о расположении пробелов в фразе про маму и Раму, то есть - ниоткуда.
То есть, это шутка конечно, но строго в тему.
> Не знаю, насколько это прибавляет наглядности.
Ну, как бы, выкидывание пробелов наглядность несколько убавляет, потому что либо создаёт обманчивое впечатление, что пробелы (или нули, как у меня) можно просто выкинуть, "они же ничего не значат", либо вызывает законные вопросы "а как их потом восстановить-то, в примере об этом ничего не сказано". И вообще, в качестве учебных примеров как-то обычно используют примеры удобные и при этом корректные, а не просто удобные :-)
Reply
Reply
Leave a comment