Интернет магазин китайских планшетных компьютеров

Компьютеры - Инкрементное кодирование

Инкрементное кодирование, также известное под названием фронтальное сжатие или тыловое сжатие, — это тип дельта-кодирования, где общие префиксы или суффиксы и их длины записываются таким образом, чтобы избегать дублирования данных. Этот алгоритм хорошо подходит для сжатия отсортированных данных, например, списка слов в словаре.

Например:

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

Этот метод использовался как базовый для утилиты GNU locate в индексе имён файлов и каталогов. Также дельта-кодирование используется для длин общего префикса. Это означает дополнительный шаг, в котором вместо длины общего префикса используется изменение в длине общего префикса.

Несмотря на простоту, инкрементное кодирование может сохранить много памяти, особенно при использовании перед другими архиваторами, такими как gzip или bzip2.