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

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

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

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

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

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

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

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

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

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

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

Релизы Boost

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

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

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

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