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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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