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

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

Например:

Вход

Общий префикс

Сжатый вывод

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%. ^[1]

Например, инкрементное кодирование используется в качестве отправной точки утилитой поиска GNU в индексе имен файлов и каталогов. Утилита GNUlocate дополнительно использует биграммное кодирование для дальнейшего сокращения популярных префиксов путей к файлам.

Ссылки [ править ]

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