Форматы сжатия с хорошей поддержкой произвольного доступа в архивах?
https://stackoverflow.com/questions/429987
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Это похоже на предыдущий вопрос, но ответы там не удовлетворяют мои потребности, и мой вопрос немного другой:
В настоящее время я использую сжатие gzip для некоторых очень больших файлов, содержащих отсортированные данные.Когда файлы не сжаты, двоичный поиск является удобным и эффективным способом поиска местоположения в отсортированных данных.
Но когда файлы сжаты, все становится сложнее.Недавно я узнал о zlib's Z_FULL_FLUSH параметр, который можно использовать во время сжатия для вставки «точек синхронизации» в сжатый вывод (inflateSync() затем можно начать чтение с разных точек файла).Это нормально, хотя файлы, которые у меня уже есть, придется пересжать, чтобы добавить эту функцию (и, как ни странно, gzip у меня нет такой возможности, но я готов написать свою собственную программу сжатия, если потребуется).
Кажется, от один источник что даже Z_FULL_FLUSH это не идеальное решение... оно не только не поддерживается всеми gzip-архивами, но и сама идея обнаружения точек синхронизации в архивах может давать ложные срабатывания (либо из-за совпадения с магическим числом для точек синхронизации, либо из-за того, что что Z_SYNC_FLUSH также создает точки синхронизации, но их нельзя использовать для произвольного доступа).
Есть ли лучшее решение?Я хотел бы по возможности избегать использования вспомогательных файлов для индексации, и явная поддержка по умолчанию квазипроизвольного доступа была бы полезной (даже если она крупномасштабная - например, возможность начинать чтение через каждые 10 МБ).Есть ли другой формат сжатия с лучшей поддержкой случайного чтения, чем gzip?
Редактировать:Как я уже упоминал, я хочу выполнить двоичный поиск в сжатых данных.Мне не нужно искать конкретную (несжатую) позицию — только поиск с некоторой грубой детализацией внутри сжатого файла.Мне просто нужна поддержка чего-то вроде «Распаковать данные, начиная примерно с 50% (25%, 12,5% и т. д.) пути в этот сжатый файл».
Решение
Я не знаю ни одного формата сжатых файлов, который бы поддерживал произвольный доступ к определенному месту в несжатых данных (ну, кроме форматов мультимедиа), но вы можете создать свой собственный.
Например, сжатые файлы bzip2 состоят из независимых сжатых блоков размером < 1 МБ без сжатия, которые разделены последовательностями магических байтов, так что вы можете проанализировать файл bzip2, получить границы блоков, а затем просто распаковать их. правильный блок. Для этого потребуется некоторая индексация, чтобы запомнить, где начинаются блоки.
Тем не менее, я думаю, что лучшим решением было бы разделить ваш файл на куски по вашему выбору, а затем сжать его с помощью какого-нибудь архиватора, такого как zip или rar, который поддерживает произвольный доступ к отдельным файлам в архиве.
Другие советы
Взгляните на dictzip . Он совместим с gzip и допускает грубый произвольный доступ.
Отрывок из его справочной страницы:
dictzip сжимает файлы с использованием алгоритма gzip (1) (LZ77) таким образом, чтобы полностью совместим с форматом файла gzip. Расширение к gzip формат файла (Extra Field, описанный в 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:
bgzip может сжимать файлы в варианте gzip, который индексируется (и может быть распакован с помощью tabix). Это используется в некоторых приложениях биоинформатики вместе с <=> индексатором.
См. пояснения здесь: http: // blastedbio .blogspot.fr / 2011/11 / bgzf-заблокировано-больше-лучше-gzip.html и здесь: http://www.htslib.org/doc/tabix.html .
Я не знаю, в какой степени он может быть адаптирован к другим приложениям.
Я не уверен, будет ли это практичным в вашей конкретной ситуации, но не могли бы вы просто сжать каждый большой файл в файлы меньшего размера, скажем, по 10 МБ каждый? В результате вы получите набор файлов: file0.gz, file1.gz, file2.gz и т. Д. На основе заданного смещения в исходном большом вы можете выполнить поиск в файле с именем "file" + (offset / 10485760) + ".gz". Смещение в несжатом архиве будет offset % 10485760.
Поскольку сжатие без потерь работает лучше в некоторых областях, чем в других, если вы храните сжатые данные в блоках удобной длины BLOCKSIZE, даже если каждый блок имеет одинаковое количество сжатых байтов, некоторые сжатые блоки будут расширяться до гораздо более длинного фрагмента открытого текста, чем другие.
Вы можете посмотреть на " Сжатие: ключ для систем извлечения текста следующего поколения " Нивио Зивиани, Эдлено Сильва де Моура, Гонсало Наварро и Рикардо Баеза-Йейтс в Журнал Компьютер , ноябрь 2000 г. http://doi.ieeecomputersociety.org/10.1109/2.881693
Их декомпрессор берет 1, 2 или 3 целых байта сжатых данных и распаковывает (используя словарный список) в целое слово. Можно непосредственно искать в сжатом тексте слова или фразы, что оказывается даже быстрее, чем поиск несжатого текста.
Их декомпрессор позволяет вам указывать на любое слово в тексте с помощью обычного (байтового) указателя и сразу начинать декомпрессию с этой точки.
Вы можете дать каждому слову уникальный 2-байтовый код, поскольку в вашем тексте, вероятно, содержится менее 65 000 уникальных слов. (В Библии KJV есть почти 13 000 уникальных слов). Даже если существует более 65 000 слов, назначить первые 256 двухбайтовых кодов & Quot; words & Quot; довольно просто. ко всем возможным байтам, чтобы вы могли произносить слова, которых нет в лексиконе из 65 000 слов &; наиболее часто встречающиеся слова и фразы " ;. (Сжатие, полученное путем упаковки частых слов и фраз в два байта обычно стоит " extension " случайного произнесения слова, используя два байта на букву). Существует множество способов выбрать лексикон & Quot; часто встречающиеся слова и фразы & Quot; это даст адекватное сжатие. Например, вы можете настроить компрессор LZW для вывода & Quot; фраз & Quot; он использует более одного раза в файл лексикона, по одной строке на фразу, и запускает его для всех ваших данных. Или вы можете произвольно разделить несжатые данные на 5-байтовые фразы в файле лексикона, по одной строке на фразу. Или вы можете нарезать свои несжатые данные на настоящие английские слова и поместить каждое слово, включая пробел в начале слова, в файл лексикона. Затем используйте & Quot; sort --unique & Quot; удалить дубликаты слов в этом файле лексикона. (Выбор идеального & Слова; оптимальный & Словацкий словарь все еще считается NP-сложным?)
Сохраните лексикон в начале вашего огромного сжатого файла, добавьте его к удобному BLOCKSIZE, а затем сохраните сжатый текст - серию из двух байтов " words " - оттуда до конца файла. Предположительно, поисковик прочтет этот лексикон один раз и сохранит его в неком быстром для декодирования формате в ОЗУ во время распаковки, чтобы ускорить распаковку & Quot; двухбайтового кода & Quot; " переменная длина фразы " ;. Мой первый черновик начинался с простой строки в каждой фразе, но позже вы могли бы перейти к сохранению лексикона в более сжатой форме с использованием некоторого инкрементного кодирования или zlib.
Вы можете выбрать любое случайное четное смещение байта в сжатый текст и начать декомпрессию оттуда. Я не думаю, что возможно сделать более тонкий формат сжатого файла произвольного доступа.
Два возможных решения:
<Ол>Позвольте ОС справиться со сжатием, создайте и смонтируйте сжатую файловую систему (SquashFS, clicfs, cloop, cramfs, e2compr или любую другую), содержащую все ваши текстовые файлы, и ничего не делайте со сжатием в вашей прикладной программе .
Используйте клики непосредственно на каждый текстовый файл (по одному клику на текстовый файл) вместо сжатия изображения файловой системы. Подумайте о & Quot; mkclicfs mytextfile mycompressedfile & Quot; будучи " gzip < mytextfile > mycompressedfile " и " клики по каталогу mycompressedfile " как способ получения произвольного доступа к данным через файл " directory / mytextfile ".
Я не знаю, упоминалось ли об этом, но проект Kiwix проделал большую работу в этом направлении. Через свою программу Kiwix они предлагают произвольный доступ к файловым архивам ZIM. Хорошее сжатие тоже. Проект возник, когда возникла потребность в автономных копиях Википедии (объем которых в несжатом виде превысил 100 ГБ, включая все носители). Они успешно взяли файл размером 25 ГБ (однофайловый вариант википедии без большинства носителей) и сжали его до ничтожного 8 ГБ файлового архива ZIM. А с помощью программы Kiwix вы можете вызывать любую страницу Википедии со всеми связанными данными быстрее, чем вы можете путешествовать по сети.
Несмотря на то, что программа Kiwix - это технология, основанная на структуре базы данных Википедии, она доказывает, что вы можете иметь отличные коэффициенты сжатия и произвольный доступ одновременно.
Это очень старый вопрос, но, похоже, zindex может дать хорошее решение (хотя я не не имеет большого опыта с этим)
razip поддерживает произвольный доступ с лучшей производительностью, чем gzip / bzip2, который необходимо настроить для этой поддержки - уменьшая сжатие за счет " ok " произвольный доступ:
Я являюсь автором инструмента с открытым исходным кодом для сжатия определенного типа биологических данных. Этот инструмент, называемый starch, разделяет данные по хромосомам и использует эти подразделения в качестве индексов для быстрого доступа к сжатым блокам данных в большем архиве.
Данные по каждой хромосоме преобразуются для удаления избыточности в геномных координатах, а преобразованные данные сжимаются с помощью алгоритмов bzip2 или gzip. Смещения, метаданные и сжатые геномные данные объединяются в один файл.
Исходный код доступен на нашем сайте GitHub . Мы скомпилировали его под Linux и Mac OS X.
В вашем случае вы можете хранить смещения (10 МБ и т. д.) в заголовке в произвольном формате архива. Вы анализируете заголовок, извлекаете смещения и постепенно fseek просматриваете файл с помощью current_offset_sum + header_size.
