Изменение порядка данных (набор строк) для оптимизации для сжатия?

12

Существуют ли алгоритмы переупорядочения данных для оптимизации для сжатия? Я понимаю, что это специфично для данных и алгоритма сжатия, но есть ли слово для этой темы? Где я могу найти исследования в этой области?

В частности, у меня есть список json с 1,5 миллионами строк, и я хочу изменить порядок строк, чтобы оптимизировать сжатие gzip (для HTTP). Сортировка строк довольно хороша, но я не знаю, насколько это оптимально.

Jayen
источник
1
Оптимальное переупорядочение строк для сжатия gzip (LZ77 с небольшим скользящим окном) звучит как NP-сложная задача. Вы можете, вероятно, придумать сокращение от самой короткой общей проблемы суперструн.
Джоуни Сирен
@ JouniSirén Я думаю, что самая длинная общая подстрока - лучший подход, так как самая короткая общая суперструна ограничивает меня наличием общей части спина к спине, верно? Я не возражаю против NP-харда, пока он податлив (например, для бега на современной машине требуется целый день).
Jayen

Ответы:

6

Это дополнение к ответу Навин Гоял.

Поскольку файл JSON можно рассматривать как древовидную структуру данных, вы можете использовать XBW-преобразование для деревьев, которое является расширением преобразования Берроуза-Уилера для строк.

Хироки Янагисава
источник
1
Спасибо за это. У меня есть только список / массив JSON, а не объекты JSON, поэтому я не понимаю, как его можно рассматривать как дерево. Я мог бы преобразовать строки в три, но тогда я не понимаю, как это связано с XBW-преобразованием.
Jayen
4

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

Навин Гоял
источник
1
Спасибо за это, но я не уверен, как я могу использовать эту информацию. Я хочу изменить порядок строк в списке для сжатия, но мне все равно, смогу ли я вернуть исходный порядок.
Jayen
1

Чтобы улучшить сжатие gzip, вы хотите, чтобы «похожие» строки были в списке близкими. Есть несколько способов определить такое сходство; позвольте мне описать разумный, который хорошо работает на практике. Напомним, что размер блока gzip составляет 64 КБ. Таким образом, ваши данные будут разбиты на блоки размером 64 КБ, и каждый блок будет сжат независимо. Чтобы оптимизировать сжатие, необходимо минимизировать количество отдельных k-мер (подстрок размера k) в каждом блоке. Мотивация заключается в том, что все такие подстроки будут заменены идентификатором.

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

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

Сергей Пупырев
источник
0

Некоторое время назад я видел алгоритм, который может быть полезен. Он использует алгоритм редактирования расстояния для вычисления расстояния между каждым словом. Таким образом, он строит график, вес каждого ребра которого составляет это расстояние. Наконец, он получает заказ, выбирая путь с наименьшей суммой весов. Может быть, это может улучшить GZIP.

Рафаэль Рибейро
источник
это не звучит, но если кто-то попробует это сделать, пожалуйста, оставьте комментарий с вашими результатами
Jayen
Я постараюсь проверить это. Мне интересно об этой проблеме. Кроме того, почему вы думаете, что это не поддается лечению?
Рафаэль Рибейру
насколько я знаю, расстояние редактирования равно O (нм), где n и m - количество букв в паре строк, и вы должны сделать это для каждой пары строк O (s ^ 2), поэтому, если n = м, это O (s ^ 2 * n ^ 2), что звучит трудно для меня за 1,5 миллиона строк.
Jayen
О, я не слишком беспокоился о сложности, потому что думал, что ваша проблема - уменьшить только двоичный размер. Так что эта операция будет происходить чаще, верно?
Рафаэль Рибейро
Я искал здесь, и, возможно, стоимость редактирования может быть уменьшена с помощью автоматов Левенштейна
Рафаэль Рибейро