оптимизация кодирования пары байтов

Question

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

Степень сжатия - с учетом отсутствия дальнейшей обработки, например, нет Хаффмана или арифметического кодирования - на удивление хорошо.

Однако время выполнения моей тривиальной реализации было меньше, чем звездное.

Как это можно оптимизировать? Можно ли сделать это за один проход?

Answer 1

Это краткое изложение моего прогресса на данный момент:

Googling нашел этот небольшой отчет, который ссылается на оригинальный код и ссылается на источник:

Филипп Гейдж, «Новый алгоритм» для сжатия данных », который появился в «The C Users Journal» - февраль Издание 1994 года.

Ссылки на код на сайте доктора Доббса не работают, но эта веб-страница отражает их.

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

Мои данные испытаний enwik8 из премии Хаттера .

|----------------|-----------------|
| Implementation | Time (min.secs) |
|----------------|-----------------|
| bpev2          | 1.24            | //The current version in the large text benchmark
| bpe_c          | 1.07            | //The original version by Gage, using a hashtable
| bpev3          | 0.25            | //Uses a list, custom sort, less memcpy
|----------------|-----------------|

bpev3 создает список всех орграфов; блоки имеют размер 10 КБ, и обычно выше порогового значения примерно 200 орграфов (из 4, что является наименьшим, который мы можем получить при сжатии байта); этот список отсортирован, и первая замена сделана.

При выполнении замен статистика обновляется; обычно в каждом проходе меняется только около 10 или 20 орграфов; они «раскрашиваются» и сортируются, а затем объединяются со списком орграфов; это значительно быстрее, чем просто всегда сортировать весь список орграфов при каждом проходе, так как список почти отсортирован.

Исходный код перемещался между байтовыми буферами 'tmp' и 'buf'; bpev3 просто меняет указатели буфера, что стоит около 10 секунд времени автономной работы.

Учитывая исправление замены буфера в bpev2, приведёт исчерпывающий поиск в соответствие с хэш-таблицей версии; Я думаю, что хеш-таблица является спорным значением, и что список является лучшей структурой для этой проблемы.

Его подоконник многоходовой, хотя. И поэтому это не совсем конкурентный алгоритм.

Если вы посмотрите на тестирование сжатия большого текста, был добавлен оригинальный bpe . Из-за больших размеров блоков он работает лучше, чем мой bpe на enwik9. Кроме того, разрыв в производительности между хэш-таблицами и моими списками гораздо ближе - я сократил до march=PentiumPro, который использует LTCB.

Есть, конечно, случаи, когда это подходит и используется; Symbian используйте его для сжатия страниц в образах ПЗУ. Я предполагаю, что 16-битная природа двоичных файлов Thumb делает этот подход простым и полезным; сжатие выполняется на ПК, а декомпрессия - на устройстве.

Answer 2

Я провел работу по оптимизации реализации сжатия LZF, и некоторые из тех же принципов, которые я использовал для улучшения производительности, можно использовать здесь.

Чтобы повысить производительность при кодировании пары байтов:

1. Ограничить размер блока до 65 КБ (возможно, оптимальным будет 8-16 КБ). Это гарантирует, что будут использоваться не все байты, и позволяет хранить информацию промежуточной обработки в ОЗУ.
2. Используйте хеш-таблицу или простую таблицу поиска по короткому целому числу (больше оперативной памяти, но быстрее), чтобы сохранить счетчики для пар байтов. Существует 65 656 пар 2 байтов и возможно BlockSize экземпляров (макс. размер блока 64к). Это дает вам таблицу из 128 тыс. Возможных выходных данных.
3. Распределение и повторное использование структур данных , способных хранить в памяти полный блок сжатия, таблицу замены, количество пар байтов и выходные байты. Это звучит бесполезно, но если вы считаете, что размер вашего блока невелик, это того стоит. Ваши данные должны полностью храниться в CPU L2 или (в худшем случае) кэш-памяти L3. Это дает БОЛЬШОЙ прирост скорости.
4. Сделайте один быстрый просмотр данных, чтобы собрать счет, ПОЧЕМУ беспокойтесь о создании таблицы замены.
5. Упакуйте байты в целые или короткие целые числа , когда это возможно (применимо в основном к C / C ++). Одна запись в таблице подсчета может быть представлена ​​целым числом (16-разрядный счет плюс пара байтов).

