Каков наилучший алгоритм сжатия, который позволяет произвольно читать/записывать в файл?

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

И я знаю, что кодировка хаффмана не может быть и речи.

Есть ли у кого-нибудь лучший алгоритм сжатия, который бы позволял случайные чтения/записи?

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

В контексте ваших ответов, пожалуйста, предположите, что файл, о котором идет речь, составляет 100 ГБ, а иногда я хочу прочитать первые 10 байт, а иногда я хочу прочитать последние 19 байт, а иногда я захочу для чтения 17 байтов в середине..

Ответ 1

Я ошеломлен количеством ответов, которые подразумевают, что такая вещь невозможна.

Не слышали ли эти люди о "сжатых файловых системах", которые существовали с тех пор, как Microsoft в 1993 году подала в суд на Stac Electronics по технологии сжатой файловой системы?

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

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

Также проверьте: fooobar.com/questions/122852/...

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

Я думаю, что Стивен Денн может быть здесь. Представьте себе:

zip-подобное сжатие последовательностей для кодов
код отображения словаря → последовательность Файл
будет похож на файловую систему
- каждая запись генерирует новый "файл" (последовательность байтов, сжатых в соответствии со словарем)
- "файловая система" отслеживает, какой "файл" принадлежит тем байтам (начало, конец)
- каждый "файл" сжимается в соответствии со словарем
- читает работу по файлу, распаковывает и извлекает байты в соответствии с "файловой системой"
- записи делают "файлы" недействительными, новые "файлы" добавляются для замены недействительных
для этой системы потребуется:
- механизм дефрагментации файловой системы
- компактный словарь время от времени (удаление неиспользуемых кодов)
сделано правильно, домашнее хозяйство может быть выполнено, когда никто не ищет (простое), или путем создания нового файла и "переключения" в конечном итоге

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

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

Ответ 5

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

например.
Сначала мы рассмотрим случай только для чтения. Скажем, вы разбиваете свой файл на 8K кусков. Вы сжимаете каждый кусок и сохраняете каждый сжатый фрагмент последовательно. Вам нужно будет записать, где хранится каждый сжатый кусок и насколько он большой. Затем скажите, что вам нужно прочитать N байтов, начиная со смещения O. Вам нужно будет выяснить, какой из них он (O/8K), распаковать этот фрагмент и захватить эти байты. Необходимые данные могут охватывать несколько кусков, поэтому вам придется иметь дело с этим сценарием.

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

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

Ответ 6

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

Однако вы можете приблизиться к произвольному доступу, поддерживая внешний список, созданный во время сжатия, который показывает соответствие между выбранными точками в несжатом потоке данных и их местоположениях в сжатом потоке данных. Вы, очевидно, должны выбрать метод, в котором схема перевода между исходным потоком и его сжатой версией не зависит от местоположения в потоке (т.е. Нет LZ77 или LZ78, вместо этого вы, вероятно, захотите пойти на Huffman или byte- парное кодирование.) Очевидно, что это повлечет за собой большие накладные расходы, и вам нужно будет решить, как вы хотели бы торговать между дисковым пространством, необходимым для "точек закладок", и временем процессора, необходимым для декомпрессии потока, начиная с чтобы получить данные, которые вы действительно ищете для чтения.

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

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

Ответ 7

Никакая схема сжатия не допускает мелкозернистый произвольный доступ по двум причинам:

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

Я могу только предложить обрабатывать файл как широковещательный поток и вставлять частые метки синхронизации/позиции с очевидными накладными расходами (метки синхронизации не только занимают место самостоятельно, но и усложняют кодировку, поскольку она должна избегать "случайных" меток синхронизации!). В качестве альтернативы, и чтобы избежать поиска чего-то вроде бинарного поиска (с оптимизацией, которую вы можете лучше понять, где начать, чем в середине), вы можете включить "оглавление" в начале или конце файла.

Как для записи с произвольным доступом... Я не могу придумать какого-либо опрятного решения: (