Адские тиски правосудия

Косякин Антон

Xakep, номер #066, стр. 066-112-5

Подводный камень

Да-да-да. Такой присутствует. Дело в том, что если существует строка (СТРОКА СИМВОЛ), находящаяся в словаре, а часть входного потока - СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, то алгоритм сжатия выведет код, прежде чем распаковщик получит возможность определить его, и получится большая бяка. К счастью, такой исключительный случай всего один, и наш алгоритм распаковки можно без труда модифицировать. При считывании кода, еще не известного нам, нужно построить строку, код которой лежит в СТРОКА, взять первый ее символ и добавить в словарь пару (СТРОКА первый_ее_символ), затем СТРОКА=СИМВОЛ, и повторить стандартную процедуру для кода больше или равного 256, но без (!) вывода результата в выходной файл. Несмотря на запутанность, это очень легко реализуется и главное - работает!

Outro

Ну вот, сегодня я тебе поведал основы написания своего собственного архиватора. Конечно, то, что я рассказал, не поможет тебе победить по степени сжатия bzip2 или WinRAR, но, например, для некоторого уменьшения размера коллекции исходных кодов твоих программ - очень даже подойдет. Представь - хранить исходники собственных программ, сжатые собственным архиватором! По-моему, это стильно. Ну что ж, удачи в этом нелегком деле. А главное - не забывай читать умные книжки, без них жизнь юного сжимателя нынче трудна :).

WARNING

Как мудрый человек Тэрри Вэлч сразу же запатентовал свой алгоритм. Но в июне 2003 года срок патента истек, и теперь ты, наверное, даже можешь смело продавать свою коммерческую реализацию LZW.

INFO

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

CD

Обязательно загляни на наш CD. Там есть все необходимое.