Простой API для произвольного доступа в сжатый файл данных

Question

Пожалуйста, порекомендуйте технологию, подходящую для следующей задачи.

У меня довольно большой (500 МБ) блок данных, который в основном представляет собой матрицу чисел.Энтропия данных низкая (она должна быть хорошо сжимаемой), а хранилище дорого там, где оно находится.

То, что я ищу, - это сжать его с помощью хорошего алгоритма сжатия (как, скажем, GZip) с маркерами, которые обеспечивают очень случайный произвольный доступ.Произвольный доступ, как в случае «чтения байта из местоположения [64-битный адрес] в исходном (несжатом) потоке».Это немного отличается от классических библиотек дефлятора, таких как ZLIB, которые позволят вам постоянно распаковывать поток.Что я хотел бы, так это иметь произвольный доступ с задержкой, скажем, до 1 МБ распаковки на чтение байтов.

Конечно, я надеюсь использовать существующую библиотеку, а не изобретать колесо NIH.

Answer 1

Если вы работаете на Java, я только что опубликовал библиотеку для этого: http://code.google.com/p/jzran.

Answer 2

Если вы хотите свести к минимуму работу, я просто разбил бы данные на 1 МБ (или что-то еще), а затем поместил их в архив PKZIP. Затем вам понадобится чуть-чуть кода внешнего интерфейса, чтобы взять смещение файла, и разделить на 1M, чтобы получить нужный файл для распаковки (и, очевидно, использовать оставшуюся часть, чтобы получить правильное смещение в этом файле). 1001 *

Изменить: Да, существует код для обработки этого. Последние версии распаковки Info-zip (версия 6.0 актуальна) включают api.c. Среди прочего, в том числе UzpUnzipToMemory - вы передаете ему имя ZIP-файла и имя одного из файлов в этом архиве, который вы хотите получить. Затем вы получите буфер, содержащий содержимое этого файла. Для обновления вам понадобится api.c из zip3.0, используя ZpInit и ZpArchive (хотя они не так просты в использовании, как сторона распаковки).

Кроме того, вы можете просто запустить копию zip / unzip в фоновом режиме, чтобы сделать работу. Это не так аккуратно, но, несомненно, немного проще в реализации (а также позволяет легко переключать форматы, если вы выберете).

Answer 3

Кодировка пар байтов обеспечивает произвольный доступ к данным.

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

Однако вам все равно понадобится какой-то индекс для поиска определенного "байта".Поскольку у вас все в порядке с задержкой в ​​1 МБ, вы будете создавать индекс для каждого 1 МБ.Надеюсь, вы сможете найти способ сделать свой индекс достаточно маленьким, чтобы по-прежнему получать выгоду от сжатия.

Одним из преимуществ этого метода также является редактирование с произвольным доступом.Вы можете обновлять, удалять и вставлять данные небольшими порциями.

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

Answer 4

Посмотрите на мой проект - csio . Я думаю, что это именно то, что вы ищете: интерфейс типа stdio и многопоточный компрессор включены.

Это библиотека, написанная на C, которая обеспечивает структуру и функции CFILE cfopen, cfseek, cftello и другие. Вы можете использовать его с обычными (не сжатыми) файлами и с файлами, сжатыми с помощью утилиты dzip. Эта утилита включена в проект и написана на C ++. Он создает действительный архив gzip, который может обрабатываться как стандартными утилитами, так и csio. dzip может сжимать много потоков (см. параметр -j), поэтому он может очень быстро сжимать очень большие файлы.

Типичное использование:

dzip -j4 myfile

...

CFILE file = cfopen("myfile.dz", "r");
off_t some_offset = 673820;
cfseek(file, some_offset);
char buf[100];
cfread(buf, 100, 1, file);
cfclose(file);

Это лицензия MIT, так что вы можете использовать ее в своих проектах без ограничений. Для получения дополнительной информации посетите страницу проекта на github: https://github.com/hoxnox/csio

Answer 5

Вы можете использовать bzip2 и довольно легко создать свой собственный API на основе seek-bzip2

Джеймса Тейлора.

Answer 6

1. Сначала отсортируйте большой файл
2. разделите его на куски желаемого размера (1 МБ) с некоторой последовательностью в имени (File_01, File_02, .., File_NN)
3. взять первый идентификатор из каждого чанка плюс имя файла и поместить обе данные в другой файл
4. сжать куски
5. Вы сможете выполнить поиск в файле идентификатора, используя метод, который вы хотите, может быть двоичный поиск и открыть каждый файл, как вам нужно.

Если вам нужна глубокая индексация, вы можете использовать алгоритм BTree с файлами "pages". в сети существует несколько реализаций этого, потому что код немного хитрый.

Answer 7

Я бы рекомендовал использовать Boost Iostreams Library . Boost.Iostreams можно использовать для создания потоков для доступа к TCP-соединениям или в качестве основы для криптографии и сжатия данных. Библиотека включает компоненты для доступа к отображенным в памяти файлам, для доступа к файлам с использованием файловых дескрипторов операционной системы, для преобразования кода, для фильтрации текста с регулярными выражениями, для преобразования конца строки и для сжатия и распаковки в форматах zlib, gzip и bzip2.

Библиотека Boost была принята комитетом по стандартам C ++ как часть TR2, поэтому в конечном итоге она будет встроена в большинство компиляторов (under std::tr2::sys). Он также кроссплатформенный.

Boost Releases

Руководство по началу работы с Boost ПРИМЕЧАНИЕ. Только некоторые части boost::iostreams являются библиотекой только для заголовков, для которой не требуются отдельно скомпилированные двоичные файлы библиотеки или особая обработка при компоновке.

Answer 8

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