Каковы хорошие стратегии для определения размера блока в алгоритме дефляции? - PullRequest
Новая
       12

Каковы хорошие стратегии для определения размера блока в алгоритме дефляции?

9 голосов
/ 27 января 2009

Я пишу библиотеку сжатия как небольшой побочный проект, и я достаточно далеко продвинулся (Моя библиотека может извлечь любой стандартный файл gzip, а также произвести совместимый (но, конечно, пока не оптимальный) вывод gzip), что время, чтобы выяснить значимую стратегию завершения блока. В настоящее время я просто обрезаю блоки после каждых 32 тыс. Входных данных (размер окна LZ77), потому что это было легко и быстро реализовать - теперь я возвращаюсь и пытаюсь реально повысить эффективность сжатия.

Спецификация Deflate может сказать только следующее: «Компрессор завершает блок, когда он определяет, что было бы полезно начать новый блок со свежими деревьями, или когда размер блока заполняет компрессор блок буфера ", что не так уж и полезно.

Я перебрал код SharpZipLib (как я полагал, что это будет наиболее читаемая реализация с открытым исходным кодом) и обнаружил, что он завершает блок каждые 16 тыс. Литералов вывода, игнорируя ввод. Это достаточно просто реализовать, но, похоже, должен быть более целенаправленный подход, особенно учитывая, что язык в спецификации «определяет, что начинать новый блок со свежих деревьев было бы полезно».

Так есть ли у кого-нибудь идеи для новых стратегий или примеры существующих?

Заранее спасибо!

Ответы [ 2 ]

2 голосов
/ 27 января 2009

Как предложение, чтобы вы пошли.

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

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

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

Простое ограничение его как минимум 8K выходными литералами, но предотвращение более 32K литералов в блоке приведет к относительно гибкой основе для попытки спекулятивных алгоритмов. вызвать 8K субблок.

Самый простой из которых (псевдокод): 

create empty sub block called definite
create empty sub block called specChange
create empty sub block called specKeep
target = definite
While (incomingData)
{
  compress data into target(s)    
  if (definite.length % SUB_BLOCK_SIZ) == 0)
  {
    if (targets is definite)
    {
      targets becomes 
        specChange assuming new block 
        specKeep assuming same block as definite
    }        
    else
    {
      if (compression specChange - OVERHEAD better than specKeep)
      {
        flush definite as a block.
        definite = specChange
        specKeep,specChange = empty
        // target remains specKeep,specChange as before 
        but update the meta data associated with specChange to be fresh
      }
      else 
      {
        definite += specKeep
        specKeep,specChange = empty
        // again update the block meta data
        if (definite is MAX_BLOCK_SIZE)
        {
          flush definite
          target becomes definite 
        }
      }
    }
  }
}
take best of specChange/specKeep if non empty and append to definite
flush definite.

OVERHEAD - некоторая константа для учета стоимости переключения блоков

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

Это может привести к созданию specChange, выполняемому только тогда, когда эвристика посчитает это разумным. Если эвристика окажется сильным индикатором, вы можете покончить со спекулятивным характером и просто решить поменяться в точке, несмотря ни на что.

0 голосов
/ 27 января 2009

Хм, мне нравится идея некоторого эвристического анализа, чтобы попытаться придумать некоторые "правила", для которых, когда завершение блока может быть полезным. Я посмотрю на ваш предложенный подход сегодня вечером и посмотрю, что я могу с ним сделать.

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

Вне моей головы, неясно, будет ли относительное распределение буквенных кодов в зависимости от длины, кодов расстояний, иметь конкретное влияние на оптимальный размер блока. Хорошая пища для размышлений.

...