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

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

Например:

Вход Общий префикс Сжатый вывод 
myxa
myxophyta
myxopod
nab
nabbed
nabbing
nabit
nabk
nabob
nacarat
nacelle

no preceding word
'myx'
'myxop'
no common prefix
'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 байт

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

Приложения

Инкрементное кодирование широко используется при поиске информации для сжатия лексиконов, используемых в поисковых индексах ; в них перечислены все слова, найденные во всех документах, и указатель для каждого из них на список местоположений. Обычно он сжимает эти показатели примерно на 40%.

В качестве одного примера, инкрементное кодирование используется в качестве отправной точки утилитой GNU locate в указателе имен файлов и каталогов. GNU найти коммунальное дальнейшее использование Биграммных кодирований для дальнейшего сокращения популярных Filepath префиксов.

Рекомендации

  1. ^ Ян Х. Виттен, Алистер Моффат, Тимоти С. Белл. Управление гигабайтами. Второе издание. Академическая пресса. ISBN   1-55860-570-3 . Раздел 4.1: Доступ к лексикону, подраздел Переднее кодирование, стр. 159–161.