Answer 3

Код в JustBasic можно найти здесь вместе с входным текстовым файлом.

Just BASIC Files Archive - сообщение на форуме

EBPE от TomC 02/2014 - расширенная кодировка пар байтов

EBPE имеет две постпроцессы для кодирования пары байтов

---

1. Сжимает словарь (считается новинкой)

Словарная запись состоит из 3 байтов:

AA – the two char to be replaced by (byte pair)
 1 – this single token (tokens are unused symbols)

Итак, "AA1" говорит нам при декодировании, что каждый раз, когда мы видим "1" в файл данных, замените его на "AA".

Хотя возможны длинные серии последовательных токенов, давайте посмотрим на это Пример 8 токенов:

AA1BB3CC4DD5EE6FF7GG8HH9

Длина 24 байта (8 * 3)

Токен 2 отсутствует в файле, указывая, что он не был открытым токеном для использовать, или как-то иначе сказать: 2 было в исходных данных.

Мы видим, что последние 7 токенов 3,4,5,6,7,8,9 являются последовательными, поэтому в любое время мы увидеть последовательный прогон из 4 или более токенов, давайте изменим наш словарь так:

AA1BB3<255>CCDDEEFFGGHH<255>

Где <255> говорит нам, что подразумеваются токены для пар байтов и увеличиваются на 1 больше, чем последний маркер, который мы видели (3) . Мы увеличиваем на единицу, пока мы не увидим следующее <255>, указывающее конец пробега.

• Оригинальный словарь был 24 байта,
• Расширенный словарь составляет 20 байтов.

Я сохранил 175 байтов, используя это улучшение в текстовом файле, где токены 128 к 254 будет в последовательности, как и другие в целом, чтобы включить прогон, созданный предварительной обработкой строчных букв.

2. Сжимает файл данных

Повторное использование редко используемых символов в качестве токенов не является чем-то новым.

После использования всех символов для сжатия (кроме <255>), мы сканируем файл и находим один "j" в файле. Пусть этот символ делает двойной обязанность по:

• "<255>j" означает, что это литерал "j"
• "j" теперь используется в качестве токена для повторного сжатия,

Если j встречается 1 раз в файле данных, нам нужно добавить 1 <255> и 3-байтовая запись словаря, поэтому нам нужно сохранить более 4 байтов в BPE чтобы это того стоило.

Если j встречается 6 раз, нам понадобится 6 <255> и 3-байтовый словарь запись, поэтому нам нужно сохранить более 9 байтов в BPE, чтобы это того стоило.

В зависимости от того, возможно ли дальнейшее сжатие и сколько осталось байтовых пар в файле этот пост-процесс сэкономил более 100 байтов при тестовых запусках.

Примечание: При распаковке убедитесь, что не распаковываете каждые "j". Нужно посмотреть на предыдущий символ, чтобы убедиться, что это не <255> в порядке распаковать Наконец, после декомпрессии, удалите <255> восстановить исходный файл.

3. Что дальше в EBPE?

Неизвестно в это время

Answer 4

