Первоначально опубликовано в блоге HonestRepair….. https://www.honestrepair.net/index.php/2019/03/08/xpress-an-experiment-in-data-compression/

Давным-давно я заинтересовался тем, как эффективно и с возможностью восстановления сжимать данные. Конечно, проблема сжатия данных уже давно решена Дэвидом А. Хаффманом из Массачусетского технологического института еще в 1952 году, а совсем недавно — Филом Кацем из PKZip. Хотя то, чему они научились тогда, не выдержало испытания временем.

Все, даже обычные пользователи компьютеров, знают, что такое сжатие данных. Они знают, что могут выбрать кучу файлов, заархивировать их, и получившийся «архив» файлов будет меньше по размеру и более переносим, ​​чем файлы, с которых они начали. Однако, помимо этого, сжатие данных для большинства остается загадкой.

Я из тех, кто любит «сворачивать свои собственные» вещи. Я лучше напишу библиотеку для приложения, чем буду полагаться на то, что сделал мой Google или Facebook. Когда я берусь за проект, мне нравится начинать как можно ближе к цепочке поставок. Обычно я пытаюсь начать с пары очень низкоуровневых зависимостей и наращивать их. Это помогает мне получить перспективу и понять, почему вещи делаются именно так, как они есть. Конечно, я кое-что дублирую, но копировать/вставлять код 30-летней давности нельзя.

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

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

Вот что я сделал. Я остановился на Python в качестве языка, потому что он довольно независим от платформы, популярен и универсален. Кроме того, Python — это весело! Затем я взял несколько случайных данных и начал искать закономерности. Я обнаружил, что шаблоны в данных чрезвычайно распространены, и с помощью некоторого эвристического анализа почти любой файл можно уменьшить, экстраполируя избыточные части файла и представляя эти части меньшим фрагментом данных. Таким образом, любому архиву, который я создаю, потребуется некоторая область, где он может хранить исходные данные, и небольшой уникальный ключ для определения того, где эти исходные данные находятся в сжатом файле. Этот «словарь», состоящий из индексов и соответствующих значений, необходимо будет встроить в архив, чтобы исходные данные можно было восстановить и восстановить позже. Также должна быть область для хранения самих данных в сжатой или несжатой форме. Наш архив уже формируется!

Теперь у нас есть область данных и область словаря. Нам нужно как-то разделить эти две области, чтобы их можно было различить во время извлечения. Мы можем сделать это, создав некоторую комбинацию префикса и суффикса, которая идет до и после словаря. Это позволит нам позже разделить сжатые и несжатые данные из словаря. Мы хотим, чтобы комбинация префикса и суффикса была чрезвычайно уникальной, чтобы она не смешивалась с данными и не пропускалась экстрактором, чтобы загрязнить восстановленные данные. Мы также хотим, чтобы префикс/суффикс был небольшим с точки зрения байтов. В конце концов, мы пытаемся сжимать файлы, а не увеличивать их!

В ПОРЯДКЕ! Итак, в нашем архивном файле теперь есть область для сжатых и несжатых данных, механизм разделения и словарь, состоящий из пар ключ/значение. «Ключ» — это небольшой идентификатор, а значение — исходные избыточные данные. Но как определить, где в исходных данных есть шаблоны, и построить на их основе словарь? Мы знаем, что шаблоны существуют почти в каждом файле, но нам нужен способ их извлечения, чтобы мы могли поместить их в наш словарь.

Мы, очевидно, хотим поместить содержимое нашего входного файла в память, чтобы мы могли выполнить с ним эту работу. Но файлы в наши дни могут быть намного больше, чем память нашей системы! Как мы будем обрабатывать большие файлы, если мы не можем поместить их в память?

Простой! Рубим их на кусочки! Нам просто нужно решить, сколько частей и насколько большими они должны быть. Мы можем определить идеальный размер наших частей, проверив, сколько памяти доступно и насколько велики наши файлы. Нам нужно будет хранить одну копию исходных данных и копию сжатых данных, а также наш словарь. Таким образом, наши фрагменты должны занимать чуть меньше 50% доступной памяти, так как нам нужно одновременно уместить примерно 2 копии фрагмента файла (плюс словарь и остальная часть нашего кода Python).

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

