Инкрементное кодирование , также известное как переднее сжатие , обратное сжатие или переднее кодирование , представляет собой тип алгоритма сжатия дельта-кодирования , при котором общие префиксы или суффиксы и их длины записываются, чтобы их не нужно было дублировать. Этот алгоритм особенно хорошо подходит для сжатия отсортированных данных , например списка слов из словаря .
Например:
Кодировка, используемая для хранения общей длины префикса, варьируется от приложения к приложению. Типичными методами являются сохранение значения в виде одного байта; дельта-кодирование , в котором сохраняется только изменение длины общего префикса; и различные универсальные коды . Его можно комбинировать с другими общими методами сжатия данных без потерь, такими как энтропийное кодирование и словарные кодеры, для сжатия оставшихся суффиксов.
Инкрементное кодирование широко используется при поиске информации для сжатия лексиконов, используемых в поисковых индексах ; в них перечислены все слова, найденные во всех документах, и указатель для каждого из них на список мест. Обычно он сжимает эти индексы примерно на 40%. [1]
В качестве примера, инкрементное кодирование используется в качестве отправной точки утилитой поиска GNU в индексе имен файлов и каталогов. Утилита GNUlocate дополнительно использует биграммное кодирование для дальнейшего сокращения популярных префиксов путей к файлам.