Существуют ли алгоритмы переупорядочения данных для оптимизации для сжатия? Я понимаю, что это специфично для данных и алгоритма сжатия, но есть ли слово для этой темы? Где я могу найти исследования в этой области?
В частности, у меня есть список json с 1,5 миллионами строк, и я хочу изменить порядок строк, чтобы оптимизировать сжатие gzip (для HTTP). Сортировка строк довольно хороша, но я не знаю, насколько это оптимально.
optimization
permutations
Jayen
источник
источник
Ответы:
Это дополнение к ответу Навин Гоял.
Поскольку файл JSON можно рассматривать как древовидную структуру данных, вы можете использовать XBW-преобразование для деревьев, которое является расширением преобразования Берроуза-Уилера для строк.
источник
Burrows - преобразование Уилера - это хорошо известный алгоритм сжатия, который работает путем переупорядочения символов в строке, подлежащей сжатию.
источник
Чтобы улучшить сжатие gzip, вы хотите, чтобы «похожие» строки были в списке близкими. Есть несколько способов определить такое сходство; позвольте мне описать разумный, который хорошо работает на практике. Напомним, что размер блока gzip составляет 64 КБ. Таким образом, ваши данные будут разбиты на блоки размером 64 КБ, и каждый блок будет сжат независимо. Чтобы оптимизировать сжатие, необходимо минимизировать количество отдельных k-мер (подстрок размера k) в каждом блоке. Мотивация заключается в том, что все такие подстроки будут заменены идентификатором.
Хотя вышеупомянутая проблема сложна в теории (это вариант разбиения гиперграфа), существуют быстрые практические алгоритмы. Я бы порекомендовал LSH-подобную кластеризацию, которая может быть реализована за один проход ваших данных. Обратите внимание, что (в алфавитном порядке) сортировка является еще одним способом «кластеризовать» похожие строки вместе. Однако специализированные алгоритмы кластеризации могут работать лучше.
Альтернативой является использование zstd , которое (i) быстрее, (ii) получает более высокие коэффициенты сжатия и (iii) не имеет ограничений на размер блока (и, таким образом, сжимает строки одинаково хорошо независимо от порядка ввода).
источник
Некоторое время назад я видел алгоритм, который может быть полезен. Он использует алгоритм редактирования расстояния для вычисления расстояния между каждым словом. Таким образом, он строит график, вес каждого ребра которого составляет это расстояние. Наконец, он получает заказ, выбирая путь с наименьшей суммой весов. Может быть, это может улучшить GZIP.
источник