Введение

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

Входные данные | Общий префикс | Сжатый вывод
------- | -------- | --------
myxa | | 0 myxa
myxophyta | 'myx' | 3 ophyta
myxopod | 'myxop' | 5 od
nab | | 0 nab
nabbed | 'nab' | 3 bed
nabbing | 'nabb' | 4 ing
nabit | 'nab' | 3 it
nabk | 'nab' | 3 k
nabob | 'nab' | 3 ob
nacarat | 'na' | 2 carat
nacelleno | 'nac' | 3 elle

64 байта | | 46 байт

Способ кодирования длины общего префикса варьируется в зависимости от реализации. Типичные методы включают хранение значения в виде одного байта, дельта-кодирование (хранение только изменения длины общего префикса) и использование различных универсальных кодов. Его можно комбинировать с другими общими методами сжатия данных без потерь, такими как энтропийное кодирование и словарные кодировщики, для сжатия оставшихся суффиксов.

Приложения

Инкрементальное кодирование широко используется в информационном поиске для сжатия лексиконов, применяемых в поисковых индексах; эти лексиконы содержат список всех слов, найденных во всех документах, и указатель для каждого слова на список его позиций. Как правило, оно позволяет сжать эти индексы примерно на 40%. Например, инкрементальное кодирование используется в качестве основы утилитой GNU locate для индекса имён файлов и каталогов. Утилита GNU locate дополнительно использует bigram-кодирование для дальнейшего сокращения часто встречающихся префиксов путей к файлам.