Инкрементное кодирование
Инкреме́нтное коди́рование, также известное под названием фронтальное сжатие или тыловое сжатие, — это тип дельта-кодирования (delta encoding), где общие префиксы или суффиксы и их длины записываются таким образом, чтобы избегать дублирования данных. Этот алгоритм хорошо подходит для сжатия отсортированных данных, например, списка слов в словаре.
Например:
Входные данные | Общий префикс | Сжатый вывод |
---|---|---|
myxa myxophyta myxopod nab nabbed nabbing nabit nabk nabob nacarat nacelle |
начало данных 'myx' 'myxop' нет общего префикса 'nab' 'nabb' 'nab' 'nab' 'nab' 'na' 'nac' |
0 myxa 3 ophyta 5 od 0 nab 3 bed 4 ing 3 it 3 k 3 ob 2 carat 3 elle |
64 байт | 46 байт |
Этот метод использовался как базовый для утилиты GNU locate в индексе имён файлов и каталогов. Также дельта-кодирование (delta encoding) используется для длин общего префикса. Это означает дополнительный шаг, в котором вместо длины общего префикса используется изменение в длине общего префикса.
Несмотря на простоту, инкрементное кодирование может сохранить много памяти, особенно при использовании перед другими архиваторами, такими как gzip или bzip2.
Это статья-заготовка об информационных технологиях и вычислительной технике. Помогите Википедии, дополнив эту статью, как и любую другую. |
Для улучшения этой статьи желательно:
|