Вот новый БПЭ (http://encode.ru/threads/1874-Alba). Пример для компиляции, gcc -O1 alba.c -o alba.exe Это быстрее, чем по умолчанию.

Answer 5

Вы также можете оптимизировать словарь так, чтобы:

AA1BB2CC3DD4EE5FF6GG7HH8 - это последовательный прогон из 8 токенов.

Перепишите это как:

AA1<255>BBCCDDEEFFGGHH<255>, где <255> сообщает программе, что каждая из следующих пар байтов (до следующей <255>) является последовательной и увеличивается на единицу. Отлично работает для текста файлы и любые, где есть по крайней мере 4 последовательных токена.

сохранить 175 байтов в последнем тесте.

Answer 6

Да, держите нас в курсе.

гарантия

BobMcGee дает хороший совет. Тем не менее, я подозреваю, что «Ограничить размер блока до 65 кБ ... Это гарантирует, что будут использоваться не все байты», это не всегда так. Я могу сгенерировать (очень искусственный) двоичный файл длиной менее 1 кБ, в котором есть пара байтов, которая повторяется 10 раз, но не может быть сжата вообще с помощью BPE, поскольку она использует все 256 байтов - нет свободных байтов, которые BPE может использовать для представляют частую пару байтов.

Если мы ограничимся 7-битным текстом ASCII, у нас будет доступно более 127 свободных байтов, поэтому все файлы, которые повторяют пару байтов достаточное количество раз, могут быть сжаты как минимум BPE. Однако даже тогда я могу (искусственно) сгенерировать файл, который использует только символы isgraph () ASCII и имеет длину менее 30 КБ, что в конечном итоге достигает предела «нет свободных байтов» в BPE, даже несмотря на то, что остается еще пара байтов с более 4 повторов.

один проход

Это кажется , как будто этот алгоритм может быть слегка изменен, чтобы сделать это за один проход. Предполагая, что 7-битный открытый текст ASCII: Просканируйте входной текст, запомнив все пары байтов, которые мы видели в некоторой внутренней структуре данных, каким-то образом посчитав количество уникальных пар байтов, которые мы видели до сих пор, и скопировав каждый байт в выходной файл ( с высоким битовым нулем). Всякий раз, когда мы сталкиваемся с повторением, испускаем специальный байт, представляющий пару байтов (с высоким битом 1, поэтому мы не путаем буквенные байты с парами байтов). Включите во внутренний список байтовых «пар» этот специальный байт, чтобы компрессор мог впоследствии испустить другой специальный байт, который представляет этот специальный байт, плюс буквальный байт - так что чистый эффект этого другого специального байта должен представлять триплет , Как отметил Фкахлер, это звучит практически так же, как LZW.

EDIT: Очевидно, что ограничение «нет свободных байтов», которое я упомянул выше, в конце концов, не является внутренним ограничением всех компрессоров пары байтов, поскольку существует по крайней мере один компрессор пары байтов без этого ограничения.

Вы видели "SCZ - Простые утилиты сжатия и библиотека" ? SCZ является своего рода кодировщиком байтовых пар. SCZ, очевидно, дает лучшее сжатие, чем другие байтовые пары компрессоры , которые я видел, потому что SCZ не имеет ограничения «нет свободных байтов», о котором я говорил выше.

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

(SCZ использует специальный escape-байт E в сжатом тексте, который указывает, что следующий байт предназначен для буквального представления себя, а не для расширения в виде пары байтов. Это позволяет некоторому байту M в сжатом тексте выполнять двойную функцию: Два байта EM в сжатом тексте представляют M в простом тексте. Байт M (без предшествующего escape-байта) в сжатом тексте представляет некоторую пару байтов BP в простом тексте. Если некоторая пара байтов BP встречается много раз больше, чем M в незашифрованном тексте, то пространство, сэкономленное путем представления каждой пары байтов BP как одного байта M в сжатых данных, больше, чем пространство, «потерянное», представляя каждый M как два байта EM.)

Answer 7

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

Вот мои мысли с первого взгляда.Возможно, вы уже это сделали или уже подумали.

Я бы попробовал следующее.

Два настраиваемых параметра:

1. Количество вхождений пар байтов в чанкеданных, прежде чем рассмотреть вопрос о его замене.(Так что словарь не растет быстрее, чем сокращается фрагмент.)
2. Количество замен за проход, прежде чем, вероятно, заменять не стоит.(Так, чтобы алгоритм прекратил тратить время, когда, возможно, осталось только 1 или 2% для выигрыша.)

Я бы делал проходы, пока все еще стоит сжимать еще один уровень (согласно параметру2).Во время каждого прохода я буду вести подсчет байтовых пар на ходу.

Я бы немного поиграл с двумя параметрами и посмотрел, как это влияет на степень сжатия и скорость.Вероятно, они должны динамически изменяться в зависимости от длины сжимаемого фрагмента (и, возможно, одного или двух других факторов).

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

Держите нас в курсе, если вы попробуете что-то и получите интересные результаты!

Answer 8

самая простая эффективная структура - это двумерный массив, такой как byte_pair (255,255). Сбросьте счетчики и измените их при сжатии файла.