Предположим, у меня есть обычный файл фиксированной ширины, который отсортирован по одному из полей. Учитывая, что я знаю длину записей, я могу использовать lseek для реализации двоичного поиска для поиска записей с полями, соответствующими заданному значению, без необходимости читать весь файл.
Теперь сложность в том, что файл заархивирован. Можно ли это сделать без полного накачивания файла? Если не с помощью gzip. есть ли какое-либо сжатие, поддерживающее такое поведение?
Это совершенно невозможно с файлом, сжатым с помощью zip и производных. Они основаны на скользящем окне словаря, как правило, с каким-то сжатием на основе буфера наиболее значимых бит выходных кодов поверх этого. Суть в том, что определенная последовательность байтов в zip-файле бессмысленна без контекста.
Если вы хотите иметь возможность произвольно считывать определенную запись из сжатого файла, вам необходимо сжимать каждую запись независимо, а затем иметь индекс в файле. В зависимости от ваших данных, это, вероятно, сделает этап сжатия бесполезным.
Формат файла bzip2 состоит из нескольких независимо сжатых блоков. Если вы хотите поддерживать индекс вместе с файлом bzip2, вы можете знать, где искать.
Примечание: это дубликаты вопросов:
Они отвечают на тот же вопрос, но также идентифицируют BGZF как gzip-совместимый выходной формат с точками синхронизации, вставленными для сброса состояния сжатия.
Практически все известные мне алгоритмы сжатия работают в блочном режиме, то есть случайный поиск невозможен. Даже LZMA, который не использует исходный словарь, требует последовательной декомпрессии.
Сжатие потока обычно означает адаптивное сжатие с потерями с некоторым ключом, который сбрасывает состояние (или фактически разрезает на блоки). Детали более сложные.
Вот несколько идей, как решить эту проблему:
Последний способ подходит для небольших сжатых файлов, а блочный метод - для сжатых файлов большего размера. Вы можете смешать то и другое.
PS: Исправлено с помощью ввода, не означает, что сжатый файл будет исправлен с помощью. Так что это довольно бесполезная информация.
Основываясь на том, что Вернайт сказал, вы можете разбейте файл на множество подфайлов фиксированного размера, прежде чем сжимать его. Ваш двоичный поиск может начаться с поиска подфайла, который содержит диапазон, тогда вам нужно будет распаковать только небольшой подфайл, а не все это целиком. Вы можете оптимизировать, создав файл верхнего уровня в архиве, который содержит первую строку каждого подфайла.
Продолжая то, что говорит Людвикас Букис: Если ваши сжатые блоки имеют уникальный заголовок, вам не нужен индекс. Это похоже на то, как выполняется поиск в некоторых сжатых видеоформатах. Вы ищете точку и ищете следующий заголовок. Тем не менее, это требует надежной проверки (с использованием контрольной суммы), поскольку возможна неправильная идентификация.
вам нужно сжатие с возможностью поиска; у dict-сервера есть dictzip, формат которого совместим с gzip, поскольку он хранит его для поиска в расширении gzip в заголовке, а в наборе для поиска есть sgzip, которого нет, поскольку он хранит длину блоков в начале каждого из блоков
