Форматы сжатия с хорошей поддержкой произвольного доступа в архивах?
Это похоже на предыдущий вопрос, но ответы там не удовлетворяют мои потребности, и мой вопрос немного отличается:
В настоящее время я использую сжатие gzip для некоторых очень больших файлов, которые содержат отсортированные данные. Когда файлы не сжаты, бинарный поиск - это удобный и эффективный способ поддержки поиска местоположения в отсортированных данных.
Но когда файлы сжимаются, все становится сложнее. Я недавно узнал о ZlibZ_FULL_FLUSH опция, которую можно использовать во время сжатия для вставки "точек синхронизации" в сжатый вывод (inflateSync() Затем можно начать чтение из различных точек в файле). Это нормально, хотя файлы, которые у меня уже есть, нужно будет повторно сжать, чтобы добавить эту функцию (и странно gzip у меня нет выбора для этого, но я готов написать свою собственную программу сжатия, если я должен).
Кажется из одного источника, что даже Z_FULL_FLUSH не является идеальным решением... оно не только не поддерживается всеми архивами gzip, но и сама идея обнаружения точек синхронизации в архивах может давать ложные срабатывания (либо по совпадению с магическим числом для точек синхронизации, либо из-за того, что тот Z_SYNC_FLUSH также производит точки синхронизации, но они не могут использоваться для произвольного доступа).
Есть ли лучшее решение? Я хотел бы избежать вспомогательных файлов для индексации, если это возможно, и явная поддержка по умолчанию для квазислучайного доступа была бы полезной (даже если она крупнозернистая - например, возможность начать чтение с каждым интервалом 10 МБ). Есть ли другой формат сжатия с лучшей поддержкой случайного чтения, чем gzip?
Изменить: как я уже говорил, я хочу сделать бинарный поиск в сжатых данных. Мне не нужно искать конкретную (несжатую) позицию - только искать с некоторой грубой детализацией в сжатом файле. Мне просто нужна поддержка для чего-то вроде "Распакуйте данные, начиная примерно с 50% (25%, 12,5% и т. Д.) Пути в этот сжатый файл".
12 ответов
Я не знаю ни одного формата сжатых файлов, который бы поддерживал произвольный доступ к определенному месту в несжатых данных (ну, кроме мультимедийных форматов), но вы можете создать свой собственный.
Например, сжатые файлы bzip2 состоят из независимых сжатых блоков размером <1 МБ без сжатия, которые разделены последовательностями магических байтов, так что вы можете проанализировать файл bzip2, получить границы блоков, а затем просто распаковать правый блок. Это потребует некоторой индексации, чтобы запомнить, где начинаются блоки.
Тем не менее, я думаю, что лучшим решением было бы разделить ваш файл на куски по вашему выбору, а затем сжать его каким-нибудь архиватором, таким как zip или rar, который поддерживает произвольный доступ к отдельным файлам в архиве.
Посмотрите на dictzip. Он совместим с gzip и обеспечивает грубый произвольный доступ.
Выдержка из его справочной страницы:
dictzip сжимает файлы с использованием алгоритма gzip(1) (LZ77) способом, полностью совместимым с форматом файлов gzip. Расширение формата файла gzip (дополнительное поле, описанное в 2.3.1.1 RFC 1952) позволяет сохранять дополнительные данные в заголовке сжатого файла. Такие программы, как gzip и zcat, будут игнорировать эти дополнительные данные. Тем не менее, [dictzcat --start] будет использовать эти данные для выполнения псевдослучайного доступа к файлу.
У меня есть пакет dictzip в Ubuntu. Или его исходный код находится в dictd-*. Tar.gz. Его лицензия GPL. Вы можете изучать это.
Обновить:
Я улучшил dictzip, чтобы не ограничивать размер файла. Моя реализация находится под лицензией MIT.
Формат файла.xz (который использует сжатие LZMA), кажется, поддерживает это:
Чтение с произвольным доступом: данные могут быть разбиты на независимо сжатые блоки. Каждый файл.xz содержит индекс блоков, что делает возможным ограниченное чтение с произвольным доступом, когда размер блока достаточно мал.
Этого должно быть достаточно для вашей цели. Недостатком является то, что API liblzma (для взаимодействия с этими контейнерами) не выглядит хорошо документированным, поэтому может потребоваться некоторое усилие, чтобы выяснить, как получить произвольный доступ к блокам.
Формат GZIP может быть произвольный доступ при условии, индекс был ранее создан, как это демонстрируется на ZLIB в zran.c исходного кода.
Я разработал инструмент командной строки на основе zlib zran.c, который создает индексы для файлов gzip: https://github.com/circulosmeos/gztool
Он даже может создать индекс для все еще растущего файла gzip (например, журнала, созданного rsyslog непосредственно в формате gzip), тем самым сокращая на практике время создания индекса до нуля. Увидеть-S(Наблюдать) вариант.
Существуют решения для обеспечения произвольного доступа к архивам gzip и bzip2:
bgzip может сжимать файлы в gzip вариант, который индексируется (и может быть распакован gzip). Это используется в некоторых приложениях биоинформатики, вместе с tabix индексатор.
См. Объяснения здесь: http://blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html и здесь: http://www.htslib.org/doc/tabix.html.
Я не знаю, в какой степени это адаптируется к другим приложениям.
Я не знаю, упоминалось ли это, но проект Kiwix проделал большую работу в этом направлении. Через свою программу Kiwix они предлагают произвольный доступ к файловым архивам ZIM. Хорошее сжатие тоже. Проект возник, когда возникла потребность в автономных копиях Википедии (объем которых в несжатом виде превысил 100 ГБ, включая все носители). Они успешно взяли файл размером 25 ГБ (однофайловый вариант википедии без большинства носителей) и сжали его до ничтожного 8 ГБ файлового архива ZIM. А с помощью программы Kiwix вы можете вызвать любую страницу Википедии со всеми связанными данными быстрее, чем вы можете путешествовать по сети.
Несмотря на то, что программа Kiwix - это технология, основанная на структуре базы данных википедии, она доказывает, что вы можете иметь отличные коэффициенты сжатия и произвольный доступ одновременно.
Поскольку сжатие без потерь работает в некоторых областях лучше, чем в других, если вы храните сжатые данные в блоках удобной длины BLOCKSIZE, даже если каждый блок имеет одинаковое количество сжатых байтов, некоторые сжатые блоки будут расширяться до гораздо более длинного фрагмента открытого текста, чем другие,
Вы можете посмотреть на "Сжатие: ключ к системам извлечения текста следующего поколения" Нивио Живиани, Эдлено Силва де Моуры, Гонсало Наварро и Рикардо Баеза-Йейтса вкомпьютерном журнале, ноябрь 2000 г. http://doi.ieeecomputersociety.org/10.1109/2.881693
Их декомпрессор берет 1, 2 или 3 целых байта сжатых данных и распаковывает (используя словарный список) в целое слово. Можно непосредственно искать в сжатом тексте слова или фразы, что оказывается даже быстрее, чем поиск несжатого текста.
Их декомпрессор позволяет вам указывать на любое слово в тексте с помощью обычного (байтового) указателя и немедленно начинать декомпрессию с этой точки.
Вы можете дать каждому слову уникальный 2-байтовый код, поскольку в вашем тексте, вероятно, содержится менее 65 000 уникальных слов. (В Библии KJV есть почти 13 000 уникальных слов). Даже если существует более 65 000 слов, довольно просто назначить первые 256 двухбайтовых кодовых "слов" для всех возможных байтов, так что вы можете прописать слова, которых нет в лексиконе из 65 000 или около того "чаще всего". слова и фразы". (Сжатие, полученное путем упаковки частых слов и фраз в два байта, обычно стоит "расширения" случайного произнесения слова, используя два байта на букву). Существует множество способов выбрать лексикон "частых слов и фраз", которые дадут адекватное сжатие. Например, вы можете настроить компрессор LZW для вывода "фраз", которые он использует более одного раза, в файл лексикона, по одной строке на фразу, и запустить его для всех ваших данных. Или вы можете произвольно разделить несжатые данные на 5-байтовые фразы в файле лексикона, по одной строке на фразу. Или вы можете нарезать свои несжатые данные на настоящие английские слова и поместить каждое слово, включая пробел в начале слова, в файл лексикона. Затем используйте "sort --unique", чтобы удалить дубликаты слов в этом файле лексикона. (Выбор идеального "оптимального" словарного словаря все еще считается NP-сложным?)
Сохраните лексикон в начале вашего огромного сжатого файла, добавьте его к удобному BLOCKSIZE, а затем сохраните сжатый текст - серию двухбайтовых "слов" - оттуда до конца файла. Предположительно, поисковик прочтет этот лексикон один раз и сохранит его в неком быстром для декодирования формате в ОЗУ во время распаковки, чтобы ускорить распаковку "двухбайтового кода" до "фразы переменной длины". Мой первый черновик начинался с простой строки в каждой фразе, но позже вы могли бы перейти к сохранению лексикона в более сжатой форме с использованием некоторого инкрементного кодирования или zlib.
Вы можете выбрать любое случайное четное смещение байта в сжатый текст и начать декомпрессию оттуда. Я не думаю, что возможно сделать более тонкий формат сжатого файла произвольного доступа.
Два возможных решения:
Позвольте ОС справиться со сжатием, создайте и смонтируйте сжатую файловую систему (SquashFS, clicfs, cloop, cramfs, e2compr или любую другую), содержащую все ваши текстовые файлы, и ничего не делайте со сжатием в вашей прикладной программе.
Используйте сжатие непосредственно для каждого текстового файла (по одному нажатию на текстовый файл) вместо сжатия изображения файловой системы. Представьте, что "mkclicfs mytextfile mycompressedfile" представляет собой "gzip
mycompressedfile" и "clicfs mycompressedfile directory" как способ получения произвольного доступа к данным через файл "directory/mytextfile".
Я не уверен, будет ли это практичным в вашей конкретной ситуации, но не могли бы вы просто сжать каждый большой файл в файлы меньшего размера, скажем, по 10 МБ каждый? В итоге вы получите кучу файлов: file0.gz, file1.gz, file2.gz и т. Д. На основании заданного смещения в исходном большом, вы можете искать в файле с именем "file" + (offset / 10485760) + ".gz", Смещение в несжатом архиве будет offset % 10485760,
Я являюсь автором инструмента с открытым исходным кодом для сжатия определенного типа биологических данных. Этот инструмент называется starch, разделяет данные по хромосомам и использует эти подразделения в качестве индексов для быстрого доступа к сжатым блокам данных в большем архиве.
Данные по каждой хромосоме преобразуются для удаления избыточности в геномных координатах, а преобразованные данные сжимаются либо bzip2 или же gzip алгоритмы. Смещения, метаданные и сжатые геномные данные объединяются в один файл.
Исходный код доступен на нашем сайте GitHub. Мы скомпилировали его под Linux и Mac OS X.
Для вашего случая вы можете хранить (10 МБ или что-то еще) смещения в заголовке в произвольном формате архива. Вы анализируете заголовок, извлекаете смещения и постепенно fseek через файл current_offset_sum + header_size,
Это очень старый вопрос, но похоже, что Zindex может обеспечить хорошее решение (хотя у меня нет большого опыта с этим)
razip поддерживает произвольный доступ с лучшей производительностью, чем gzip/bzip2, который необходимо настроить для этой поддержки, уменьшая сжатие за счет "нормального" произвольного доступа: