Алгоритм поиска соответствия LZ4 (быстрое сканирование)

Я реализовал алгоритм сжатия на основе LZ77/LZ4 (без энтропийного кодирования), основанный на хеш-цепочках бесконечной глубины. Работает хорошо, скорость приемлемая, но степень сжатия близка к LZ4. Читая документацию и просматривая исходный код проекта LZ4, я понимаю, что он использует хэш-цепочку с глубиной 1, но если я установлю глубину своей реализации на 1, LZ4 превзойдет ее.

Я не могу понять, как работает алгоритм поиска соответствия LZ4 (быстрое сканирование). Может ли кто-нибудь объяснить это?

Спасибо.


compression lz4 lossless-compression
person user3368561    schedule 20.12.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

В процессе сканирования используется поиск по хешу. как следующее:

  1. Старые байты--------------анкор-------------Новые байты----текущие
  2. ч = хэш [int4]
  3. reference=hash.get(h)
  4. hash.put(h,current) for later matching
  5. int(ссылка)==int(текущий)? обрабатывать совпадения: повторить попытку
  6. обрабатывать спички

Переменная seachMatchNb — это способ пропуска для быстрого сопоставления, но может быть совпадение минут с потерями или нет.

Хэш-таблица представляет собой JIT-стиль, в котором сохраняются только смещения. Функция readIntEquals выполняет сопоставление ключей.

Просто игнорируйте его в режиме обучения.

person qinxian    schedule 21.08.2017