поиск в сжатом отсортированном файле фиксированной ширины

Question

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

Теперь сложность в том, что файл распакован. Возможно ли это сделать без полного надувания файла? Если не с gzip. есть ли сжатие, которое поддерживает такое поведение?

Answer 1

Формат файла bzip2 состоит из нескольких независимо сжатых блоков. Если вы хотите сохранить индекс рядом с файлом bzip2, вы можете знать, где искать.

Примечание: это дубликат вопросов:

• Форматы сжатия с хорошей поддержкой произвольного доступа в архивах?
• произвольный доступ gzip stream
• произвольный доступ к файлам gzip из нескольких частей (на Java)

Они отвечают на тот же вопрос, но также идентифицируют BGZF как gzip-совместимый формат вывода с точками синхронизации, вставленными для сброса состояния сжатия.

Answer 2

Это абсолютно невозможно с файлом, сжатым с помощью zip и производных. Они основаны на скользящем окне словаря, обычно с некоторым своего рода сжатием на основе буфера наиболее значимых битов выходных кодов поверх этого. Суть в том, что определенная последовательность байтов в zip-файле не имеет смысла без контекста.

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

Answer 3

то, что вы хотите - это искомое сжатие; на сервере dict есть dictzip, совместимый по формату с gzip, поскольку он хранит его для поиска в расширении gzip в заголовке, а в наборе sleuth есть sgzip, который не хранит длины блоков в начале каждого из блоков

Answer 4

Продолжая то, что говорит Людвикас Букис: Если у ваших сжатых блоков уникальный заголовок, вам не нужен индекс.Это похоже на поиск в некоторых сжатых видеоформатах.Вы стремитесь к точке и ищите следующий заголовок.Это требует надежной проверки (с использованием контрольной суммы), поскольку возможна неправильная идентификация.

Answer 5

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

Answer 6

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

Сжатие потока означает обычно адаптивное с потерями сжатие с некоторым ключом, который сбрасывает состояние (или фактически разрезает на блоки). Детали более сложные.

Теперь вот пара идей для решения этой проблемы:

• Создание индекса : Как и при открытии ZIP, вы можете увидеть все файлы в нем
• Разрежьте сжатый файл на блоки , а затем используйте бинарный поиск в каждом блоке (фактически аналогично первому)
• Распаковать в память , но фактически отбрасывать любые данные, пока вы не найдете начало искомых данных.

Последний способ подходит для небольших сжатых файлов, а блочный метод - для больших сжатых файлов. Вы можете смешать два.

PS: исправлено с помощью ввода, не означает, что сжатый файл будет исправлен с помощью. Так что это довольно бесполезная информация.