Сначала нам нужно посмотреть, насколько велик файл, и решить, насколько большими должны быть наши словарные записи. Файлы с большим количеством избыточных данных выиграют от больших записей словаря, в то время как файлы с меньшим количеством избыточных данных больше выиграют от меньших записей словаря. Таким образом, мы решим, насколько большими должны быть словарные статьи в зависимости от размера файла. Мы также решаем, когда прекратить сжатие, или, говоря другими словами; мы решаем, что стоит сжимать. Мы можем найти избыточные данные, которые настолько малы, что фактически увеличиваем их размер, представляя их с помощью словарного индекса. Нам нужен способ измерить нашу производительность сжатия, чтобы узнать, действительно ли мы добиваемся стоящего прогресса или просто тратим циклы ЦП впустую. Мы можем сделать это, установив порог сжатия в зависимости от размера файла. Большие файлы выиграют от более низкого порога, в то время как файлы меньшего размера должны иметь более высокий порог. По сути, мы смотрим на размер сжимаемых данных, и если он не уменьшается на [threshold]%, мы оставляем эти данные в несжатом виде. Для файлов с большим количеством избыточных данных, таких как текстовый файл, мы не хотим тратить время на сокращение 4 копий слова «кошка», когда мы могли бы улучшить сжатие, сократив вместо этого 3 копии фразы «корм для кошек». . Если бы мы были довольны простым сжатием слова «кошка», мы бы, вероятно, все равно создали отдельную словарную статью для слова «еда». Использование 2 записей словаря для выполнения работы 1 требует больше процессорного времени и большего объема памяти для представления.

Поэтому, если наше сжатие не дает результатов, мы ничего не сжимаем. Но если бы мы оставили все как есть, наш алгоритм сжатия не был бы таким уж алгоритмом сжатия, не так ли? Вместо того, чтобы сдаваться или делать расточительное количество словарных статей, мы можем настроить длину словарной статьи и попробовать еще раз. Конечно, должен быть верхний предел, когда мы решаем, что закончили попытки, иначе наша программа никогда не закончится! В настоящее время xPress попытается изменить длину словарной записи 9 раз, прежде чем сдаться. Он попытается увеличить, а затем уменьшить длину словарных записей, пока не найдет ту, которая дает результаты сжатия лучше, чем порог, который мы установили ранее.

Логический поток нашей программы в настоящее время выглядит примерно так…..

Для БОЛЬШИХ файлов…

LARGE_FILE.txt -> Файл больше 50% памяти -> Разбить файл на части -> Предсказать длину словарной записи -> Сканировать блок на наличие избыточных данных с шагом [длина словаря] -> Обнаружены избыточные данные -> Дублирующие данные не соответствуют пороговое значение при сжатии — › Запись несжатых данных — › Настройка длины словарной записи — › Сканирование фрагмента на наличие избыточных данных — › Найдены избыточные данные — › Избыточные данные ДЕЙСТВИТЕЛЬНО соответствуют пороговому значению при сжатии — › Запись сжатых данных — › Обновить словарь — › Сканирование фрагмента на наличие избыточных данных данные в приращениях [длина словаря] -› Не найдены избыточные данные -› Отрегулировать длину словарной записи -› КОНЕЦ ЧАНКА - › НАЧАТЬ НОВЫЙ ЧАНК -› Сканировать фрагмент на наличие избыточных данных….. …..ПОВТОРЯТЬ ДО КОНЦА ФАЙЛА ИЛИ РЕЗУЛЬТАТОВ СЖАТИЯ ›ПОРОГ -> Добавить словарь в выходной файл.

Для МАЛЕНЬКИХ файлов…

SMALL_FILE.txt -> Файл меньше 50% памяти -> Предсказать длину словарной записи -> Сканировать файл на наличие избыточных данных с шагом [длина словаря] -> Обнаружены избыточные данные -> При сжатии избыточные данные не достигают порогового значения -> Записать несжатые данные — › Отрегулировать длину словарной записи — › Сканировать файл на наличие избыточных данных — › Обнаружены избыточные данные — › Повторяющиеся данные ДЕЙСТВИТЕЛЬНО соответствуют пороговому значению при сжатии — › Записать сжатые данные — › Обновить словарь — › Сканировать файл на наличие избыточных данных в [длина словаря] приращения -> Дублирующие данные НЕ найдены -> Отрегулировать длину словарной записи -> Сканировать файл на наличие избыточных данных….. …..ПОВТОРЯТЬ ДО КОНЦА ФАЙЛА ИЛИ РЕЗУЛЬТАТОВ СЖАТИЯ›ПОРОГ ->Добавить словарь в выходной файл.

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

Извлекать данные из архива xPress намного проще. Мы просто отделяем словарь от конца архива и перебираем его, заменяя каждый экземпляр индекса словаря соответствующими исходными данными из словаря. Когда больше нет совпадений в словаре; архив распаковывается.

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

И это история о том, как я сделал свой собственный алгоритм сжатия, ничего не зная о сжатии. Я делаю это правильно? Я далеко от базы? Как бы вы сделали это лучше? Зайдите в официальный репозиторий Github и дайте мне знать или оставьте свои комментарии ниже!