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

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

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

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

Это заготовка статьи об информационных технологиях и вычислительной технике. Помогите Википедии, дополнив её. Это примечание по возможности следует заменить более точным.

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (20 октября 2024)