Инкрементное кодирование

Инкреме́нтное коди́рование, также известное под названием фронтальное сжатие или тыловое сжатие, — это тип дельта-кодирования (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.