Целочисленный алгоритм сжатия CSV

Question

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

Моя цель - сжать большое количество структурированных целых чисел, разделенных запятыми. Есть ли известный алгоритм для такого? Если нет, где можно было бы начать читать некоторые интересующие нас области, которые помогут мне начать разработку такого алгоритма? Конечно, алгоритм должен быть обратимым и потерять, чтобы я мог распаковать сжатые данные для извлечения значений csv.

Структура данных представляет собой массив из трех значений, домен первого номера от 0 до 4, второй - от 0 до 6, третий - от 0 до n, где n не является большим числом. Эта структура повторяется для создания данных, которые находятся в двухмерном массиве.

Answer 1

Использование стандартных алгоритмов сжатия, таких как gzip или bzip2, для структурированных данных не дает оптимальной эффективности сжатия, поэтому построение конкретного случая алгоритма выполнило трюк.

Ниже приведен пример структуры данных.

// cell: a data structure, array of three numbers 
// digits[0]: { 0, 1, 2, 3, 4 } 
// digits[1]: { 0, 1, 2, 3 } 
// digits[2]: { 0, 1, 2, ..., n } n is not an absurdly large number 
// Below it is reused in a multi-dimensional array. 
var cells = [ 
    [ [3, 0, 1], [4, 2, 4], [3, 0, 2], [4, 1, 3] ], 
    [ [4, 2, 3], [3, 0, 3], [4, 3, 3], [1, 1, 0] ], 
    [ [3, 3, 0], [2, 3, 1], [2, 2, 5], [0, 2, 4] ], 
    [ [2, 1, 0], [3, 0, 0], [0, 2, 3], [1, 0, 0] ] 
]; 

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

• GZ сжатого от 171 до 88 байт
• bzip2 сжат с 171 до 87 байт
• Deflate сжат с 171 до 76 байт

алгоритм я строител cted сжал данные до 33 байтов до n = 192. Так что на конкретном случае я смог сжать свои данные с более чем двойной эффективностью стандартных алгоритмов сжатия текста.

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

Поскольку я нацелен на удобство использования человеком (сжатый код будет напечатан), я использовал базу 62, которую я представлял как {[0-9], [a-z], [A-Z]} от 0 до 61 соответственно. Я забуферировал длину ячейки при преобразовании в Base62 на две цифры. Это позволило использовать 62 * 62 (3844) различные комбинации ячеек.

Наконец, я добавил базовую цифру 62 в начале сжатой строки, которая представляет количество столбцов. При распаковке размера y используется для вывода размера x из длины строки. Таким образом, данные могут быть правильно распакованы без потери данных.

Сжатый строка приведенного выше примера выглядит следующим образом:

var uncompressed = compress(cells); // "4n0w1H071c111h160i0B0O1s170308110" 

Я представил объяснение моего метода, чтобы решить мою проблему, чтобы помочь другим столкнулись с подобной проблемой. Я не предоставил свой код по причинам безвестности.

TL; DR

Для сжатия структурированных данных:

1. Представляет дискретный объект как целое
2. закодировать основание 10 целое число к более высокому основанию
3. Повторите для всех объектов
4. Добавить количество строк или столбцов в сжатую строку

Для того, чтобы распаковать структурированные данные:

1. прочитать строки или столбцы и выводить другие из длины строки
2. Обратных шаги 1 и 2 при сжатии
3. Повторите для всех объектов

Answer 2

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

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