Форматы сжатия с хорошей поддержкой произвольного доступа в архивах?

Я не знаю ни одного сжатого формата файла, который поддерживал бы произвольный доступ к определенному месту в несжатых данных (ну, кроме мультимедийных форматов), но вы можете создать свой собственный.

Например, сжатые файлы 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 и bzip2:

• gzip zran.c из исходного кода zlib
• bzip2 Node.JS-версия seek-bzip (исходный C версия Джеймса Тейлора вроде бы исчезла из интернета ...)

(Я ищу что-то для 7zip)

bgzip может сжимать файлы в gzip варианте, который индексируется (и может быть распакован с помощью gzip). Он используется в некоторых приложениях биоинформатики вместе с индексатором tabix.

См. Объяснения здесь: http://blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html, а здесь: http://www.htslib.org/doc/tabix.html.

Я не знаю, насколько он адаптируется к другим приложениям.

Доступ к формату gzip можно получить случайным образом при условии, что индекс был ранее создан, как это показано на zran.c исходный код zlib.

Я разработал инструмент командной строки на основе zran.c zlib, который создает индексы для файлов gzip: https://github.com/circulosmeos/gztool

Он может даже создать индекс для все еще растущего файла gzip (например, журнала, созданного rsyslog непосредственно в формате gzip), тем самым сокращая на практике время создания индекса до нуля. См. Параметр -S (Наблюдать).

Я не уверен, будет ли это практичным в вашей конкретной ситуации, но не могли бы вы просто сжать каждый большой файл на файлы меньшего размера, скажем, по 10 МБ каждый? В результате вы получите кучу файлов: file0.gz, file1.gz, file2.gz и т. Д. На основе заданного смещения в пределах исходного размера вы можете искать в файле с именем "file" + (offset / 10485760) + ".gz". Смещение в несжатом архиве будет offset % 10485760.

Поскольку сжатие без потерь работает лучше в некоторых областях, чем в других, если вы храните сжатые данные в блоках удобной длины BLOCKSIZE, даже если каждый блок имеет точно такое же количество сжатых байтов, некоторые сжатые блоки будут расширяться до гораздо более длинного фрагмента открытого текста, чем другие. .

Вы можете посмотреть «Сжатие: ключ к системам поиска текста нового поколения» Нивио Зивиани, Эдлено Сильва де Моура, Гонсало Наварро и Рикардо Баеза-Йейтс в журнале Computer, ноябрь 2000 г. http://doi.ieeecomputersociety.org/10.1109/2.881693

Их декомпрессор берет 1, 2 или 3 целых байта сжатых данных и распаковывает (используя список словаря) в целое слово. Можно напрямую искать в сжатом тексте слова или фразы, что оказывается даже быстрее, чем поиск в несжатом тексте.

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

Вы можете присвоить каждому слову уникальный двухбайтовый код, поскольку в вашем тексте, вероятно, меньше 65 000 уникальных слов. (В Библии KJV почти 13 000 уникальных слов). Даже если имеется более 65 000 слов, довольно просто назначить первые 256 двухбайтовых кодовых «слов» всем возможным байтам, так что вы можете составить слова, которых нет в лексиконе 65 000 или около того «наиболее часто встречающихся» слова и фразы". (Сжатие, достигаемое за счет упаковки частых слов и фраз в два байта, обычно стоит «расширения», когда иногда пишется слово с использованием двух байтов на букву). Существует множество способов подобрать словарный запас «часто встречающихся слов и фраз», которые обеспечат адекватное сжатие. Например, вы можете настроить компрессор LZW, чтобы выгружать «фразы», ​​которые он использует более одного раза, в файл словаря, по одной строке на фразу, и запускать его по всем вашим данным. Или вы можете произвольно разделить несжатые данные на 5-байтовые фразы в файле словаря, по одной строке на фразу. Или вы можете разделить несжатые данные на настоящие английские слова и поместить каждое слово - включая пробел в начале слова - в файл словаря. Затем используйте команду «sort --unique», чтобы удалить повторяющиеся слова в этом файле лексики. (Выбор идеального "оптимального" словарного списка по-прежнему считается непростой задачей?)

Сохраните лексикон в начале вашего огромного сжатого файла, дополните его до некоторого удобного размера BLOCKSIZE, а затем сохраните сжатый текст - серию двухбайтовых «слов» - оттуда до конца файла. Предположительно, поисковик прочитает этот лексикон один раз и сохранит его в каком-либо формате для быстрого декодирования в ОЗУ во время распаковки, чтобы ускорить распаковку «двухбайтового кода» в «фразу переменной длины». Мой первый черновик будет начинаться с простого списка фраз по одной строке, но позже вы можете переключиться на хранение лексики в более сжатой форме, используя какое-то инкрементное кодирование или zlib.

Вы можете выбрать любое случайное смещение в байтах сжатого текста и начать распаковку оттуда. Я не думаю, что возможно создать более детализированный формат сжатого файла с произвольным доступом.

Два возможных решения:

1. Позвольте ОС заниматься сжатием, создавать и монтировать сжатую файловую систему (SquashFS, clicfs, cloop, cramfs, e2compr или что-то еще), содержащую все ваши текстовые файлы, и ничего не делать со сжатием в вашей прикладной программе.

2. Используйте клики непосредственно в каждом текстовом файле (по одному клику на текстовый файл) вместо сжатия образа файловой системы. Думайте о «mkclicfs mytextfile mycompressedfile» как о «gzip‹ mytextfile ›mycompressedfile», а «clicfs mycompressedfile directory» как о способе получения произвольного доступа к данным через файл «directory / mytextfile».

Это очень старый вопрос, но похоже, что zindex может предоставить хорошее решение (хотя у меня нет большой опыт с этим)

Я не знаю, упоминалось ли об этом, но проект Kiwix проделал большую работу в в этом отношении. Через свою программу Kiwix они предлагают произвольный доступ к файловым архивам ZIM. Сжатие тоже хорошее. Проект возник, когда возник спрос на офлайн-копии Википедии (который достиг более 100 ГБ в несжатом виде, включая все носители). Они успешно взяли файл размером 25 ГБ (однофайловый вариант Википедии без большинства носителей) и сжали его в жалкий zim-архив размером 8 ГБ. А с помощью программы Kiwix вы можете вызвать любую страницу Википедии со всеми связанными данными быстрее, чем при серфинге в сети.

Несмотря на то, что программа Kiwix является технологией, основанной на структуре базы данных Википедии, она доказывает, что вы можете иметь отличные коэффициенты сжатия и произвольный доступ одновременно.

razip поддерживает произвольный доступ с лучшей производительностью, чем gzip / bzip2, которые необходимо настроить для этой поддержки - уменьшение сжатия за счет "ok" произвольного доступа:

http://sourceforge.net/projects/razip/

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

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

Исходный код доступен на нашем сайте GitHub. Мы скомпилировали его под Linux и Mac OS X.

В вашем случае вы можете хранить (10 МБ или что-то еще) смещения в заголовке в настраиваемом формате архива. Вы анализируете заголовок, извлекаете смещения и постепенно fseek через файл с помощью current_offset_sum + header_size.